oj.uz

Submission #263193

# Submission time Handle Problem Language Result Execution time Memory
263193 2020-08-13T13:58:43 Z vioalbert Coins (LMIO19_monetos) C++14
100 / 100
 158 ms 49016 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rng(time(NULL));

const int N = 305, NN = 65, INF = 1e7;
int t, n, k1, k2, scale = 5;
int grid[N][N], pref[N][N];
int memo[NN][NN][NN*NN/2], opt[NN][NN][NN*NN/2];
int best[NN];

int dp(int idx, int prv, int total) {
	if(total < 0) return INF;
	if(idx == 0 && prv == n) return (total == 0)?0:INF;
	if(memo[idx][prv][total] != -1) return memo[idx][prv][total];
	int &ret = memo[idx][prv][total] = INF;
	if(idx > 0) {
		int goUp = min(INF, dp(idx - 1, prv, total - prv) + pref[idx][prv]);
		if(goUp != INF && ret > goUp) {
			ret = goUp;
			opt[idx][prv][total] = 1;
		}
	}
	if(prv < n) {
		int goRight = dp(idx, prv + 1, total);
		if(goRight != INF && ret > goRight) {
			ret = goRight;
			opt[idx][prv][total] = 2;
		}
	}
	return ret;
}

void backtrack() {
	int idx = n, prv = 0, total = n*n/2;
	while(idx > 0 || prv < n) {
		if(opt[idx][prv][total] == 1) {
			best[idx] = prv;
			idx--;
			total -= prv;
		} else if(opt[idx][prv][total] == 2) {
			prv++;
		}
	}
}

void compress() {
	for(int j = 1; j <= n; j++)
		pref[0][j] = 0;
	for(int i = 1; i <= n; i++) {
		pref[i][0] = 0;
		for(int j = 1; j <= n; j++)
			pref[i][j] = grid[i][j] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
	}

	n /= scale;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			int ii = i*scale, jj = j*scale;
			grid[i][j] = pref[ii][jj] - pref[ii - scale][jj] - pref[ii][jj - scale] + pref[ii - scale][jj - scale];
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> t >> n >> k1 >> k2;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++)
			cin >> grid[i][j];
	}

	if(t <= 2) scale = 1;
	compress();
	for(int j = 1; j <= n; j++)
		pref[0][j] = 0;
	for(int i = 1; i <= n; i++) {
		pref[i][0] = 0;
		for(int j = 1; j <= n; j++)
			pref[i][j] = pref[i][j - 1] + grid[i][j];
	}

	memset(memo, -1, sizeof memo);
	int ans = dp(n, 0, n*n/2);
	backtrack();
	n *= scale;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			if(j <= best[(i + scale - 1) / scale] * scale) cout << 0 << " \n"[j == n];
			else cout << 1 << " \n"[j == n];
		}
	}

	return 0;
}

Compilation message

monetos.cpp: In function 'int main()':
monetos.cpp:84:6: warning: unused variable 'ans' [-Wunused-variable]
   84 |  int ans = dp(n, 0, n*n/2);
      |      ^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35576 KB K = 17
2 Correct 74 ms 43896 KB K = 576
3 Correct 146 ms 48888 KB K = 18657
4 Correct 142 ms 49016 KB K = 21839
5 Correct 147 ms 48888 KB K = 17169
6 Correct 141 ms 49016 KB K = 20873
7 Correct 146 ms 48944 KB K = 21477
8 Correct 144 ms 49016 KB K = 19614
9 Correct 158 ms 48888 KB K = 20777
10 Correct 142 ms 49016 KB K = 20150