oj.uz

Submission #164367

# Submission time Handle Problem Language Result Execution time Memory
164367 2019-11-19T16:06:43 Z costle Wombats (IOI13_wombats) C++17
100 / 100
 4330 ms 183416 KB 
#include "wombats.h"
 
#include <stdio.h>
#include <algorithm>
#define INF 1e9
#define ele (1<<9)
#define R 5000
#define C 200
#define BS 10
#define BN R/BS
using namespace std;
int H[R][C-1],V[R][C];
int sgt[ele<<1][C][C],p[C+1];
void update_(int xs,int xe,int w,int l,int r){
	if(l==r){
		for(int i=0;i<C;i++){
            for(int j=0;j<C;j++) sgt[w][i][j]=INF;
		}
		for(int i=0;i<C;i++){
			sgt[w][i][i]=0;
			for(int j=l*BS;j<(l+1)*BS;j++){
				for(int k=1;k<C;k++) sgt[w][i][k]=min(sgt[w][i][k-1]+H[j][k-1],sgt[w][i][k]);
				for(int k=C-1;k;k--) sgt[w][i][k-1]=min(sgt[w][i][k]+H[j][k-1],sgt[w][i][k-1]);
				for(int k=0;k<C;k++) sgt[w][i][k]+=V[j][k];
			}
		}
		return;
	}
	int m=(l+r)>>1;
	if(xs<=m) update_(xs,xe,w<<1,l,m);
	if(m<xe) update_(xs,xe,w<<1|1,m+1,r);
	for(int i=0;i<C;i++) p[i]=0;
	for(int i=0;i<C;i++){
		for(int j=C-1;j>=0;j--){
			int mn=INF,mni=0;
			for(int k=p[j];k<=p[j+1];k++){
                if(mn>=sgt[w<<1][i][k]+sgt[w<<1|1][k][j]) mn=sgt[w<<1][i][k]+sgt[w<<1|1][k][j],mni=k;
			}
			sgt[w][i][j]=mn,p[j]=mni;
		}
	}
}
void init(int r, int c, int h[5000][200], int v[5000][200]) {
    for(int i=0;i<R;i++){
        for(int j=0;j<C-1;j++) H[i][j]=INF;
    }
    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];
    }
	p[C]=C-1;
	update_(0,BN-1,1,0,BN-1);
}
 
void changeH(int a, int b, int c) {
	H[a][b]=c;
	update_(a/BS,a/BS,1,0,BN-1);
}
 
void changeV(int a, int b, int c) {
	V[a][b]=c;
	update_(a/BS,a/BS,1,0,BN-1);
}
 
