oj.uz

Submission #98088

# Submission time Handle Problem Language Result Execution time Memory
98088 2019-02-20T15:32:07 Z tincamatei Wombats (IOI13_wombats) C++14
12 / 100
 86 ms 16252 KB 
    #include "wombats.h"
    #include <bits/stdc++.h>
     
    using namespace std;
     
    const int MAX_C = 20;
    const int MAX_R = 20;
    const int INF = 1000000000;
     
    int R, C;
    int H[MAX_R][MAX_C], V[MAX_R][MAX_C];
    int sp[MAX_R][MAX_C];
    int a[MAX_C][MAX_C];
     
    struct Matrix {
    	int dp[MAX_C][MAX_C];
    	Matrix() {
    		for(int i = 0; i < MAX_C; ++i)
    			for(int j = 0; j < MAX_C; ++j)
    				dp[i][j] = INF;
    	}
     
    	Matrix operator* (const Matrix &x) const {
    		Matrix rez;
    		for(int i = 0; i < C; ++i) {
    			for(int j = 0; j < C; ++j) {
    				int dist = dp[i][j] + x.dp[j][i];
    				if(dist < rez.dp[i][i]) {
    					rez.dp[i][i] = dist;
    					a[i][i] = j;
    				}
    			}
    		}
     
    		for(int d = 1; d < C; ++d) {
    			for(int i = 0; i < C - d; ++i) {
    				int j = i + d;
    				int st, dr;
    				st = a[i][j - 1];
    				dr = a[i + 1][j];
    				for(int k = st; k <= dr; ++k) {
    					int dist = dp[i][k] + x.dp[k][j];
    					if(dist < rez.dp[i][j]) {
    						rez.dp[i][j] = dist;
    						a[i][j] = k;
    					}
    				}
    			}
     
    			for(int i = d; i < C; ++i) {
    				int j = i - d;
    				int st, dr;
    				st = a[i - 1][j];
    				dr = a[i][j + 1];
    				for(int k = st; k <= dr; ++k) {
    					int dist = dp[i][k] + x.dp[k][j];
    					if(dist < rez.dp[i][j]) {
    						rez.dp[i][j] = dist;
    						a[i][j] = k;
    					}
    				}
    			}
    		}
    		return rez;
    	}
    } dp[MAX_R];
     
    Matrix rez;
     
    void initrez() {
    	for(int i = 0; i < C; ++i)
    		for(int j = 0; j < C; ++j)
    			if(i == j)
    				rez.dp[i][j] = 0;
    			else
    				rez.dp[i][j] = INF;
    }
     
    void initrow(Matrix &x, int r) {
    	for(int i = 0; i < C; ++i)
    		for(int j = 0; j < C; ++j)
    			x.dp[i][j] = abs(sp[r][i] - sp[r][j]) + V[r][j];
    }
     
    void calcrez() {
    	initrez();
    	for(int i = 0; i < R; ++i)
    		rez = rez * dp[i];
    }
     
    void init(int _R, int _C, int _H[5000][200], int _V[5000][200]) {
    	R = _R;
    	C = _C;
    	for(int i = 0; i < R; ++i)
    		for(int j = 0; j < C; ++j) {
    			H[i][j] = _H[i][j];
    			V[i][j] = _V[i][j];
    		}
     
    	for(int i = 0; i < R; ++i) {
    		sp[i][0] = 0;
    		for(int j = 1; j < C; ++j)
    			sp[i][j] = sp[i][j - 1] + H[i][j - 1];
    	}
     
    	for(int i = 0; i < R; ++i)
    		initrow(dp[i], i);
     
    	calcrez();
    }
     
    void changeH(int P, int Q, int W) {
    	H[P][Q] = W;
    	for(int i = 1; i < C; ++i)
    		sp[P][i] = sp[P][i - 1] + H[P][i - 1];
    	initrow(dp[P], P);
    	calcrez();
    }
     
    void changeV(int P, int Q, int W) {
    	V[P][Q] = W;
    	initrow(dp[P], P);
    	calcrez();
    }
     
    int escape(int V1, int V2) {
    	return rez.dp[V1][V2];
    }

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;
      ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 8448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 16252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -