oj.uz

Submission #28901

# Submission time Handle Problem Language Result Execution time Memory
28901 2017-07-17T14:20:27 Z kriii Test Data Creation (FXCUP2_testdata) C++14
1 / 1
 3779 ms 4844 KB 
#include <stdio.h>

int N,M,T[300*300];
bool ans[300*300];

const int non = 0x0f0f0f0f;
const int per = 700;
const int base = 300;
int S1[per][base*2+1];
int S2[per][base*2+1];

void upd(int s[per][base*2+1], int i, int k, int x)
{
	i %= per;
	if (s[i][k] > x)
		s[i][k] = x;
}

int go(int i1, int k1, int i2, int k2)
{
	if (i1 == i2 && k1 == k2) return T[i1+k1-base];
	int r1 = (i1 + i2) / 2 + 150;
	if (r1 >= i2) r1 = i2;
	int l2 = (i1 + i2) / 2 - 150;
	if (l2 <= i1) l2 = i1;

	for (int i=i1;i<=r1;i++) for (int k=0;k<=base*2;k++) S1[i%per][k] = non;
	S1[i1%per][k1] = T[i1] + (k1 != base ? T[i1+k1-base] : 0);
	for (int i=i1;i<=r1;i++){
		int px = i / M, py = i % M;
		for (int k=0;k<=base*2;k++){
			int &s = S1[i%per][k];
			if (s != non){
				if (k >= base){
					if (px + 1 < N) upd(S1,i+M,k-M,s+(k-M!=base?T[i+M]:0));
					if (py + 1 < M) upd(S1,i+1,k-1,s+(k-1!=base?T[i+1]:0));
				}
				else{
					int qx = (i + k - base) / N, qy = (i + k - base) % N;
					if (qx + 1 < M) upd(S1,i,k+N,s+(k+N!=base?T[i+k+N-base]:0));
					if (qy + 1 < N) upd(S1,i,k+1,s+(k+1!=base?T[i+k+1-base]:0));
				}
			}
			S1[(i+per/2)%per][k] = non;
		}
	}

	for (int i=l2;i<=i2;i++) for (int k=0;k<=base*2;k++) S2[i%per][k] = non;
	S2[i2%per][k2] = T[i2] + (k2 != base ? T[i2+k2-base] : 0);
	for (int i=i2;i>=l2;i--){
		int px = i / M, py = i % M;
		for (int k=base*2;k>=0;k--){
			int &s = S2[i%per][k];
			if (s != non){
				if (px > 0 && base <= k + M && k + M <= base*2) upd(S2,i-M,k+M,s+(k+M!=base?T[i-M]:0));
				if (py > 0 && base <= k + 1 && k + 1 <= base*2) upd(S2,i-1,k+1,s+(k+1!=base?T[i-1]:0));

				int qx = (i + k - base) / N, qy = (i + k - base) % N;
				if (qx > 0 && 0 <= k - N && k - N < base) upd(S2,i,k-N,s+T[i+k-N-base]);
				if (qy > 0 && 0 <= k - 1 && k - 1 < base) upd(S2,i,k-1,s+T[i+k-1-base]);
			}
			S2[(i+per/2)%per][k] = non;
		}
	}

	int mx = non, ci, ck;
	for (int i=l2;i<=r1;i++){
		for (int k=0;k<=base*2;k++){
			if (i == i1 && k == k1) continue;
			if (i == i2 && k == k2) continue;
			int now = S1[i%per][k] + S2[i%per][k];
			if (now >= non) continue;
			now -= T[i] + (k != base ? T[i+k-base] : 0);
			if (mx > now){
				mx = now;
				ci = i; ck = k;
			}
		}
	}

	if (mx == non) return 0;
	ans[ci] = ans[ci+ck-base] = 1;
	go(i1,k1,ci,ck);
	go(ci,ck,i2,k2);
	return mx;
}

int main()
{
	scanf ("%d %d",&M,&N);
	for (int i=0;i<M*N;i++) scanf ("%d",&T[i]);

	printf ("%d\n",go(0,base,N*M-1,base));
	ans[0] = ans[N*M-1] = 1;
	for (int i=0;i<M*N;i++) printf("%d%c",ans[i]?1:0,(i+1)%M==0?'\n':' ');

	return 0;
}

Compilation message

testdata.cpp: In function 'int main()':
testdata.cpp:90:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d",&M,&N);
                       ^
testdata.cpp:91:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=0;i<M*N;i++) scanf ("%d",&T[i]);
                                            ^
testdata.cpp: In function 'int go(int, int, int, int)':
testdata.cpp:84:17: warning: 'ck' may be used uninitialized in this function [-Wmaybe-uninitialized]
  go(ci,ck,i2,k2);
                 ^
testdata.cpp:84:17: warning: 'ci' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4844 KB Correct
2 Correct 0 ms 4844 KB Correct
3 Correct 43 ms 4844 KB Correct
4 Correct 189 ms 4844 KB Correct
5 Correct 973 ms 4844 KB Correct
6 Correct 3779 ms 4844 KB Correct
7 Correct 3603 ms 4844 KB Correct
8 Correct 513 ms 4844 KB Correct
9 Correct 539 ms 4844 KB Correct
10 Correct 0 ms 4844 KB Correct
11 Correct 66 ms 4844 KB Correct
12 Correct 109 ms 4844 KB Correct
13 Correct 99 ms 4844 KB Correct
14 Correct 186 ms 4844 KB Correct
15 Correct 309 ms 4844 KB Correct
16 Correct 596 ms 4844 KB Correct
17 Correct 1533 ms 4844 KB Correct
18 Correct 3616 ms 4844 KB Correct
19 Correct 179 ms 4844 KB Correct
20 Correct 2443 ms 4844 KB Correct
21 Correct 1886 ms 4844 KB Correct
22 Correct 1126 ms 4844 KB Correct
23 Correct 1463 ms 4844 KB Correct
24 Correct 3419 ms 4844 KB Correct
25 Correct 3439 ms 4844 KB Correct