oj.uz

Submission #108196

# Submission time Handle Problem Language Result Execution time Memory
108196 2019-04-28T03:24:43 Z ihdignite Wombats (IOI13_wombats) C++14
100 / 100
 3395 ms 174124 KB 
#pragma GCC optimize("O3")
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

const int r=5e3, c=200, bs=10, bc=r/bs, sts=1024;
int h[r][c-1], v[r][c], st[sts][c][c], o[c+1];

void upd(int l1, int r1, int i=1, int l2=0, int r2=bc-1) {
	if(l2==r2) {
		memset(st[i], 0x3f, sizeof(st[i]));
		for(int j=0; j<c; ++j) {
			st[i][j][j]=0;
			for(int k=l2*bs; k<(l2+1)*bs; ++k) {
				for(int l=1; l<c; ++l)
					st[i][j][l]=min(st[i][j][l-1]+h[k][l-1], st[i][j][l]);
				for(int l=c-1; l; --l)
					st[i][j][l-1]=min(st[i][j][l]+h[k][l-1], st[i][j][l-1]);
				for(int l=0; l<c; ++l)
					st[i][j][l]+=v[k][l];
			}
		}
		return;
	}
	int m2=(l2+r2)/2;
	if(l1<=m2)
		upd(l1, r1, 2*i, l2, m2);
	if(m2<r1)
		upd(l1, r1, 2*i+1, m2+1, r2);
	memset(o, 0, 4*c);
	for(int j1=0; j1<c; ++j1) {
		for(int j2=c-1; ~j2; --j2) {
			array<int, 2> d{INT_MAX, 0};
			for(int k=o[j2]; k<=o[j2+1]; ++k)
				d=min(array<int, 2>{st[2*i][j1][k]+st[2*i+1][k][j2], -k}, d);
			st[i][j1][j2]=d[0];
			o[j2]=-d[1];
		}
	}
}

void init(int r, int c, int h[5000][200], int v[5000][200]) {
	memset(::h, 0x3f, sizeof(::h));
	for(int i=0; i<r; ++i)
		for(int j=0; j<c-1; ++j)
			::h[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];
	o[::c]=::c-1;
	upd(0, bc-1);
}

void changeH(int p, int q, int w) {
	h[p][q]=w;
	upd(p/bs, p/bs);
}

void changeV(int p, int q, int w) {
	v[p][q]=w;
	upd(p/bs, p/bs);
}

int escape(int a, int b) {
	return st[1][a][b];
}

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 upd(int, int, int, int, int)':
wombats.cpp:66:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 }
 ^
