Editorial for Hội trường


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const maxn=10000;
      maxs=30000;
var n,num:longint;
    a:array[0..maxn,0..1] of longint;
    b,c:array[0..maxs] of longint;

procedure rf;
var i:longint;
begin
     readln(n);
     for i:=1 to n do readln(a[i,0],a[i,1]);
end;

procedure sort(l,r:longint);
var i,j,x:longint;
begin
     i:=l; j:=r; x:=a[(i+j) div 2,1];
     repeat
           while a[i,1]<x do i:=i+1;
           while a[j,1]>x do j:=j-1;
           if i<=j then
           begin
                a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0];
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

function bs(t,num:longint):longint;
var l,r,m:longint;
begin
     l:=1; r:=num; m:=0;
     while l<=r do
     begin
          m:=(l+r) div 2;
          if b[m]=t then break
          else
          begin
               if b[m]>t then r:=m-1
               else l:=m+1;
          end;
     end;
     while (b[m]>t) and (m>0) do dec(m);
     bs:=m;
end;

procedure pr;
var i,t,u,k:longint;
begin
     sort(1,n);
     fillchar(b,sizeof(b),0);
     fillchar(c,sizeof(c),0);
     num:=0;
     for i:=1 to n do
     begin
          t:=a[i,0]; u:=a[i,1];
          k:=bs(t,num);
          if (c[k]+u-t>c[num]) then
          begin
               num:=num+1;
               b[num]:=u;
               c[num]:=c[k]+u-t;
          end;
     end;
end;

procedure wf;
begin
     write(c[num]);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include <cstdio>
#include <vector>
using namespace std;

#define TR(v, it) for(typeof((v).begin()) it = (v).begin(), _e = (v).end(); it != _e; ++it )
#define fi first
#define se second
#define MAX 30000
typedef pair<int, int> ii;

int n;
vector<int> req[MAX+5];
int f[MAX+5];

int max( int a, int b ) {
    return a > b ? a : b;
}

int main() {
    scanf( "%d", &n );
    for( int i = 0; i < n; ++i ) {
        int p, k; scanf( "%d%d", &p, &k );
        req[k].push_back(p);
    }
    f[0] = 0;
    for( int i = 1; i <= MAX; ++i ) {
        f[i] = f[i-1];
        TR(req[i], it) {
            //printf( "%d %d %d\n", *it, i, i-*it + f[*it] );
            f[i] = max( f[i], i-*it + f[*it] );
        }
    }
    printf( "%d\n", f[MAX] );
    //for( int i = 0; i <= 20; ++i ) printf( "%d ", f[i] );
    return 0;
}

Code mẫu của ladpro98

program nkrez;
uses    math;
const   maxN=10001;
        fi='';
type    offer = record
        p,k:longint;
        end;
var     f:array[0..maxN] of longint;
        a:array[1..maxN] of offer;
        n:longint;
procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        readln(inp,a[i].p,a[i].k);
        close(inp);
end;

procedure swap(i,j:longint);
var     t:offer;
begin
        t:=a[i];
        a[i]:=a[j];
        a[j]:=t;
end;

function find(last,key:longint):longint;
var     l,r,m,k:longint;
begin
        l:=1;
        r:=last;
        k:=1;
        while l<=r do
        begin
                m:=(l+r) shr 1;
                if a[m].k<=key then
                begin
                        k:=m;
                        l:=m+1;
                end
                else
                r:=m-1;
        end;
        exit(k);
end;

procedure sort(l,r:longint);
var     pivot,i,j:longint;
begin
        if l>=r then exit;
        pivot:=a[random(r-l+1)+l].k;
        i:=l;j:=r;
        repeat
                while a[i].k<pivot do inc(i);
                while a[j].k>pivot do dec(j);
                if i<=j then
                begin
                        if i<j then swap(i,j);
                        inc(i);
                        dec(j);
                end;
        until i>j;
        sort(l,j);
        sort(i,r);


end;

procedure dp;
var     i,j:longint;
begin
        f[0]:=0;
        for i:=1 to n do
        begin
                f[i]:=max(a[i].k-a[i].p,f[i-1]);
                j:=find(i-1,a[i].p);
                if a[j].k<=a[i].p then
                        f[i]:=max(f[i],a[i].k-a[i].p+f[j]);
        end;
end;

begin
        input;
        sort(1,n);
        dp;
        write(f[n]);
end.

Code mẫu của RR

uses math;
var
  res,u,i,n:longint;
  a,b:array[1..10111] of longint;
  bit:array[1..30111] of longint;

procedure swap(var a,b:longint);
    var
      tmp:longint;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure sort(l,r:longint);
    var
      i,j,mid:longint;
    begin
      i:=l; j:=r; mid:=a[l+random(r-l+1)];
      repeat
        while a[i]<mid do inc(i);
        while a[j]>mid do dec(j);
        if i<=j then
          begin
            swap(a[i],a[j]);
            swap(b[i],b[j]);
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort(i,r);
      if l<j then sort(l,j);
    end;

function get(u:longint):longint;
    var
      v:longint;
    begin
      if u<=0 then exit(0);
      v:=u-u and (-u);
      exit(max(bit[u],get(v)));
    end;

procedure update(u,k:longint);
    var
      v:longint;
    begin
      bit[u]:=max(bit[u],k);
      v:=u+u and (-u);
      if v<=30000 then update(v,k);
    end;

