oj.uz

Submission #227329

# Submission time Handle Problem Language Result Execution time Memory
227329 2020-04-27T01:32:52 Z kig9981 Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 182428 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "wombats.h"
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;
 
const int B=10, SZ=1<<9;
int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], P[200][200], md[SZ], D[200], D2[200];
 
void set_md(int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(s==e) return;
	set_md(2*bit,s,m);
	set_md(2*bit+1,m+1,e);
	md[bit]=min((m+1)*B-1,N-1);
}
 
int get_cost(int h, int s, int e)
{
	if(s>e) swap(s,e);
	return PS[h][e]-PS[h][s];
}
 
void dnc(int h, int s1, int e1, int s2, int e2)
{
	int m2=(s2+e2)>>1, m=s1;
	if(s2>e2) return;
	for(int i=s1+1;i<=e1;i++) if(D[i]+get_cost(h,i,m2)<D[m]+get_cost(h,m,m2)) m=i;
	D2[m2]=D[m]+get_cost(h,m,m2);
	dnc(h,s1,m,s2,m2-1);
	dnc(h,m,e1,m2+1,e2);
}
 
void dijk(int b)
{
	for(int r=0;r<M;r++) {
		for(int i=0;i<B && b*B+i<N;i++) {
			if(i) {
				for(int j=0;j<M;j++) D[j]=D2[j]+V[b*B+i-1][j];
			}
			else {
				for(int j=0;j<M;j++) D[j]=(r!=j)*0x3fffffff;
			}
			dnc(b*B+i,0,M-1,0,M-1);
		}
		for(int j=0;j<M;j++) tree[SZ+b][r][j]=D2[j];
	}
}
 
void combine(int p, int l, int r)
{
	for(int i=0;i<M;i++) {
		P[i][i]=0;
		for(int j=1;j<M;j++) if(tree[l][i][P[i][i]]+V[md[p]][P[i][i]]+tree[r][P[i][i]][i]>=tree[l][i][j]+V[md[p]][j]+tree[r][j][i]) P[i][i]=j;
		tree[p][i][i]=tree[l][i][P[i][i]]+V[md[p]][P[i][i]]+tree[r][P[i][i]][i];
	}
	for(int i=1;i<M;i++) for(int j=0;j+i<M;j++) {
		P[j][j+i]=P[j][j+i-1];
		P[j+i][j]=P[j+i-1][j];
		for(int k=P[j][j+i-1]+1;k<=P[j+1][j+i];k++) if(tree[l][j][P[j][j+i]]+V[md[p]][P[j][j+i]]+tree[r][P[j][j+i]][j+i]>=tree[l][j][k]+V[md[p]][k]+tree[r][k][j+i]) P[j][j+i]=k;
		for(int k=P[j+i-1][j]+1;k<=P[j+i][j+1];k++) if(tree[l][j+i][P[j+i][j]]+V[md[p]][P[j+i][j]]+tree[r][P[j+i][j]][j]>=tree[l][j+i][k]+V[md[p]][k]+tree[r][k][j]) P[j+i][j]=k;
		tree[p][j][j+i]=tree[l][j][P[j][j+i]]+V[md[p]][P[j][j+i]]+tree[r][P[j][j+i]][j+i];
		tree[p][j+i][j]=tree[l][j+i][P[j+i][j]]+V[md[p]][P[j+i][j]]+tree[r][P[j+i][j]][j];
	}
}
 
void init(int R, int C, int (*H)[200], int (*V)[200])
{
	N=R; M=C; memset(tree,0x3f,sizeof(tree));
	for(int i=0;i<N;i++) for(int j=0;j<M-1;j++) {
		::H[i][j]=H[i][j];
		PS[i][j+1]=PS[i][j]+H[i][j];
	}
	for(int i=0;i<N-1;i++) for(int j=0;j<M;j++) ::V[i][j]=V[i][j];
	for(int i=0;i<SZ;i++) {
		if(i*B<N) dijk(i);
		else for(int j=0;j<M;j++) tree[SZ+i][j][j]=0;
	}
	set_md();
	for(int i=SZ;--i;) combine(i,2*i,2*i+1);
}
 
void changeH(int P, int Q, int W)
{
    H[P][Q]=W;
	for(int j=0;j<M-1;j++) PS[P][j+1]=PS[P][j]+H[P][j];
	dijk(P/B);
	for(int n=SZ+P/B;n>>=1;) combine(n,2*n,2*n+1);
}
 
void changeV(int P, int Q, int W)
{
    V[P][Q]=W;
	if(P/B==(P+1)/B) dijk(P/B);
	for(int n=SZ+P/B;n>>=1;) combine(n,2*n,2*n+1);
}
 
