Submission #9781

#	Time	Username	Problem	Language	Result	Execution time	Memory
9781		myungwoo	Solve another chuck (kriii2_S)	C++14	0 / 4	0 ms	1252 KiB

S

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

int N, M, K, C, all, zeros, X = 2e9;
bool V[10001];
vector <int> arr;

int main()
{
	int i, j, k;
	scanf("%d%d", &N, &M); K = N*M;
	for (i=1;i<=K;i++){
		scanf("%d", &k);
		if (k < 0) C++, k = -k;
		if (k) arr.push_back(k);
		else zeros++;
		all += k;
	}
	sort(arr.begin(), arr.end());
	queue <int> que;
	V[C] = 1; que.push(C);
	while (!que.empty()){
		int q = que.front(); que.pop();
		if (q >= N){
			if (!V[q-N]) V[q-N] = 1, que.push(q-N);
		}
		else{
			if (X > q) X = q;
			for (i=0;i<=zeros;i++) if (q+i <= N){
				int v = N-i-q;
				if (X > v) X = v;
			}
		}
		if (q >= M){
			if (!V[q-M]) V[q-M] = 1, que.push(q-M);
		}
		else{
			if (X > q) X = q;
			for (i=0;i<=zeros;i++) if (q+i <= M){
				int v = M-i-q;
				if (X > v) X = v;
			}
		}
	}
	int ans = all;
	for (i=0;i<X;i++) ans -= arr[i];
	printf("%d 0\n", ans);
}

• Subtask 1: 0 / 4