oj.uz

Submission #227196

# Submission time Handle Problem Language Result Execution time Memory
227196 2020-04-26T12:55:50 Z kig9981 Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 21520 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=500;
int N, M, H[5000][200], PS[5000][200], V[5000][200], C[11][200][200], D[200], D2[200];
 
int get_cost(int h, int s, int e)
{
	if(s>e) swap(s,e);
	return PS[h][e]-PS[h][s];
}
 
void dnc2(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);
	dnc2(h,s1,m,s2,m2-1);
	dnc2(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;
			}
			dnc2(b*B+i,0,M-1,0,M-1);
		}
		for(int j=0;j<M;j++) C[b][r][j]=D2[j];
	}
}
 
void init(int R, int C, int (*H)[200], int (*V)[200])
{
	N=R; M=C;
	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*B<N;i++) dijk(i);
}
 
void changeH(int P, int Q, int W)
{
    H[P][Q]=W;
	for(int j=0;j<M;j++) PS[P][j+1]=PS[P][j]+H[P][j];
	dijk(P/B);
}
 
void changeV(int P, int Q, int W)
{
    V[P][Q]=W;
	if(P/B==(P+1)/B) dijk(P/B);
}
 
void dnc(int b, 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]+C[b][i][m2]<D[m]+C[b][m][m2]) m=i;
	D2[m2]=D[m]+C[b][m][m2];
	dnc(b,s1,m,s2,m2-1);
	dnc(b,m,e1,m2+1,e2);
}
 
int escape(int V1, int V2)
{
	for(int b=0;b*B<N;b++) {
		if(b) {
			for(int j=0;j<M;j++) D[j]=D2[j]+V[b*B-1][j];
		}
		else {
			for(int j=0;j<M;j++) D[j]=(V1!=j)*0x3fffffff;
		}
		dnc(b,0,M-1,0,M-1);
	}
	return D2[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 12 ms 8192 KB Output is correct
2 Correct 12 ms 8192 KB Output is correct
3 Correct 121 ms 9936 KB Output is correct
4 Correct 13 ms 8192 KB Output is correct
5 Correct 13 ms 8192 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 166 ms 1532 KB Output is correct
12 Correct 5 ms 512 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4893 ms 972 KB Output is correct
2 Correct 3989 ms 1024 KB Output is correct
3 Correct 4953 ms 880 KB Output is correct
4 Correct 4955 ms 880 KB Output is correct
5 Correct 4791 ms 888 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 19963 ms 872 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 19968 KB Output is correct
2 Correct 29 ms 19968 KB Output is correct
3 Correct 31 ms 19968 KB Output is correct
4 Correct 107 ms 20856 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4935 ms 996 KB Output is correct
2 Correct 4048 ms 888 KB Output is correct
3 Correct 4980 ms 888 KB Output is correct
4 Correct 4998 ms 880 KB Output is correct
5 Correct 4884 ms 888 KB Output is correct
6 Correct 34 ms 19968 KB Output is correct
7 Correct 32 ms 19968 KB Output is correct
8 Correct 31 ms 19968 KB Output is correct
9 Correct 100 ms 20728 KB Output is correct
10 Correct 12 ms 8192 KB Output is correct
11 Correct 12 ms 8192 KB Output is correct
12 Correct 125 ms 9848 KB Output is correct
13 Correct 13 ms 8192 KB Output is correct
14 Correct 13 ms 8192 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 512 KB Output is correct
19 Correct 5 ms 512 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 512 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 165 ms 1528 KB Output is correct
26 Correct 6 ms 512 KB Output is correct
27 Execution timed out 20073 ms 768 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5118 ms 1008 KB Output is correct
2 Correct 4154 ms 768 KB Output is correct
3 Correct 5072 ms 880 KB Output is correct
4 Correct 4963 ms 880 KB Output is correct
5 Correct 4864 ms 888 KB Output is correct
6 Correct 32 ms 19968 KB Output is correct
7 Correct 40 ms 19968 KB Output is correct
8 Correct 31 ms 19968 KB Output is correct
9 Correct 102 ms 20728 KB Output is correct
10 Correct 12 ms 8192 KB Output is correct
11 Correct 12 ms 8192 KB Output is correct
12 Correct 140 ms 9848 KB Output is correct
13 Correct 16 ms 8192 KB Output is correct
14 Correct 16 ms 8192 KB Output is correct
15 Incorrect 12673 ms 21520 KB Output isn't correct
16 Halted 0 ms 0 KB -