int escape(int a, int b) {
	return sgt[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 update_(int, int, int, int, int)':
wombats.cpp:69:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 }
 ^
wombats.cpp:69:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:69:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:14:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 void update_(int xs,int xe,int w,int l,int r){
      ^~~~~~~
wombats.cpp:14:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:14: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 3685 ms 168528 KB Output is correct
2 Correct 3711 ms 168696 KB Output is correct
3 Correct 3842 ms 171312 KB Output is correct
4 Correct 3760 ms 168464 KB Output is correct
5 Correct 3667 ms 168552 KB Output is correct
6 Correct 1407 ms 160632 KB Output is correct
7 Correct 1417 ms 160804 KB Output is correct
8 Correct 1388 ms 160784 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1381 ms 160824 KB Output is correct
2 Correct 1388 ms 160860 KB Output is correct
3 Correct 1387 ms 160880 KB Output is correct
4 Correct 1412 ms 160992 KB Output is correct
5 Correct 1387 ms 160820 KB Output is correct
6 Correct 1396 ms 160760 KB Output is correct
7 Correct 1385 ms 160800 KB Output is correct
8 Correct 1381 ms 160820 KB Output is correct
9 Correct 1498 ms 160760 KB Output is correct
10 Correct 1387 ms 160984 KB Output is correct
11 Correct 1468 ms 163236 KB Output is correct
12 Correct 1434 ms 160832 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1841 ms 161124 KB Output is correct
2 Correct 1826 ms 161144 KB Output is correct
3 Correct 1833 ms 161144 KB Output is correct
4 Correct 1833 ms 161016 KB Output is correct
5 Correct 1840 ms 161016 KB Output is correct
6 Correct 1384 ms 160752 KB Output is correct
7 Correct 1380 ms 160928 KB Output is correct
8 Correct 1388 ms 160664 KB Output is correct
9 Correct 3617 ms 161128 KB Output is correct
10 Correct 1392 ms 160756 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3641 ms 172440 KB Output is correct
2 Correct 3703 ms 172536 KB Output is correct
3 Correct 3716 ms 172596 KB Output is correct
4 Correct 3750 ms 173892 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1904 ms 160944 KB Output is correct
2 Correct 1840 ms 161048 KB Output is correct
3 Correct 1839 ms 161104 KB Output is correct
4 Correct 1889 ms 161100 KB Output is correct
5 Correct 1842 ms 161144 KB Output is correct
6 Correct 3673 ms 172596 KB Output is correct
7 Correct 3679 ms 172484 KB Output is correct
8 Correct 3771 ms 172548 KB Output is correct
9 Correct 3719 ms 174104 KB Output is correct
10 Correct 3740 ms 168696 KB Output is correct
11 Correct 3768 ms 168716 KB Output is correct
12 Correct 3783 ms 171384 KB Output is correct
13 Correct 3751 ms 168748 KB Output is correct
14 Correct 3699 ms 168632 KB Output is correct
15 Correct 1452 ms 160792 KB Output is correct
16 Correct 1380 ms 160760 KB Output is correct
17 Correct 1451 ms 160632 KB Output is correct
18 Correct 1435 ms 160760 KB Output is correct
19 Correct 1383 ms 160888 KB Output is correct
20 Correct 1384 ms 160756 KB Output is correct
21 Correct 1381 ms 160724 KB Output is correct
22 Correct 1394 ms 160868 KB Output is correct
23 Correct 1385 ms 160880 KB Output is correct
24 Correct 1390 ms 160888 KB Output is correct
25 Correct 1623 ms 163244 KB Output is correct
26 Correct 1380 ms 160760 KB Output is correct
27 Correct 3613 ms 160892 KB Output is correct
28 Correct 3834 ms 176760 KB Output is correct
29 Correct 3879 ms 174400 KB Output is correct
30 Correct 3884 ms 174328 KB Output is correct
31 Correct 3834 ms 178400 KB Output is correct
32 Correct 1445 ms 160744 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1831 ms 161012 KB Output is correct
2 Correct 1847 ms 161252 KB Output is correct
3 Correct 2001 ms 161144 KB Output is correct
4 Correct 1837 ms 161160 KB Output is correct
5 Correct 1837 ms 160964 KB Output is correct
6 Correct 3679 ms 172720 KB Output is correct
7 Correct 3671 ms 172716 KB Output is correct
8 Correct 3783 ms 172576 KB Output is correct
9 Correct 3876 ms 173944 KB Output is correct
10 Correct 3641 ms 168484 KB Output is correct
11 Correct 4131 ms 168520 KB Output is correct
12 Correct 3786 ms 171356 KB Output is correct
13 Correct 3771 ms 168696 KB Output is correct
14 Correct 3679 ms 168632 KB Output is correct
15 Correct 1620 ms 182416 KB Output is correct
16 Correct 4187 ms 183416 KB Output is correct
17 Correct 1380 ms 160760 KB Output is correct
18 Correct 1510 ms 160760 KB Output is correct
19 Correct 1381 ms 160708 KB Output is correct
20 Correct 1383 ms 160744 KB Output is correct
21 Correct 1376 ms 160764 KB Output is correct
22 Correct 1386 ms 160756 KB Output is correct
23 Correct 1386 ms 160776 KB Output is correct
24 Correct 1391 ms 160760 KB Output is correct
25 Correct 1384 ms 160816 KB Output is correct
26 Correct 1392 ms 160776 KB Output is correct
27 Correct 1463 ms 163184 KB Output is correct
28 Correct 1387 ms 160888 KB Output is correct
29 Correct 3677 ms 161016 KB Output is correct
30 Correct 3783 ms 176672 KB Output is correct
31 Correct 3853 ms 180984 KB Output is correct
32 Correct 3821 ms 180980 KB Output is correct
33 Correct 3863 ms 174504 KB Output is correct
34 Correct 4027 ms 178288 KB Output is correct
35 Correct 3905 ms 174460 KB Output is correct
36 Correct 4166 ms 178260 KB Output is correct
37 Correct 3863 ms 178296 KB Output is correct
38 Correct 3891 ms 181668 KB Output is correct
39 Correct 1396 ms 160888 KB Output is correct
40 Correct 4330 ms 178360 KB Output is correct