int escape(int V1, int V2)
{
	return tree[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]
  int res;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 168440 KB Output is correct
2 Correct 95 ms 168440 KB Output is correct
3 Correct 166 ms 170232 KB Output is correct
4 Correct 90 ms 168568 KB Output is correct
5 Correct 88 ms 168608 KB Output is correct
6 Correct 79 ms 160632 KB Output is correct
7 Correct 81 ms 160632 KB Output is correct
8 Correct 80 ms 160632 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 160632 KB Output is correct
2 Correct 85 ms 160632 KB Output is correct
3 Correct 80 ms 160632 KB Output is correct
4 Correct 83 ms 160760 KB Output is correct
5 Correct 84 ms 160764 KB Output is correct
6 Correct 85 ms 160764 KB Output is correct
7 Correct 82 ms 160760 KB Output is correct
8 Correct 82 ms 160760 KB Output is correct
9 Correct 85 ms 160632 KB Output is correct
10 Correct 84 ms 160760 KB Output is correct
11 Correct 167 ms 162072 KB Output is correct
12 Correct 83 ms 160760 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 694 ms 161176 KB Output is correct
2 Correct 650 ms 161272 KB Output is correct
3 Correct 741 ms 161272 KB Output is correct
4 Correct 703 ms 161144 KB Output is correct
5 Correct 718 ms 161272 KB Output is correct
6 Correct 79 ms 160632 KB Output is correct
7 Correct 81 ms 160632 KB Output is correct
8 Correct 86 ms 160760 KB Output is correct
9 Correct 2661 ms 161272 KB Output is correct
10 Correct 94 ms 160632 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 180220 KB Output is correct
2 Correct 93 ms 180192 KB Output is correct
3 Correct 93 ms 180216 KB Output is correct
4 Correct 133 ms 181112 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 161144 KB Output is correct
2 Correct 646 ms 161272 KB Output is correct
3 Correct 747 ms 161272 KB Output is correct
4 Correct 704 ms 161268 KB Output is correct
5 Correct 710 ms 161272 KB Output is correct
6 Correct 92 ms 180216 KB Output is correct
7 Correct 90 ms 180216 KB Output is correct
8 Correct 91 ms 180216 KB Output is correct
9 Correct 139 ms 181368 KB Output is correct
10 Correct 86 ms 168544 KB Output is correct
11 Correct 84 ms 168440 KB Output is correct
12 Correct 168 ms 170360 KB Output is correct
13 Correct 94 ms 168440 KB Output is correct
14 Correct 88 ms 168568 KB Output is correct
15 Correct 81 ms 160632 KB Output is correct
16 Correct 81 ms 160632 KB Output is correct
17 Correct 77 ms 160632 KB Output is correct
18 Correct 92 ms 160788 KB Output is correct
19 Correct 89 ms 161016 KB Output is correct
20 Correct 85 ms 160760 KB Output is correct
21 Correct 84 ms 160760 KB Output is correct
22 Correct 82 ms 160764 KB Output is correct
23 Correct 84 ms 160760 KB Output is correct
24 Correct 81 ms 160760 KB Output is correct
25 Correct 173 ms 162040 KB Output is correct
26 Correct 85 ms 160760 KB Output is correct
27 Correct 2618 ms 161144 KB Output is correct
28 Correct 4484 ms 180984 KB Output is correct
29 Correct 4532 ms 177528 KB Output is correct
30 Correct 4533 ms 177444 KB Output is correct
31 Correct 4567 ms 182008 KB Output is correct
32 Correct 79 ms 160632 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 161144 KB Output is correct
2 Correct 664 ms 161144 KB Output is correct
3 Correct 743 ms 161400 KB Output is correct
4 Correct 701 ms 161304 KB Output is correct
5 Correct 724 ms 161268 KB Output is correct
6 Correct 91 ms 180216 KB Output is correct
7 Correct 92 ms 180216 KB Output is correct
8 Correct 92 ms 180216 KB Output is correct
9 Correct 132 ms 181112 KB Output is correct
10 Correct 84 ms 168568 KB Output is correct
11 Correct 85 ms 168444 KB Output is correct
12 Correct 172 ms 170232 KB Output is correct
13 Correct 85 ms 168568 KB Output is correct
14 Correct 83 ms 168568 KB Output is correct
15 Correct 9451 ms 180504 KB Output is correct
16 Execution timed out 20106 ms 182428 KB Time limit exceeded
17 Halted 0 ms 0 KB -