oj.uz

Submission #263274

# Submission time Handle Problem Language Result Execution time Memory
263274 2020-08-13T14:56:19 Z eohomegrownapps Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 9372 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;
int cache[5000][5000];
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    /* ... */
    h=H;v=V;
    r=R;c=C;
    for (int i = 0; i<c; i++){
    	cache[i][0]=-1;
    }
}

void changeH(int P, int Q, int W) {
    /* ... */
    h[P][Q]=W;
    for (int i = 0; i<c; i++){
    	cache[i][0]=-1;
    }
}

void changeV(int P, int Q, int W) {
    /* ... */
    v[P][Q]=W;
    for (int i = 0; i<c; i++){
    	cache[i][0]=-1;
    }
}

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

int escape(int vtop, int vbot) {
	if (cache[vtop][0]!=-1){
		return cache[vtop][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;
    }
    for (int x = 0; x<c; x++){
    	cache[vtop][x]=harr[!cur][x];
    }
    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 27 ms 4224 KB Output is correct
2 Correct 26 ms 4224 KB Output is correct
3 Correct 110 ms 5880 KB Output is correct
4 Correct 27 ms 4224 KB Output is correct
5 Correct 27 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 0 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 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 2 ms 544 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 488 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 87 ms 1400 KB Output is correct
12 Correct 1 ms 512 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 896 KB Output is correct
2 Correct 11 ms 896 KB Output is correct
3 Correct 12 ms 896 KB Output is correct
4 Correct 11 ms 896 KB Output is correct
5 Correct 13 ms 896 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
9 Correct 7 ms 896 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 8220 KB Output is correct
2 Correct 88 ms 8224 KB Output is correct
3 Correct 94 ms 8312 KB Output is correct
4 Correct 128 ms 8952 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 896 KB Output is correct
2 Correct 10 ms 896 KB Output is correct
3 Correct 12 ms 1152 KB Output is correct
4 Correct 11 ms 896 KB Output is correct
5 Correct 14 ms 896 KB Output is correct
6 Correct 86 ms 8192 KB Output is correct
7 Correct 90 ms 8192 KB Output is correct
8 Correct 92 ms 8192 KB Output is correct
9 Correct 129 ms 9208 KB Output is correct
10 Correct 26 ms 4224 KB Output is correct
11 Correct 26 ms 4224 KB Output is correct
12 Correct 110 ms 5880 KB Output is correct
13 Correct 26 ms 4224 KB Output is correct
14 Correct 26 ms 4224 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 1 ms 512 KB Output is correct
20 Correct 1 ms 512 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 86 ms 1400 KB Output is correct
26 Correct 1 ms 512 KB Output is correct
27 Correct 9 ms 896 KB Output is correct
28 Execution timed out 20015 ms 8812 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 896 KB Output is correct
2 Correct 16 ms 896 KB Output is correct
3 Correct 11 ms 896 KB Output is correct
4 Correct 12 ms 896 KB Output is correct
5 Correct 11 ms 896 KB Output is correct
6 Correct 91 ms 8212 KB Output is correct
7 Correct 90 ms 8192 KB Output is correct
8 Correct 89 ms 8344 KB Output is correct
9 Correct 132 ms 8952 KB Output is correct
10 Correct 28 ms 4224 KB Output is correct
11 Correct 27 ms 4224 KB Output is correct
12 Correct 109 ms 5880 KB Output is correct
13 Correct 27 ms 4224 KB Output is correct
14 Correct 27 ms 4224 KB Output is correct
15 Correct 323 ms 8960 KB Output is correct
16 Execution timed out 20029 ms 9372 KB Time limit exceeded
17 Halted 0 ms 0 KB -