wombats.cpp:66:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:66:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:9:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 void upd(int l1, int r1, int i=1, int l2=0, int r2=bc-1) {
      ^~~
wombats.cpp:9:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:9:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2860 ms 168596 KB Output is correct
2 Correct 2804 ms 168616 KB Output is correct
3 Correct 2965 ms 170184 KB Output is correct
4 Correct 2769 ms 168588 KB Output is correct
5 Correct 2628 ms 168568 KB Output is correct
6 Correct 780 ms 160748 KB Output is correct
7 Correct 840 ms 160760 KB Output is correct
8 Correct 870 ms 160808 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 895 ms 160876 KB Output is correct
2 Correct 803 ms 160760 KB Output is correct
3 Correct 745 ms 160792 KB Output is correct
4 Correct 785 ms 160804 KB Output is correct
5 Correct 804 ms 160832 KB Output is correct
6 Correct 779 ms 160800 KB Output is correct
7 Correct 801 ms 160772 KB Output is correct
8 Correct 733 ms 160760 KB Output is correct
9 Correct 805 ms 160776 KB Output is correct
10 Correct 731 ms 160840 KB Output is correct
11 Correct 939 ms 161744 KB Output is correct
12 Correct 795 ms 160876 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1260 ms 161120 KB Output is correct
2 Correct 1256 ms 161144 KB Output is correct
3 Correct 1218 ms 161024 KB Output is correct
4 Correct 1269 ms 161024 KB Output is correct
5 Correct 1296 ms 161024 KB Output is correct
6 Correct 879 ms 160696 KB Output is correct
7 Correct 807 ms 160860 KB Output is correct
8 Correct 867 ms 160776 KB Output is correct
9 Correct 2971 ms 161044 KB Output is correct
10 Correct 764 ms 160744 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2705 ms 172480 KB Output is correct
2 Correct 2922 ms 172548 KB Output is correct
3 Correct 2985 ms 172580 KB Output is correct
4 Correct 2855 ms 173368 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1294 ms 161016 KB Output is correct
2 Correct 1169 ms 161252 KB Output is correct
3 Correct 1135 ms 161112 KB Output is correct
4 Correct 1093 ms 160888 KB Output is correct
5 Correct 1408 ms 161140 KB Output is correct
6 Correct 2917 ms 172596 KB Output is correct
7 Correct 2920 ms 172584 KB Output is correct
8 Correct 2919 ms 172468 KB Output is correct
9 Correct 3068 ms 173312 KB Output is correct
10 Correct 2922 ms 168592 KB Output is correct
11 Correct 2652 ms 168572 KB Output is correct
12 Correct 2847 ms 170096 KB Output is correct
13 Correct 2906 ms 168572 KB Output is correct
14 Correct 2991 ms 168548 KB Output is correct
15 Correct 878 ms 160628 KB Output is correct
16 Correct 824 ms 160688 KB Output is correct
17 Correct 858 ms 160640 KB Output is correct
18 Correct 872 ms 160772 KB Output is correct
19 Correct 904 ms 160736 KB Output is correct
20 Correct 939 ms 160772 KB Output is correct
21 Correct 942 ms 160800 KB Output is correct
22 Correct 892 ms 160808 KB Output is correct
23 Correct 889 ms 160736 KB Output is correct
24 Correct 820 ms 160812 KB Output is correct
25 Correct 799 ms 161756 KB Output is correct
26 Correct 793 ms 160760 KB Output is correct
27 Correct 3050 ms 160976 KB Output is correct
28 Correct 3025 ms 172996 KB Output is correct
29 Correct 2960 ms 170760 KB Output is correct
30 Correct 3227 ms 170800 KB Output is correct
31 Correct 3070 ms 173852 KB Output is correct
32 Correct 882 ms 160900 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1284 ms 160952 KB Output is correct
2 Correct 1132 ms 160928 KB Output is correct
3 Correct 1313 ms 161008 KB Output is correct
4 Correct 1302 ms 161012 KB Output is correct
5 Correct 1391 ms 160984 KB Output is correct
6 Correct 3014 ms 172460 KB Output is correct
7 Correct 3115 ms 172460 KB Output is correct
8 Correct 2990 ms 172460 KB Output is correct
9 Correct 2740 ms 173336 KB Output is correct
10 Correct 2921 ms 168500 KB Output is correct
11 Correct 2976 ms 168444 KB Output is correct
12 Correct 2597 ms 170084 KB Output is correct
13 Correct 2592 ms 168652 KB Output is correct
14 Correct 2781 ms 168556 KB Output is correct
15 Correct 1092 ms 172488 KB Output is correct
16 Correct 3248 ms 174124 KB Output is correct
17 Correct 864 ms 160760 KB Output is correct
18 Correct 939 ms 160744 KB Output is correct
19 Correct 764 ms 160620 KB Output is correct
20 Correct 768 ms 160888 KB Output is correct
21 Correct 777 ms 160760 KB Output is correct
22 Correct 778 ms 160792 KB Output is correct
23 Correct 712 ms 160884 KB Output is correct
24 Correct 770 ms 160784 KB Output is correct
25 Correct 801 ms 160824 KB Output is correct
26 Correct 841 ms 160760 KB Output is correct
27 Correct 859 ms 161768 KB Output is correct
28 Correct 840 ms 160880 KB Output is correct
29 Correct 2638 ms 160984 KB Output is correct
30 Correct 3305 ms 172968 KB Output is correct
31 Correct 2663 ms 173244 KB Output is correct
32 Correct 2779 ms 173188 KB Output is correct
33 Correct 2692 ms 170940 KB Output is correct
34 Correct 2999 ms 171344 KB Output is correct
35 Correct 2807 ms 170788 KB Output is correct
36 Correct 3395 ms 171212 KB Output is correct
37 Correct 3330 ms 173816 KB Output is correct
38 Correct 2754 ms 173868 KB Output is correct
39 Correct 814 ms 160808 KB Output is correct
40 Correct 3273 ms 171168 KB Output is correct