oj.uz

Submission #283483

# Submission time Handle Problem Language Result Execution time Memory
283483 2020-08-25T20:16:55 Z shayan_p Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 23036 KB 
// And you curse yourself for things you never done

#include<bits/stdc++.h>
#include "wombats.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 5010, maxm = 210, SQ = 5010, mod = 1e9 + 7, inf = 1e9 + 10;

int n, m;
int tmp[maxm][maxm], opt[maxm][maxm];

void knuth(int a[maxm][maxm], int b[maxm][maxm], int ans[maxm][maxm]){
    for(int i = 0; i < m; i++){
	for(int j = 0; j < m; j++)
	    tmp[i][j] = inf;
    }    
    for(int i = 0; i < m; i++){
	for(int j = 0; j < m; j++){
	    int x = a[i][j] + b[j][i];
	    if(x < tmp[i][i])
		opt[i][i] = j, tmp[i][i] = x;
	}
    }
    for(int ln = 1; ln < m; ln++){
	for(int i = 0; i < m; i++){
	    int j = i + ln;
	    for(int k = opt[i][j-1]; k <= opt[i+1][j]; k++){
		int x = a[i][k] + b[k][j];
		if(x < tmp[i][j])
		    opt[i][j] = k, tmp[i][j] = x;
	    }
	}
    }
    for(int ln = 1; ln < m; ln++){
	for(int i = ln; i < m; i++){
	    int j = i - ln;
	    for(int k = opt[i-1][j]; k <= opt[i][j+1]; k++){
		int x = a[i][k] + b[k][j];
		if(x < tmp[i][j])
		    opt[i][j] = k, tmp[i][j] = x;
	    }
	}
    }
    for(int i = 0; i < m; i++){
	for(int j = 0; j < m; j++)
	    ans[i][j] = tmp[i][j];
    }
}

int cx[maxn][maxm], cy[maxn][maxm];

int ds[4 * (maxn / SQ +1)][maxm][maxm];

int tmp2[maxm][maxm];

void restart(int l, int r, int ans[maxm][maxm]){
    for(int a = 0; a < m; a++){
	ans[a][a] = 0;
	for(int b = a+1; b < m; b++)
	    ans[a][b] = ans[a][b-1] + cy[l][b-1];
	for(int b = a-1; b >= 0; b--)
	    ans[a][b] = ans[a][b+1] + cy[l][b];
    }
    for(int w = l+1; w <= r; w++){
	for(int a = 0; a < m; a++){
	    tmp2[a][a] = cx[w-1][a];
	    for(int b = a+1; b < m; b++)
		tmp2[a][b] = tmp2[a][b-1] + cy[w][b-1];
	    for(int b = a-1; b >= 0; b--)
		tmp2[a][b] = tmp2[a][b+1] + cy[w][b];
	}
	knuth(ans, tmp2, ans);
    }
}
void build(int l = 0, int r = n, int id = 1){
    if(r-l <= SQ){
	restart(l, r, ds[id]);
	return;
    }
    int mid = (l+r) >> 1;
    build(l, mid, 2*id);
    build(mid, r, 2*id+1);
    knuth(ds[2*id], ds[2*id+1], ds[id]);
}
void change(int pos, int l = 0, int r = n, int id = 1){
    if(r < pos || pos < l)
	return;
    if(r-l <= SQ){
	restart(l, r, ds[id]);
	return;	    
    }
    int mid = (l+r) >> 1;
    change(pos, l, mid, 2*id);
    change(pos, mid, r, 2*id+1);
    knuth(ds[2*id], ds[2*id+1], ds[id]);
}
void init(int n, int m, int H[5000][200], int V[5000][200]){
    --n;
    ::n = n, ::m = m;
    for(int i = 0; i <= n; i++){
	for(int j = 0; j < m; j++)
	    cy[i][j] = H[i][j], cx[i][j] = V[i][j];
    }
    build();    
}
void changeH(int P, int Q, int W) {// Y
    cy[P][Q] = W;
    change(P);
}
void changeV(int P, int Q, int W){ // X
    cx[P][Q] = W;
    change(P);
}
int escape(int V1, int V2){
    return ds[1][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]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 12416 KB Output is correct
2 Correct 32 ms 12416 KB Output is correct
3 Correct 128 ms 14072 KB Output is correct
4 Correct 32 ms 12536 KB Output is correct
5 Correct 32 ms 12544 KB Output is correct
6 Correct 1 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 1 ms 384 KB Output is correct
3 Correct 0 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 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 89 ms 1528 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 1430 ms 1052 KB Output is correct
2 Correct 1006 ms 1144 KB Output is correct
3 Correct 1409 ms 1056 KB Output is correct
4 Correct 1405 ms 1056 KB Output is correct
5 Correct 1391 ms 1056 KB Output is correct
6 Correct 1 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 5507 ms 1024 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 101 ms 16440 KB Output is correct
2 Correct 85 ms 16384 KB Output is correct
3 Correct 108 ms 16384 KB Output is correct
4 Correct 143 ms 17144 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1398 ms 1144 KB Output is correct
2 Correct 973 ms 1144 KB Output is correct
3 Correct 1397 ms 1024 KB Output is correct
4 Correct 1391 ms 1144 KB Output is correct
5 Correct 1375 ms 1144 KB Output is correct
6 Correct 111 ms 16384 KB Output is correct
7 Correct 101 ms 16384 KB Output is correct
8 Correct 112 ms 16384 KB Output is correct
9 Correct 144 ms 17144 KB Output is correct
10 Correct 37 ms 12536 KB Output is correct
11 Correct 31 ms 12416 KB Output is correct
12 Correct 141 ms 14076 KB Output is correct
13 Correct 31 ms 12416 KB Output is correct
14 Correct 38 ms 12416 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 512 KB Output is correct
22 Correct 1 ms 512 KB Output is correct
23 Correct 1 ms 512 KB Output is correct
24 Correct 1 ms 512 KB Output is correct
25 Correct 89 ms 1528 KB Output is correct
26 Correct 1 ms 512 KB Output is correct
27 Correct 5497 ms 1052 KB Output is correct
28 Execution timed out 20096 ms 16760 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1370 ms 1024 KB Output is correct
2 Correct 977 ms 1152 KB Output is correct
3 Correct 1400 ms 1056 KB Output is correct
4 Correct 1391 ms 1024 KB Output is correct
5 Correct 1371 ms 1024 KB Output is correct
6 Correct 101 ms 16384 KB Output is correct
7 Correct 86 ms 16504 KB Output is correct
8 Correct 101 ms 16384 KB Output is correct
9 Correct 147 ms 17140 KB Output is correct
10 Correct 31 ms 12416 KB Output is correct
11 Correct 31 ms 12416 KB Output is correct
12 Correct 113 ms 14128 KB Output is correct
13 Correct 31 ms 12416 KB Output is correct
14 Correct 31 ms 12416 KB Output is correct
15 Correct 12186 ms 17016 KB Output is correct
16 Execution timed out 20098 ms 23036 KB Time limit exceeded
17 Halted 0 ms 0 KB -