oj.uz

Submission #108197

# Submission time Handle Problem Language Result Execution time Memory
108197 2019-04-28T03:25:56 Z ihdignite Wombats (IOI13_wombats) C++14
100 / 100
 3432 ms 174268 KB 
#pragma GCC optimize("Ofast")
#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 3034 ms 168556 KB Output is correct
2 Correct 3106 ms 168552 KB Output is correct
3 Correct 2804 ms 170028 KB Output is correct
4 Correct 2796 ms 168676 KB Output is correct
5 Correct 2881 ms 168596 KB Output is correct
6 Correct 776 ms 160700 KB Output is correct
7 Correct 852 ms 160692 KB Output is correct
8 Correct 868 ms 160888 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 928 ms 160820 KB Output is correct
2 Correct 758 ms 160732 KB Output is correct
3 Correct 881 ms 160780 KB Output is correct
4 Correct 866 ms 160812 KB Output is correct
5 Correct 825 ms 160900 KB Output is correct
6 Correct 860 ms 160720 KB Output is correct
7 Correct 878 ms 160900 KB Output is correct
8 Correct 889 ms 160740 KB Output is correct
9 Correct 880 ms 160668 KB Output is correct
10 Correct 824 ms 160768 KB Output is correct
11 Correct 911 ms 161816 KB Output is correct
12 Correct 836 ms 160752 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1272 ms 161156 KB Output is correct
2 Correct 1289 ms 161256 KB Output is correct
3 Correct 1284 ms 160940 KB Output is correct
4 Correct 1240 ms 161008 KB Output is correct
5 Correct 1409 ms 161016 KB Output is correct
6 Correct 770 ms 160792 KB Output is correct
7 Correct 851 ms 160656 KB Output is correct
8 Correct 710 ms 160612 KB Output is correct
9 Correct 3112 ms 160980 KB Output is correct
10 Correct 883 ms 160708 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3201 ms 172464 KB Output is correct
2 Correct 2961 ms 172468 KB Output is correct
3 Correct 3237 ms 172520 KB Output is correct
4 Correct 2911 ms 173484 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1431 ms 161012 KB Output is correct
2 Correct 1235 ms 161088 KB Output is correct
3 Correct 1335 ms 161056 KB Output is correct
4 Correct 1421 ms 161116 KB Output is correct
5 Correct 1213 ms 161016 KB Output is correct
6 Correct 2771 ms 172468 KB Output is correct
7 Correct 3007 ms 172484 KB Output is correct
8 Correct 3129 ms 172440 KB Output is correct
9 Correct 2782 ms 173212 KB Output is correct
10 Correct 2608 ms 168628 KB Output is correct
11 Correct 2626 ms 168548 KB Output is correct
12 Correct 2863 ms 170092 KB Output is correct
13 Correct 2923 ms 168560 KB Output is correct
14 Correct 2643 ms 168704 KB Output is correct
15 Correct 800 ms 160732 KB Output is correct
16 Correct 761 ms 160728 KB Output is correct
17 Correct 738 ms 160724 KB Output is correct
18 Correct 842 ms 160840 KB Output is correct
19 Correct 851 ms 160728 KB Output is correct
20 Correct 763 ms 160764 KB Output is correct
21 Correct 758 ms 160668 KB Output is correct
22 Correct 734 ms 160884 KB Output is correct
23 Correct 796 ms 160732 KB Output is correct
24 Correct 842 ms 160860 KB Output is correct
25 Correct 960 ms 161892 KB Output is correct
26 Correct 937 ms 160744 KB Output is correct
27 Correct 2849 ms 161016 KB Output is correct
28 Correct 2966 ms 172872 KB Output is correct
29 Correct 2755 ms 170940 KB Output is correct
30 Correct 2733 ms 170716 KB Output is correct
31 Correct 3120 ms 173872 KB Output is correct
32 Correct 817 ms 160760 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1282 ms 161144 KB Output is correct
2 Correct 1182 ms 160996 KB Output is correct
3 Correct 1173 ms 160968 KB Output is correct
4 Correct 1330 ms 160984 KB Output is correct
5 Correct 1306 ms 161056 KB Output is correct
6 Correct 2687 ms 172464 KB Output is correct
7 Correct 2910 ms 172520 KB Output is correct
8 Correct 2687 ms 172540 KB Output is correct
9 Correct 2767 ms 173364 KB Output is correct
10 Correct 3270 ms 168692 KB Output is correct
11 Correct 2876 ms 168568 KB Output is correct
12 Correct 3014 ms 170096 KB Output is correct
13 Correct 2959 ms 168712 KB Output is correct
14 Correct 2931 ms 168824 KB Output is correct
15 Correct 968 ms 172440 KB Output is correct
16 Correct 3417 ms 174268 KB Output is correct
17 Correct 835 ms 160760 KB Output is correct
18 Correct 861 ms 160948 KB Output is correct
19 Correct 821 ms 160744 KB Output is correct
20 Correct 806 ms 161004 KB Output is correct
21 Correct 829 ms 160852 KB Output is correct
22 Correct 875 ms 160868 KB Output is correct
23 Correct 838 ms 160832 KB Output is correct
24 Correct 768 ms 160708 KB Output is correct
25 Correct 834 ms 160768 KB Output is correct
26 Correct 797 ms 160712 KB Output is correct
27 Correct 906 ms 161708 KB Output is correct
28 Correct 763 ms 160752 KB Output is correct
29 Correct 2730 ms 161012 KB Output is correct
30 Correct 2781 ms 172840 KB Output is correct
31 Correct 2610 ms 173304 KB Output is correct
32 Correct 2887 ms 173392 KB Output is correct
33 Correct 3024 ms 170968 KB Output is correct
34 Correct 2927 ms 171308 KB Output is correct
35 Correct 2726 ms 170736 KB Output is correct
36 Correct 3248 ms 171200 KB Output is correct
37 Correct 2788 ms 174016 KB Output is correct
38 Correct 2687 ms 174008 KB Output is correct
39 Correct 874 ms 160740 KB Output is correct
40 Correct 3432 ms 171052 KB Output is correct