답안 #16754 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16754	2015-09-18T12:22:33 Z	CodingBug	웜뱃 (IOI13_wombats)	C++	100 / 100	7631 ms	180520 KB

wombats

#include "wombats.h"
#include <algorithm>
#define R 5000
#define C 200
#define INF 1000000000

using namespace std;

struct Node{
    int d[C][C];
    Node *chi[2];
} *rt;

int r,c;
int h[R][C],v[R][C];

void dp(int d[C][C],int s,int e){
    int i,j,k;

    for(k=0;k<c;k++){
        for(j=0;j<c;j++) d[k][j]=(k==j ? 0 : INF+1);

        for(i=s;i<e;i++){
            for(j=1;j<c;j++) d[k][j]=min(d[k][j],d[k][j-1]+h[i][j-1]);
            for(j=c-2;j>=0;j--) d[k][j]=min(d[k][j],d[k][j+1]+h[i][j]);
            for(j=0;j<c;j++) d[k][j]+=v[i][j];
        }
        for(j=1;j<c;j++) d[k][j]=min(d[k][j],d[k][j-1]+h[i][j-1]);
        for(j=c-2;j>=0;j--) d[k][j]=min(d[k][j],d[k][j+1]+h[i][j]);
    }
}

void mgDynamic(Node *no,int mid){
    int i,j,k,t=0;
    int l[2][C+1];
    l[0][0]=0;
    l[0][1]=c-1;

    for(i=-(c-1);i<0;i++){
        l[!t][0]=0;
        for(j=-i;j<c;j++){
            int p;
            p=k=l[t][j+i];
            no->d[j][j+i]=no->chi[0]->d[j][k]+no->chi[1]->d[k][j+i]+v[mid][k];
            for(k=l[t][j+i]+1;k<=l[t][j+i+1];k++){
                if(no->d[j][j+i]>no->chi[0]->d[j][k]+no->chi[1]->d[k][j+i]+v[mid][k]){
                    p=k;
                    no->d[j][j+i]=no->chi[0]->d[j][k]+no->chi[1]->d[k][j+i]+v[mid][k];
                }
            }
            l[!t][j+i+1]=p;
        }
        l[!t][i+c+1]=c-1;
        t=!t;
    }
    for(i=0;i<c;i++){
        for(j=0;j<c-i;j++){
            int p;
            p=k=l[t][j+i];
            no->d[j][j+i]=no->chi[0]->d[j][k]+no->chi[1]->d[k][j+i]+v[mid][k];
            for(k=l[t][j+i]+1;k<=l[t][j+i+1];k++){
                if(no->d[j][j+i]>no->chi[0]->d[j][k]+no->chi[1]->d[k][j+i]+v[mid][k]){
                    p=k;
                    no->d[j][j+i]=no->chi[0]->d[j][k]+no->chi[1]->d[k][j+i]+v[mid][k];
                }
            }
            l[!t][j+i+1]=p;
        }
        t=!t;
    }
}

void setTree(int s,int e,Node *no){
    if(s+16>=e){
        dp(no->d,s,e);
        return;
    }
    int mid=(s+e)/2;
    if(!no->chi[0]) no->chi[0]=new Node();
    if(!no->chi[1]) no->chi[1]=new Node();
    setTree(s,mid,no->chi[0]);
    setTree(mid+1,e,no->chi[1]);

    mgDynamic(no,mid);
}

void updateTree(int s,int e,int x,Node *no){
    if(e<x || x<s) return;
    if(s+16>=e){
        dp(no->d,s,e);
        return;
    }
    int mid=(s+e)/2;
    updateTree(s,mid,x,no->chi[0]);
    updateTree(mid+1,e,x,no->chi[1]);

    mgDynamic(no,mid);
}

void init(int _r, int _c, int H[5000][200], int V[5000][200]) {
    int i,j;
    r=_r; c=_c;
    for(i=0;i<r;i++) for(j=0;j<c-1;j++) h[i][j]=H[i][j];
    for(i=0;i<r-1;i++) for(j=0;j<c;j++) v[i][j]=V[i][j];

    rt=new Node();
    setTree(0,r-1,rt);
}

void changeH(int P, int Q, int W) {
    h[P][Q]=W;
    updateTree(0,r-1,P,rt);
}

void changeV(int P, int Q, int W) {
    v[P][Q]=W;
    updateTree(0,r-1,P,rt);
}