begin
  read(n);
  for i:=1 to n do
    begin
      read(a[i],b[i]);
      inc(a[i]);
      inc(b[i]);
    end;
  sort(1,n);

  for i:=1 to n do
    begin
      u:=get(a[i])+b[i]-a[i];
      res:=max(res,u);
      update(b[i],u);
    end;
  writeln(res);
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
void quickSort(long A[],long d[],long lower,long upper)
{
        long x = A[(lower + upper) / 2];
        long i = lower;
        long j = upper;
        do{
                while(A[i] < x)
                        i ++;
                while (A[j] > x)
                        j --;
                if (i <= j)
                {
                     long tg=A[i];
                     A[i]=A[j];
                     A[j]=tg;
                     long tgd=d[i];
                     d[i]=d[j];
                     d[j]=tgd;    
                        i ++;
                        j --;
                }
        }while(i <= j);
        if (j > lower)
                quickSort(A,d, lower, j);
        if (i < upper)
                quickSort(A,d, i, upper);
}
main()
{
long n,p[10000],k[10000],A[10000],d[10000],F[10000],Max,MaxF=0;      
scanf("%ld",&n);
for(long i=0;i<n;i++)
  {
  scanf("%ld %ld",&p[i],&k[i]);
  A[i]=p[i];
  d[i]=i;
  }
quickSort(A,d,0,n-1);
F[0]=k[d[0]]-p[d[0]];
for(long i=1;i<n;i++)
  {
  F[i]=k[d[i]]-p[d[i]];
  Max=0;
  for(int j=0;j<i;j++)
    if(k[d[j]]<=p[d[i]]&&F[j]>Max)
      Max=F[j];
  F[i]+=Max;
  }
for(long i=0;i<n;i++)  
  if(F[i]>MaxF)
    MaxF=F[i];
printf("%ld",MaxF);
//getch();
}

Code mẫu của ll931110

program NKREZ;
const
  input  = '';
  output = '';
  maxn = 10000;
  maxk = 30000;
type
  rec = record
    x,y: integer;
  end;
var
  a: array[1..maxn] of rec;
  res: array[0..maxk] of integer;
  n: integer;

procedure init;
var
  f: text;
  i: integer;
begin
  assign(f, input);
    reset(f);

  readln(f, n);
  for i := 1 to n do readln(f, a[i].x, a[i].y);

  close(f);
end;

procedure swap(var u,v: rec);
var
  z: rec;
begin
  z := u;  u := v;  v := z;
end;

procedure qsort(l,h: integer);
var
  i,j: integer;
  p: rec;
begin
  if l >= h then exit;
  i := l;  j := h;  p := a[random(h - l + 1) + l];

  repeat
    while a[i].y < p.y do inc(i);
    while a[j].y > p.y do dec(j);

    if i <= j then
      begin
        if i < j then swap(a[i],a[j]);
        inc(i);
        dec(j);
      end;
  until i > j;

  qsort(l,j);
  qsort(i,h);
end;

procedure solve;
var
  f: text;
  i,j,max: integer;
begin
  fillchar(res, sizeof(res), 0);
  max := a[n].y;

  res[a[1].y] := a[1].y - a[1].x;
  for i := 2 to n do
    begin
      if a[i].y > a[i - 1].y then
        for j := a[i - 1].y + 1 to a[i].y do
          if res[j] < res[a[i - 1].y] then res[j] := res[a[i - 1].y];

      if res[a[i].y] < res[a[i].x] + a[i].y - a[i].x
        then res[a[i].y] := res[a[i].x] + a[i].y - a[i].x;
    end;

  assign(f, output);
    rewrite(f);
    writeln(f, res[max]);
  close(f);
end;

begin
  init;
  qsort(1,n);
  solve;
end.

Code mẫu của skyvn97

#include<stdio.h>
#include<algorithm>
#define MAX   11111
using namespace std;
typedef pair<int,int> ii;
ii a[MAX];
int n;
int f[MAX];
void init(void) {
    scanf("%d",&n);
    int i,p,k;
    for (i=1;i<=n;i=i+1) {
        scanf("%d",&p);
        scanf("%d",&k);
        a[i]=ii(k,p);
    }
    sort(&a[1],&a[n+1]);    
    a[0]=ii(0,0);
}
int bs(int l,int r,int val) {
    if (l==r) return (r);
    if (r-l==1) {
        if (a[r].first<=val) return (r);
        return (l);
    }
    int m=(l+r)/2;
    if (a[m].first<=val) return (bs(m,r,val));
    return (bs(l,m,val));
}
void optimize(void) {
    int i,x;
    f[0]=0;
    f[1]=a[1].first-a[1].second;
    for (i=2;i<=n;i=i+1) {
        f[i]=f[i-1];
        x=bs(0,i-1,a[i].second);
        if (f[x]+a[i].first-a[i].second>f[i]) f[i]=f[x]+a[i].first-a[i].second;
    }       
    printf("%d",f[n]);
}
int main(void) {    
    init();
    optimize();
}

Code mẫu của khuc_tuan

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int n;
int a[10010], b[10010];
vector<int> list[30030];
int F[30030];

int main() {
    scanf("%d", &n);
    for(int i=0;i<n;++i) { scanf("%d%d", a+i, b+i); a[i] +=10; b[i] += 10; }
    for(int i=0;i<n;++i) list[b[i]].push_back(a[i]);
    F[0] = 0;
    for(int i=1;i<=30020;++i) {
        F[i] = F[i-1];
        for(int k=0;k<list[i].size();++k) {
            int j = list[i][k];
            F[i] >?= F[j] + i - j;
        }
    }
    cout << F[30020] << endl;
    //system("pause");
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.