oj.uz

Submission #13432

# Submission time Handle Problem Language Result Execution time Memory
13432 2015-02-20T07:42:08 Z dohyun0324 Wombats (IOI13_wombats) C++
100 / 100
 17464 ms 197664 KB 
#include "wombats.h"
#include<algorithm>
#define M 2147483647
using namespace std;
int r,c,h[5010][210],v[5010][210],tree[1026][210][210],d[11][210][210],arr[210],D[11][210][210],imsi[210],t,ch[2010],arr2[210],imsi2[210];
void Merge(int x)
{
    int i,j,k,l,w=0; x/=2;
    while(x){
        ch[x]=1, arr[1]=1, arr[2]=c;
        if(ch[x*2+1]==0){
            for(j=1;j<=c;j++) for(k=1;k<=c;k++) tree[x][j][k]=tree[x*2][j][k];
            x/=2; continue;
        }
        for(j=c;j>=1;j--){
            for(k=1;k<=c-j+1;k++){
                tree[x][k][k+j-1]=M;
                for(l=arr[k];l<=arr[k+1];l++){
                    if(tree[x][k][k+j-1]>tree[x*2][k][l]+tree[x*2+1][l][k+j-1]) tree[x][k][k+j-1]=tree[x*2][k][l]+tree[x*2+1][l][k+j-1], imsi[k]=l;
                }
            }
            for(k=2;k<=c-j+2;k++) arr[k]=imsi[k-1];
            arr[1]=1; arr[c-j+3]=c;
        }
        arr[1]=1, arr[2]=c;
        for(j=c;j>=1;j--){
            for(k=1;k<=c-j+1;k++){
                tree[x][k+j-1][k]=M;
                for(l=arr[k];l<=arr[k+1];l++){
                    if(tree[x][k+j-1][k]>tree[x*2][k+j-1][l]+tree[x*2+1][l][k]) tree[x][k+j-1][k]=tree[x*2][k+j-1][l]+tree[x*2+1][l][k], imsi[k]=l;
                }
            }
            for(k=2;k<=c-j+2;k++) arr[k]=imsi[k-1];
            arr[1]=1; arr[c-j+3]=c;
        }
        x/=2;
    }
}
void update(int x)
{
    int p,i,j,k,l,w=0,s1,s2;
    for(i=(x-1)*10+1;i<=min(r-1,(x-1)*10+10);i++){
        w++; arr[1]=arr2[1]=1, arr[2]=arr2[2]=c;
        for(j=c;j>=1;j--){
            for(k=1;k<=c-j+1;k++){
                d[w][k][k+j-1]=M; d[w][k+j-1][k]=M;
                for(l=arr[k];l<=arr[k+1];l++){
                    if(l>=k) s1=1; else s1=-1;
                    if(l<=k+j-1) s2=1; else s2=-1;
                    p=v[i][l]+s2*(h[i+1][k+j-2]-h[i+1][l-1])+s1*(h[i][l-1]-h[i][k-1]);
                    if(d[w][k][k+j-1]>p) d[w][k][k+j-1]=p, imsi[k]=l;
                }
                for(l=arr2[k];l<=arr2[k+1];l++){
                    if(l>=k) s1=1; else s1=-1;
                    if(l<=k+j-1) s2=1; else s2=-1;
                    p=v[i][l]+s2*(h[i][k+j-2]-h[i][l-1])+s1*(h[i+1][l-1]-h[i+1][k-1]);
                    if(d[w][k+j-1][k]>p) d[w][k+j-1][k]=p, imsi2[k]=l;
                }
            }
            for(k=2;k<=c-j+2;k++) arr[k]=imsi[k-1];
            for(k=2;k<=c-j+2;k++) arr2[k]=imsi2[k-1];
            arr[1]=1; arr[c-j+3]=c; arr2[1]=1; arr2[c-j+3]=c;
        }
    }
    for(i=1;i<=c;i++) for(j=1;j<=c;j++) D[1][i][j]=d[1][i][j];
    for(i=2;i<=w;i++){
        arr[2]=c;
        for(j=c;j>=1;j--){
            for(k=1;k<=c-j+1;k++){
                D[i][k][k+j-1]=M;
                for(l=arr[k];l<=arr[k+1];l++){
                    p=D[i-1][k][l]+d[i][l][k+j-1];
                    if(D[i][k][k+j-1]>p) D[i][k][k+j-1]=p, imsi[k]=l;
                }
            }
            for(k=2;k<=c-j+2;k++) arr[k]=imsi[k-1];
            arr[1]=1; arr[c-j+3]=c;
        }
        arr[2]=c;
        for(j=c;j>=1;j--){
            for(k=1;k<=c-j+1;k++){
                D[i][k+j-1][k]=M;
                for(l=arr[k];l<=arr[k+1];l++){
                    p=D[i-1][k+j-1][l]+d[i][l][k];
                    if(D[i][k+j-1][k]>p) D[i][k+j-1][k]=p, imsi[k]=l;
                }
            }
            for(k=2;k<=c-j+2;k++) arr[k]=imsi[k-1];
            arr[1]=1; arr[c-j+3]=c;
        }
    }
    for(i=1;i<=c;i++) for(j=1;j<=c;j++) tree[x+t-1][i][j]=D[w][i][j];
    ch[x+t-1]=1;
    Merge(x+t-1);
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r=R; c=C;
    int i,j;
    for(i=1;i<=r;i++){
        for(j=1;j<=c-1;j++){
            h[i][j]=h[i][j-1]+H[i-1][j-1];
        }
    }
    for(i=1;i<=r-1;i++){
        for(j=1;j<=c;j++){
            v[i][j]=V[i-1][j-1];
        }
    }
    for(t=1;t<(r-2)/10+1;t*=2);
    for(i=1;i<=(r-2)/10+1;i++) update(i);
}
void changeH(int P, int Q, int W) {
    int i,j,s; P++; Q++;
    s=W-(h[P][Q]-h[P][Q-1]);
    for(i=Q;i<=c-1;i++) h[P][i]+=s;
    if(P==r) P--;
    update((P-1)/10+1);
    if((P-1)/10 && P%10==1) update((P-1)/10);
}
void changeV(int P, int Q, int W) {
    v[P+1][Q+1]=W;
    update(P/10+1);
}
int escape(int V1, int V2) {
    return tree[1][V1+1][V2+1];
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 197664 KB Output is correct - 505 tokens
2 Correct 4 ms 197664 KB Output is correct - 505 tokens
3 Correct 52 ms 197664 KB Output is correct - 200005 tokens
4 Correct 0 ms 197664 KB Output is correct - 505 tokens
5 Correct 0 ms 197664 KB Output is correct - 505 tokens
6 Correct 0 ms 197664 KB Output is correct - 6 tokens
7 Correct 0 ms 197664 KB Output is correct - 6 tokens
8 Correct 0 ms 197664 KB Output is correct - 6 tokens

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 197664 KB Output is correct - 6 tokens
2 Correct 0 ms 197664 KB Output is correct - 6 tokens
3 Correct 0 ms 197664 KB Output is correct - 6 tokens
4 Correct 0 ms 197664 KB Output is correct - 405 tokens
5 Correct 0 ms 197664 KB Output is correct - 405 tokens
6 Correct 0 ms 197664 KB Output is correct - 405 tokens
7 Correct 0 ms 197664 KB Output is correct - 405 tokens
8 Correct 2 ms 197664 KB Output is correct - 366 tokens
9 Correct 0 ms 197664 KB Output is correct - 405 tokens
10 Correct 0 ms 197664 KB Output is correct - 366 tokens
11 Correct 96 ms 197664 KB Output is correct - 200005 tokens
12 Correct 0 ms 197664 KB Output is correct - 405 tokens

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 197664 KB Output is correct - 105 tokens
2 Correct 356 ms 197664 KB Output is correct - 105 tokens
3 Correct 487 ms 197664 KB Output is correct - 105 tokens
4 Correct 459 ms 197664 KB Output is correct - 105 tokens
5 Correct 461 ms 197664 KB Output is correct - 105 tokens
6 Correct 0 ms 197664 KB Output is correct - 6 tokens
7 Correct 0 ms 197664 KB Output is correct - 6 tokens
8 Correct 0 ms 197664 KB Output is correct - 6 tokens
9 Correct 1824 ms 197664 KB Output is correct - 105 tokens
10 Correct 0 ms 197664 KB Output is correct - 8 tokens

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 197664 KB Output is correct - 1005 tokens
2 Correct 3 ms 197664 KB Output is correct - 1005 tokens
3 Correct 0 ms 197664 KB Output is correct - 1005 tokens
4 Correct 45 ms 197664 KB Output is correct - 100005 tokens

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 197664 KB Output is correct - 105 tokens
2 Correct 357 ms 197664 KB Output is correct - 105 tokens
3 Correct 490 ms 197664 KB Output is correct - 105 tokens
4 Correct 453 ms 197664 KB Output is correct - 105 tokens
5 Correct 459 ms 197664 KB Output is correct - 105 tokens
6 Correct 3 ms 197664 KB Output is correct - 1005 tokens
7 Correct 0 ms 197664 KB Output is correct - 1005 tokens
8 Correct 11 ms 197664 KB Output is correct - 1005 tokens
9 Correct 36 ms 197664 KB Output is correct - 100005 tokens
10 Correct 4 ms 197664 KB Output is correct - 505 tokens
11 Correct 3 ms 197664 KB Output is correct - 505 tokens
12 Correct 89 ms 197664 KB Output is correct - 200005 tokens
13 Correct 0 ms 197664 KB Output is correct - 505 tokens
14 Correct 0 ms 197664 KB Output is correct - 505 tokens
15 Correct 0 ms 197664 KB Output is correct - 6 tokens
16 Correct 0 ms 197664 KB Output is correct - 6 tokens
17 Correct 0 ms 197664 KB Output is correct - 6 tokens
18 Correct 0 ms 197664 KB Output is correct - 405 tokens
19 Correct 2 ms 197664 KB Output is correct - 405 tokens
20 Correct 0 ms 197664 KB Output is correct - 405 tokens
21 Correct 0 ms 197664 KB Output is correct - 405 tokens
22 Correct 2 ms 197664 KB Output is correct - 366 tokens
23 Correct 0 ms 197664 KB Output is correct - 405 tokens
24 Correct 0 ms 197664 KB Output is correct - 366 tokens
25 Correct 76 ms 197664 KB Output is correct - 200005 tokens
26 Correct 0 ms 197664 KB Output is correct - 405 tokens
27 Correct 1828 ms 197664 KB Output is correct - 105 tokens
28 Correct 3984 ms 197664 KB Output is correct - 50005 tokens
29 Correct 4416 ms 197664 KB Output is correct - 50005 tokens
30 Correct 4351 ms 197664 KB Output is correct - 50005 tokens
31 Correct 4091 ms 197664 KB Output is correct - 200005 tokens
32 Correct 2 ms 197664 KB Output is correct - 8 tokens

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 197664 KB Output is correct - 105 tokens
2 Correct 355 ms 197664 KB Output is correct - 105 tokens
3 Correct 488 ms 197664 KB Output is correct - 105 tokens
4 Correct 458 ms 197664 KB Output is correct - 105 tokens
5 Correct 466 ms 197664 KB Output is correct - 105 tokens
6 Correct 7 ms 197664 KB Output is correct - 1005 tokens
7 Correct 7 ms 197664 KB Output is correct - 1005 tokens
8 Correct 4 ms 197664 KB Output is correct - 1005 tokens
9 Correct 36 ms 197664 KB Output is correct - 100005 tokens
10 Correct 0 ms 197664 KB Output is correct - 505 tokens
11 Correct 0 ms 197664 KB Output is correct - 505 tokens
12 Correct 92 ms 197664 KB Output is correct - 200005 tokens
13 Correct 0 ms 197664 KB Output is correct - 505 tokens
14 Correct 7 ms 197664 KB Output is correct - 505 tokens
15 Correct 6980 ms 197664 KB Output is correct - 11 tokens
16 Correct 17464 ms 197664 KB Output is correct - 200005 tokens
17 Correct 0 ms 197664 KB Output is correct - 6 tokens
18 Correct 0 ms 197664 KB Output is correct - 6 tokens
19 Correct 0 ms 197664 KB Output is correct - 6 tokens
20 Correct 2 ms 197664 KB Output is correct - 405 tokens
21 Correct 0 ms 197664 KB Output is correct - 405 tokens
22 Correct 2 ms 197664 KB Output is correct - 405 tokens
23 Correct 0 ms 197664 KB Output is correct - 405 tokens
24 Correct 2 ms 197664 KB Output is correct - 366 tokens
25 Correct 0 ms 197664 KB Output is correct - 405 tokens
26 Correct 0 ms 197664 KB Output is correct - 366 tokens
27 Correct 71 ms 197664 KB Output is correct - 200005 tokens
28 Correct 0 ms 197664 KB Output is correct - 405 tokens
29 Correct 1855 ms 197664 KB Output is correct - 105 tokens
30 Correct 3976 ms 197664 KB Output is correct - 50005 tokens
31 Correct 15546 ms 197664 KB Output is correct - 100005 tokens
32 Correct 15346 ms 197664 KB Output is correct - 100005 tokens
33 Correct 4429 ms 197664 KB Output is correct - 50005 tokens
34 Correct 16051 ms 197664 KB Output is correct - 100005 tokens
35 Correct 4342 ms 197664 KB Output is correct - 50005 tokens
36 Correct 15595 ms 197664 KB Output is correct - 100005 tokens
37 Correct 4096 ms 197664 KB Output is correct - 200005 tokens
38 Correct 15459 ms 197664 KB Output is correct - 200005 tokens
39 Correct 0 ms 197664 KB Output is correct - 8 tokens
40 Correct 16122 ms 197664 KB Output is correct - 100005 tokens