int escape(int V1, int V2) {
    return rt->d[V1][V2];
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	180520 KB	Output is correct - 505 tokens
2	Correct	0 ms	180520 KB	Output is correct - 505 tokens
3	Correct	119 ms	180520 KB	Output is correct - 200005 tokens
4	Correct	17 ms	180520 KB	Output is correct - 505 tokens
5	Correct	29 ms	180520 KB	Output is correct - 505 tokens
6	Correct	0 ms	17000 KB	Output is correct - 6 tokens
7	Correct	0 ms	17000 KB	Output is correct - 6 tokens
8	Correct	0 ms	17000 KB	Output is correct - 6 tokens

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	17000 KB	Output is correct - 6 tokens
2	Correct	0 ms	17000 KB	Output is correct - 6 tokens
3	Correct	0 ms	17000 KB	Output is correct - 6 tokens
4	Correct	0 ms	17320 KB	Output is correct - 405 tokens
5	Correct	0 ms	17320 KB	Output is correct - 405 tokens
6	Correct	0 ms	17320 KB	Output is correct - 405 tokens
7	Correct	0 ms	17320 KB	Output is correct - 405 tokens
8	Correct	0 ms	17320 KB	Output is correct - 366 tokens
9	Correct	0 ms	17320 KB	Output is correct - 405 tokens
10	Correct	0 ms	17320 KB	Output is correct - 366 tokens
11	Correct	87 ms	17320 KB	Output is correct - 200005 tokens
12	Correct	0 ms	17320 KB	Output is correct - 405 tokens

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	170 ms	19240 KB	Output is correct - 105 tokens
2	Correct	168 ms	19240 KB	Output is correct - 105 tokens
3	Correct	185 ms	19240 KB	Output is correct - 105 tokens
4	Correct	184 ms	19240 KB	Output is correct - 105 tokens
5	Correct	176 ms	19240 KB	Output is correct - 105 tokens
6	Correct	0 ms	17000 KB	Output is correct - 6 tokens
7	Correct	0 ms	17000 KB	Output is correct - 6 tokens
8	Correct	0 ms	17000 KB	Output is correct - 6 tokens
9	Correct	790 ms	19240 KB	Output is correct - 105 tokens
10	Correct	0 ms	17000 KB	Output is correct - 8 tokens

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	180520 KB	Output is correct - 1005 tokens
2	Correct	22 ms	180520 KB	Output is correct - 1005 tokens
3	Correct	5 ms	180520 KB	Output is correct - 1005 tokens
4	Correct	61 ms	180520 KB	Output is correct - 100005 tokens

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	173 ms	19240 KB	Output is correct - 105 tokens
2	Correct	164 ms	19240 KB	Output is correct - 105 tokens
3	Correct	186 ms	19240 KB	Output is correct - 105 tokens
4	Correct	186 ms	19240 KB	Output is correct - 105 tokens
5	Correct	181 ms	19240 KB	Output is correct - 105 tokens
6	Correct	11 ms	180520 KB	Output is correct - 1005 tokens
7	Correct	45 ms	180520 KB	Output is correct - 1005 tokens
8	Correct	16 ms	180520 KB	Output is correct - 1005 tokens
9	Correct	48 ms	180520 KB	Output is correct - 100005 tokens
10	Correct	34 ms	180520 KB	Output is correct - 505 tokens
11	Correct	29 ms	180520 KB	Output is correct - 505 tokens
12	Correct	138 ms	180520 KB	Output is correct - 200005 tokens
13	Correct	19 ms	180520 KB	Output is correct - 505 tokens
14	Correct	0 ms	180520 KB	Output is correct - 505 tokens
15	Correct	0 ms	17000 KB	Output is correct - 6 tokens
16	Correct	0 ms	17000 KB	Output is correct - 6 tokens
17	Correct	0 ms	17000 KB	Output is correct - 6 tokens
18	Correct	0 ms	17320 KB	Output is correct - 405 tokens
19	Correct	0 ms	17320 KB	Output is correct - 405 tokens
20	Correct	0 ms	17320 KB	Output is correct - 405 tokens
21	Correct	0 ms	17320 KB	Output is correct - 405 tokens
22	Correct	0 ms	17320 KB	Output is correct - 366 tokens
23	Correct	0 ms	17320 KB	Output is correct - 405 tokens
24	Correct	0 ms	17320 KB	Output is correct - 366 tokens
25	Correct	80 ms	17320 KB	Output is correct - 200005 tokens
26	Correct	0 ms	17320 KB	Output is correct - 405 tokens
27	Correct	798 ms	19240 KB	Output is correct - 105 tokens
28	Correct	1679 ms	180520 KB	Output is correct - 50005 tokens
29	Correct	1925 ms	98600 KB	Output is correct - 50005 tokens
30	Correct	1954 ms	98600 KB	Output is correct - 50005 tokens
31	Correct	1752 ms	180520 KB	Output is correct - 200005 tokens
32	Correct	0 ms	17000 KB	Output is correct - 8 tokens

Subtask #6
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	177 ms	19240 KB	Output is correct - 105 tokens
2	Correct	168 ms	19240 KB	Output is correct - 105 tokens
3	Correct	178 ms	19240 KB	Output is correct - 105 tokens
4	Correct	184 ms	19240 KB	Output is correct - 105 tokens
5	Correct	181 ms	19240 KB	Output is correct - 105 tokens
6	Correct	0 ms	180520 KB	Output is correct - 1005 tokens
7	Correct	42 ms	180520 KB	Output is correct - 1005 tokens
8	Correct	0 ms	180520 KB	Output is correct - 1005 tokens
9	Correct	69 ms	180520 KB	Output is correct - 100005 tokens
10	Correct	12 ms	180520 KB	Output is correct - 505 tokens
11	Correct	11 ms	180520 KB	Output is correct - 505 tokens
12	Correct	84 ms	180520 KB	Output is correct - 200005 tokens
13	Correct	21 ms	180520 KB	Output is correct - 505 tokens
14	Correct	12 ms	180520 KB	Output is correct - 505 tokens
15	Correct	2571 ms	180520 KB	Output is correct - 11 tokens
16	Correct	6877 ms	180520 KB	Output is correct - 200005 tokens
17	Correct	0 ms	17000 KB	Output is correct - 6 tokens
18	Correct	0 ms	17000 KB	Output is correct - 6 tokens
19	Correct	0 ms	17000 KB	Output is correct - 6 tokens
20	Correct	0 ms	17320 KB	Output is correct - 405 tokens
21	Correct	2 ms	17320 KB	Output is correct - 405 tokens
22	Correct	0 ms	17320 KB	Output is correct - 405 tokens
23	Correct	0 ms	17320 KB	Output is correct - 405 tokens
24	Correct	0 ms	17320 KB	Output is correct - 366 tokens
25	Correct	0 ms	17320 KB	Output is correct - 405 tokens
26	Correct	0 ms	17320 KB	Output is correct - 366 tokens
27	Correct	52 ms	17320 KB	Output is correct - 200005 tokens
28	Correct	0 ms	17320 KB	Output is correct - 405 tokens
29	Correct	799 ms	19240 KB	Output is correct - 105 tokens
30	Correct	1736 ms	180520 KB	Output is correct - 50005 tokens
31	Correct	6328 ms	180520 KB	Output is correct - 100005 tokens
32	Correct	6349 ms	180520 KB	Output is correct - 100005 tokens
33	Correct	1857 ms	98600 KB	Output is correct - 50005 tokens
34	Correct	7262 ms	98600 KB	Output is correct - 100005 tokens
35	Correct	1993 ms	98600 KB	Output is correct - 50005 tokens
36	Correct	7330 ms	98600 KB	Output is correct - 100005 tokens
37	Correct	1705 ms	180520 KB	Output is correct - 200005 tokens
38	Correct	6446 ms	180520 KB	Output is correct - 200005 tokens
39	Correct	0 ms	17000 KB	Output is correct - 8 tokens
40	Correct	7631 ms	98600 KB	Output is correct - 100005 tokens

답안 #16754

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 12.0 / 12.0

Subtask #3 16.0 / 16.0

Subtask #4 18.0 / 18.0

Subtask #5 21.0 / 21.0

Subtask #6 24.0 / 24.0

Subtask #1
9.0 / 9.0

Subtask #2
12.0 / 12.0

Subtask #3
16.0 / 16.0

Subtask #4
18.0 / 18.0

Subtask #5
21.0 / 21.0

Subtask #6
24.0 / 24.0