Submission #28665

#	Time	Username	Problem	Language	Result	Execution time	Memory
28665		not good but never sad (#68)	Test Data Creation (FXCUP2_testdata)	C++98	0 / 1	3 ms	4376 KiB

testdata

#include <stdio.h>
#include <algorithm>
using namespace std;

int N, M, S[400][601], T[300*300];
int S1[400][601], S2[400][601];
bool ans[303*303];

void upd(int s[400][601], int i, int k, int t)
{
	i %= 400;
	if (s[i][k] == -1 || s[i][k] > t){
		s[i][k] = t;
	}
}

void go(int i1, int k1, int i2, int k2)
{
	ans[i1] = ans[i1+k1-300] = ans[i2] = ans[i2+k2-300] = 1;
	if (i1 == i2 && k1 == k2) return;

	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=0;i<400;i++) for (int k=0;k<=600;k++) S1[i][k] = -1;
	S1[i1][k1] = T[i1] + (k1 != 300 ? T[i1+k1] : 0);
	for (int i=i1;i<=r1;i++){
		int xp = i / M, yp = i % M;
		for (int k=0;k<=600;k++){
			int &s = S1[i%400][k];
			if (s != -1){
				if (k >= 300){
					if (xp + 1 < N) upd(S1, i+M, k-M, s+(k-M!=300?T[i+M]:0));
					if (yp + 1 < M) upd(S1, i+1, k-1, s+(k-1!=300?T[i+1]:0));
				}
				else{
					int xq = (i + k - 300) / N, yq = (i + k - 300) % N;
					if (xq + 1 < M) upd(S1, i, k+N, s+(k+N!=300?T[i+k+N-300]:0));
					if (yq + 1 < N) upd(S1, i, k+1, s+(k+1!=300?T[i+k+1-300]:0));
				}
			}
			S1[(i+350)%400][k] = -1;
		}
	}

	for (int i=0;i<400;i++) for (int k=0;k<=600;k++) S2[i][k] = -1;
	S2[i2][k2] = T[i2] + (k2 != 300 ? T[i2+k2] : 0);
	for (int i=i2;i>=l2;i--){
		int xp = i / M, yp = i % M;
		for (int k=600;k>=0;k--){
			int &s = S2[i%400][k];
			if (s != -1){
				if (xp > 0 && k + M >= 300) upd(S2, i-M, k+M, s+(k+M!=300?T[i-M]:0));
				if (yp > 0 && k + 1 >= 300) upd(S2, i-1, k+1, s+(k+1!=300?T[i-1]:0));

				int xq = (i + k - 300) / N, yq = (i + k - 300) % N;
				if (xq > 0 && k - N < 300) upd(S2, i, k-N, s+(k-N!=300?T[i+k-N-300]:0));
				if (yq > 0 && k - 1 < 300) upd(S2, i, k-1, s+(k-1!=300?T[i+k-1-300]:0));
			}
			S2[(i+50)%400][k] = -1;
		}
	}

	int ci, ck, mx = 0x7fffffff;
	for (int i=l2;i<=r1;i++){
		for (int k=0;k<=600;k++) if (S1[i%400][k] != -1 && S2[i%400][k] != -1){
			if (i == i1 && k == k1) continue;
			if (i == i2 && k == k2) continue;
			int sum = S1[i%400][k] + S2[i%400][k] - T[i] - (k != 300 ? T[i] : 0);
			if (mx > sum){
				ci = i; ck = k;
				mx = sum;
			}
		}
	}
	if (mx == 0x7fffffff) return;
	go(i1,k1,ci,ck);
	go(ci,ck,i2,k2);
}

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

	S[0][300] = T[0];
	int tp;
	for (int i=0;i<N*M;i++){
		int xp = i / M, yp = i % M;
		for (int k=0;k<=600;k++){
			int &s = S[i%400][k];
			if (i == N*M-1 && k == 300) tp = s;
			if (s != -1){
				if (k >= 300){
					if (xp + 1 < N) upd(S, i+M, k-M, s+(k-M!=300?T[i+M]:0));
					if (yp + 1 < M) upd(S, i+1, k-1, s+(k-1!=300?T[i+1]:0));
				}
				else{
					int xq = (i + k - 300) / N, yq = (i + k - 300) % N;
					if (xq + 1 < M) upd(S, i, k+N, s+(k+N!=300?T[i+k+N-300]:0));
					if (yq + 1 < N) upd(S, i, k+1, s+(k+1!=300?T[i+k+1-300]:0));
				}
				s = -1;
			}
		}
	}

	printf("%d\n", tp);
	go(0,300,N*M-1,300);

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

	return 0;
}

Compilation message (stderr)

testdata.cpp: In function 'int main()':
testdata.cpp:85:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &M, &N);
                        ^
testdata.cpp:86:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=0;i<N*M;i++) scanf("%d", &T[i]);
                                            ^
testdata.cpp: In function 'void go(int, int, int, int)':
testdata.cpp:20:21: warning: 'ck' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (i1 == i2 && k1 == k2) return;
                     ^
testdata.cpp:19:18: warning: 'ci' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ans[i1] = ans[i1+k1-300] = ans[i2] = ans[i2+k2-300] = 1;
                  ^

• Subtask 1: 0 / 1