oj.uz

Submission #64737

# Submission time Handle Problem Language Result Execution time Memory
64737 2018-08-05T13:29:13 Z mhnd Wombats (IOI13_wombats) C++14
55 / 100
 10784 ms 263168 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N = 1e5+50;
const ll oo = 1e18;
const ll mod = 1e9+7;

int dp[201][5001][201],h[5010][210],v[5010][210],c,r;

void build(){
	for(int x = 0;x<c;x++){
		for(int i=0;i<c;i++)dp[x][r-1][i]=1e9;
		dp[x][r-1][x]=0;
	    for(int i=r-2;i>=0;i--)
	    	for(int j=0;j<c;j++)
	    		dp[x][i][j] = dp[x][i+1][j] + v[i][j];
		for(int i=r-1;i>=0;i--){
		    for(int j=0;j<c;j++){
		    	if(i!=r-1)dp[x][i][j] = min(dp[x][i][j],dp[x][i+1][j]+v[i][j]);
		    	if(j)dp[x][i][j] = min(dp[x][i][j],dp[x][i][j-1] + h[i][j-1]);
		    	if(j < c-1)dp[x][i][j] = min(dp[x][i][j],dp[x][i][j+1]+h[i][j]);
		    }
		    for(int j=c-1;j>=0;j--){
		    	if(i!=r-1)dp[x][i][j] = min(dp[x][i][j],dp[x][i+1][j]+v[i][j]);
		    	if(j)dp[x][i][j] = min(dp[x][i][j],dp[x][i][j-1] + h[i][j-1]);
		    	if(j < c-1)dp[x][i][j] = min(dp[x][i][j],dp[x][i][j+1]+h[i][j]);
		    }
		    for(int j=0;j<c;j++){
		    	if(i!=r-1)dp[x][i][j] = min(dp[x][i][j],dp[x][i+1][j]+v[i][j]);
		    	if(j)dp[x][i][j] = min(dp[x][i][j],dp[x][i][j-1] + h[i][j-1]);
		    	if(j < c-1)dp[x][i][j] = min(dp[x][i][j],dp[x][i][j+1]+h[i][j]);
		    }
		}
	}
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	r=R;
	c=C;
	for(int i=0;i<5000;i++)
		for(int j=0;j<200;j++){
			h[i][j]=H[i][j];
			v[i][j]=V[i][j];
		}
	build();
}

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

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

int escape(int V1, int V2) {
	if(dp[V2][0][V1] == 1e9)return 0;
    return dp[V2][0][V1];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
wombats.cpp: In function 'void build()':
wombats.cpp:18:6: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
      for(int i=r-2;i>=0;i--)
      ^~~
wombats.cpp:21:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int i=r-1;i>=0;i--){
   ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 16376 KB Output is correct
2 Correct 87 ms 16640 KB Output is correct
3 Correct 172 ms 18204 KB Output is correct
4 Correct 115 ms 18204 KB Output is correct
5 Correct 113 ms 18204 KB Output is correct
6 Correct 13 ms 18204 KB Output is correct
7 Correct 12 ms 18204 KB Output is correct
8 Correct 12 ms 18204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 18204 KB Output is correct
2 Correct 12 ms 18204 KB Output is correct
3 Correct 13 ms 18204 KB Output is correct
4 Correct 14 ms 18204 KB Output is correct
5 Correct 16 ms 18204 KB Output is correct
6 Correct 15 ms 18204 KB Output is correct
7 Correct 16 ms 18204 KB Output is correct
8 Correct 14 ms 18204 KB Output is correct
9 Correct 12 ms 18204 KB Output is correct
10 Correct 15 ms 18204 KB Output is correct
11 Correct 159 ms 18204 KB Output is correct
12 Correct 14 ms 18204 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2171 ms 18204 KB Output is correct
2 Correct 2238 ms 18204 KB Output is correct
3 Correct 2125 ms 18204 KB Output is correct
4 Correct 1997 ms 18204 KB Output is correct
5 Correct 1917 ms 18204 KB Output is correct
6 Correct 10 ms 18204 KB Output is correct
7 Correct 13 ms 18204 KB Output is correct
8 Correct 11 ms 18204 KB Output is correct
9 Correct 9732 ms 18204 KB Output is correct
10 Correct 13 ms 18204 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 24960 KB Output is correct
2 Correct 273 ms 25084 KB Output is correct
3 Correct 372 ms 25276 KB Output is correct
4 Correct 444 ms 26640 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2031 ms 26640 KB Output is correct
2 Correct 1949 ms 26640 KB Output is correct
3 Correct 2058 ms 26640 KB Output is correct
4 Correct 2021 ms 26640 KB Output is correct
5 Correct 1962 ms 26640 KB Output is correct
6 Correct 267 ms 26640 KB Output is correct
7 Correct 288 ms 26640 KB Output is correct
8 Correct 270 ms 26640 KB Output is correct
9 Correct 347 ms 27988 KB Output is correct
10 Correct 86 ms 27988 KB Output is correct
11 Correct 84 ms 27988 KB Output is correct
12 Correct 184 ms 27988 KB Output is correct
13 Correct 81 ms 27988 KB Output is correct
14 Correct 85 ms 27988 KB Output is correct
15 Correct 13 ms 27988 KB Output is correct
16 Correct 12 ms 27988 KB Output is correct
17 Correct 14 ms 27988 KB Output is correct
18 Correct 13 ms 27988 KB Output is correct
19 Correct 15 ms 27988 KB Output is correct
20 Correct 15 ms 27988 KB Output is correct
21 Correct 16 ms 27988 KB Output is correct
22 Correct 14 ms 27988 KB Output is correct
23 Correct 16 ms 27988 KB Output is correct
24 Correct 13 ms 27988 KB Output is correct
25 Correct 108 ms 27988 KB Output is correct
26 Correct 14 ms 27988 KB Output is correct
27 Correct 10535 ms 27988 KB Output is correct
28 Execution timed out 10784 ms 263168 KB Time limit exceeded (wall clock)
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2005 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -