oj.uz

Submission #263252

# Submission time Handle Problem Language Result Execution time Memory
263252 2020-08-13T14:42:12 Z eohomegrownapps Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 18040 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

int (*h)[200];
int (*v)[200];

int r,c; //r: height c: width
int INF = 1e9;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    /* ... */
    h=H;v=V;
    r=R;c=C;
}

void changeH(int P, int Q, int W) {
    /* ... */
    h[P][Q]=W;
}

void changeV(int P, int Q, int W) {
    /* ... */
    v[P][Q]=W;
}

int harr[2][5000];
int prefsum[5000];

int escape(int vtop, int vbot) {
    for (int i = 0; i<c; i++){
    	harr[0][i]=INF;
    }
    harr[0][vtop]=0;
    bool cur = 1;
    for (int y = 1; y<=r; y++){
    	//process row h[y-1][x] and v[y-1][x]
    	prefsum[0]=0;
    	for (int x = 0; x<c-1; x++){
    		prefsum[x+1]=prefsum[x]+h[y-1][x];
    	}
    	int minval = INF;
    	for (int x = c-1; x>=0; x--){
    		int vert = (y==r)?0:v[y-1][x];
    		//cout<<prefsum[x]<<' ';
    		minval=min(minval,prefsum[x]+harr[!cur][x]);
    		harr[cur][x]=minval-prefsum[x]+vert;
    	}//cout<<'\n';
    	
    	prefsum[c-1]=0;
    	for (int x = c-2; x>=0; x--){
    		prefsum[x]=prefsum[x+1]+h[y-1][x];
    	}
    	minval = INF;
    	for (int x = 0; x<c; x++){
    		int vert = (y==r)?0:v[y-1][x];
    		minval=min(minval,prefsum[x]+harr[!cur][x]);
    		harr[cur][x]=min(harr[cur][x],minval-prefsum[x]+vert);
    	}
    	/*for (int i = 0; i<c; i++){
    		cout<<harr[cur][i]<<' ';
    	}cout<<'\n';*/
    	cur=!cur;
    }
    return harr[!cur][vbot];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4224 KB Output is correct
2 Correct 26 ms 4224 KB Output is correct
3 Correct 9405 ms 7424 KB Output is correct
4 Correct 27 ms 4224 KB Output is correct
5 Correct 26 ms 4224 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 691 ms 2808 KB Output is correct
12 Correct 2 ms 416 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 512 KB Output is correct
2 Correct 10 ms 512 KB Output is correct
3 Correct 11 ms 512 KB Output is correct
4 Correct 11 ms 512 KB Output is correct
5 Correct 13 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 13 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 8312 KB Output is correct
2 Correct 86 ms 8192 KB Output is correct
3 Correct 90 ms 8192 KB Output is correct
4 Correct 8205 ms 9796 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 512 KB Output is correct
2 Correct 11 ms 512 KB Output is correct
3 Correct 11 ms 620 KB Output is correct
4 Correct 11 ms 640 KB Output is correct
5 Correct 11 ms 512 KB Output is correct
6 Correct 89 ms 8268 KB Output is correct
7 Correct 89 ms 8192 KB Output is correct
8 Correct 96 ms 8268 KB Output is correct
9 Correct 8471 ms 9636 KB Output is correct
10 Correct 26 ms 4224 KB Output is correct
11 Correct 28 ms 4332 KB Output is correct
12 Correct 9763 ms 7108 KB Output is correct
13 Correct 26 ms 4224 KB Output is correct
14 Correct 41 ms 4328 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 412 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 707 ms 2808 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 11 ms 512 KB Output is correct
28 Execution timed out 20036 ms 11824 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 512 KB Output is correct
2 Correct 12 ms 512 KB Output is correct
3 Correct 11 ms 512 KB Output is correct
4 Correct 11 ms 640 KB Output is correct
5 Correct 11 ms 512 KB Output is correct
6 Correct 100 ms 8344 KB Output is correct
7 Correct 94 ms 8192 KB Output is correct
8 Correct 89 ms 8312 KB Output is correct
9 Correct 8067 ms 9596 KB Output is correct
10 Correct 31 ms 4224 KB Output is correct
11 Correct 28 ms 4224 KB Output is correct
12 Correct 9423 ms 7092 KB Output is correct
13 Correct 27 ms 4224 KB Output is correct
14 Correct 26 ms 4224 KB Output is correct
15 Correct 290 ms 18040 KB Output is correct
16 Execution timed out 20066 ms 16028 KB Time limit exceeded
17 Halted 0 ms 0 KB -