oj.uz

Submission #31450

# Submission time Handle Problem Language Result Execution time Memory
31450 2017-08-27T10:58:32 Z jun6873 Wombats (IOI13_wombats) C++11
28 / 100
 20000 ms 28692 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

struct matrix {
	int a[202][202];
};

const int lim = 1;
int r, c, h[5004][204], v[5004][204], hs[5004][204], thr[204][204];
bool f[lim];
matrix m[lim], all;

void printmat(matrix k){
	for (int i=0; i<=c; i++) {
		for (int j=0; j<=c; j++) printf("%d ", k.a[i][j]);
		puts("");
	}
	puts("");
}

inline int hsum(int k, int x, int y) {
	if (x>y) swap(x, y);
	return x ? (hs[k][y] - hs[k][x]) : hs[k][y];
}

matrix sum(matrix &a, matrix &b, int k) {
	matrix ret;
	for (int i=0; i<=c; i++) thr[i][c-i+1] = c-1;
	for (int tog=0; tog<2; tog++) for (int j=c-1; j>=0; j--) for (int i=0; i+j<c; i++) {
		int mn = 2e9, mp = -1;
		int x = tog ? (i+j) : i, y = tog ? i : (i+j);
		for (int t=thr[j+1][i]; t<=thr[j+1][i+1]; t++) {
			int now = a.a[x][t] + v[k][t] + b.a[t][y];
			if (now <= mn) mn = now, mp = t;
		}
		if (tog) ret.a[i+j][i] = mn;
		else ret.a[i][i+j] = mn;
		thr[j][i+1] = mp;
	}
	return ret;
}

matrix base(int k) {
	matrix ret;
	for (int i=0; i<c; i++) for (int j=0; j<c; j++) ret.a[i][j] = hsum(k, i, j);
	return ret;
}

matrix get(int s, int e, int x, int all) {
	if (s==e) return base(s);
	if (!all and x<lim and f[x]) return m[x];
	int mid = (s+e)/2;
	if (x<lim) f[x] = 1;
	matrix l = get(s, mid, 2*x, all), r = get(mid+1, e, 2*x+1, all);
	matrix ret = sum(l, r, mid);
	if (x<lim) m[x] = ret;
	return ret;
}

matrix update(int s, int e, int x, int p) {
	if (s==e) return base(s);
	int k = (s+e)/2;
	if (p<=k) update(s, k, 2*x, p);
	else update(k+1, e, 2*x+1, p);
	if (x<lim) f[x] = 0;
	return get(s, e, x, 0);
}

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-1; j++) h[i][j] = H[i][j], hs[i][j+1] = hs[i][j] + h[i][j];
    for (int i=0; i<r-1; i++) for (int j=0; j<c; j++) v[i][j] = V[i][j];
    all = get(0, r-1, 1, 1);
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    for (int j=0; j<c-1; j++) hs[P][j+1] = hs[P][j] + h[P][j];
    all = update(0, r-1, 1, P);
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    all = update(0, r-1, 1, P);
}

int escape(int V1, int V2) {
    return all.a[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 Execution timed out 20000 ms 28684 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 22788 KB Output is correct
2 Correct 0 ms 22788 KB Output is correct
3 Correct 0 ms 22788 KB Output is correct
4 Correct 0 ms 24704 KB Output is correct
5 Correct 0 ms 24700 KB Output is correct
6 Correct 0 ms 24704 KB Output is correct
7 Correct 0 ms 24704 KB Output is correct
8 Correct 0 ms 24704 KB Output is correct
9 Correct 0 ms 24704 KB Output is correct
10 Correct 0 ms 24704 KB Output is correct
11 Correct 106 ms 24700 KB Output is correct
12 Correct 0 ms 24700 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3373 ms 25820 KB Output is correct
2 Correct 2723 ms 25820 KB Output is correct
3 Correct 3696 ms 25820 KB Output is correct
4 Correct 4113 ms 25816 KB Output is correct
5 Correct 3749 ms 25820 KB Output is correct
6 Correct 0 ms 22792 KB Output is correct
7 Correct 0 ms 22788 KB Output is correct
8 Correct 0 ms 22792 KB Output is correct
9 Correct 14663 ms 25816 KB Output is correct
10 Correct 0 ms 23428 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20000 ms 28684 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3583 ms 25816 KB Output is correct
2 Correct 2829 ms 25820 KB Output is correct
3 Correct 3676 ms 25816 KB Output is correct
4 Correct 3749 ms 25820 KB Output is correct
5 Correct 3953 ms 25820 KB Output is correct
6 Execution timed out 20000 ms 28692 KB Execution timed out
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3453 ms 25820 KB Output is correct
2 Correct 3119 ms 25820 KB Output is correct
3 Correct 3739 ms 25820 KB Output is correct
4 Correct 3639 ms 25820 KB Output is correct
5 Correct 4106 ms 25820 KB Output is correct
6 Execution timed out 20000 ms 28692 KB Execution timed out
7 Halted 0 ms 0 KB -