oj.uz

Submission #227193

# Submission time Handle Problem Language Result Execution time Memory
227193 2020-04-26T12:50:28 Z kig9981 Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 20932 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=1000;
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 15 ms 8192 KB Output is correct
2 Correct 15 ms 8192 KB Output is correct
3 Correct 111 ms 9848 KB Output is correct
4 Correct 15 ms 8192 KB Output is correct
5 Correct 14 ms 8192 KB Output is correct
6 Correct 4 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 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 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 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 158 ms 1400 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4887 ms 992 KB Output is correct
2 Correct 4051 ms 868 KB Output is correct
3 Correct 5040 ms 892 KB Output is correct
4 Correct 5114 ms 888 KB Output is correct
5 Correct 4905 ms 892 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 19998 ms 888 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 45 ms 19968 KB Output is correct
2 Correct 42 ms 19960 KB Output is correct
3 Correct 46 ms 19968 KB Output is correct
4 Correct 104 ms 20696 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4883 ms 872 KB Output is correct
2 Correct 3996 ms 976 KB Output is correct
3 Correct 4973 ms 884 KB Output is correct
4 Correct 4935 ms 876 KB Output is correct
5 Correct 4818 ms 888 KB Output is correct
6 Correct 46 ms 19968 KB Output is correct
7 Correct 42 ms 19960 KB Output is correct
8 Correct 46 ms 19960 KB Output is correct
9 Correct 103 ms 20728 KB Output is correct
10 Correct 14 ms 8192 KB Output is correct
11 Correct 15 ms 8320 KB Output is correct
12 Correct 108 ms 9848 KB Output is correct
13 Correct 14 ms 8192 KB Output is correct
14 Correct 15 ms 8192 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 4 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 512 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 512 KB Output is correct
25 Correct 159 ms 1400 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 19827 ms 876 KB Output is correct
28 Execution timed out 20083 ms 20504 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4933 ms 896 KB Output is correct
2 Correct 3984 ms 992 KB Output is correct
3 Correct 4986 ms 768 KB Output is correct
4 Correct 4936 ms 992 KB Output is correct
5 Correct 4806 ms 888 KB Output is correct
6 Correct 45 ms 19956 KB Output is correct
7 Correct 41 ms 19960 KB Output is correct
8 Correct 45 ms 19960 KB Output is correct
9 Correct 100 ms 20728 KB Output is correct
10 Correct 15 ms 8192 KB Output is correct
11 Correct 15 ms 8192 KB Output is correct
12 Correct 111 ms 9848 KB Output is correct
13 Correct 15 ms 8192 KB Output is correct
14 Correct 16 ms 8192 KB Output is correct
15 Incorrect 16145 ms 20932 KB Output isn't correct
16 Halted 0 ms 0 KB -