oj.uz

Submission #538294

# Submission time Handle Problem Language Result Execution time Memory
538294 2022-03-16T14:10:01 Z hmm789 Popeala (CEOI16_popeala) C++14
17 / 100
 53 ms 1364 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	#define int long long 
	int n, t, s;
	cin >> n >> t >> s;
	int pts[t+1], dp[s][t], last[n], best[n+1], ac[t];
	pts[0] = 0;
	for(int i = 1; i <= t; i++) {
		cin >> pts[i];
		pts[i] += pts[i-1];
	}
	string score[n];
	for(int i = 0; i < n; i++) cin >> score[i];
	bool died[n];
	memset(died, 0, sizeof(died));
	for(int i = 0; i < t; i++) {
		for(int j = 0; j < n; j++) if(score[j][i] == '0') died[j] = 1;
		dp[0][i] = 0;
		for(int j = 0; j < n; j++) if(!died[j]) dp[0][i] += pts[i+1];
	}
	for(int i = 1; i < s; i++) {
		for(int j = 0; j < n; j++) best[j] = 0, last[j] = 0;
		best[n] = 0;
		for(int j = 0; j < t; j++) {
			ac[j] = n;
			if(dp[i-1][best[n]] + (pts[j+1]-pts[best[n]])*n > dp[i-1][j-1] + (pts[j+1]-pts[j])*n)
				best[n] = j-1;
			for(int k = 0; k < n; k++) {
				if(score[k][j] == '0') {
					for(int l = last[k]+1; l <= j; l++) best[ac[l]] = 0;
					for(int l = last[k]+1; l <= j; l++) {
						ac[l]--;
						if(dp[i-1][best[ac[l]]] + (pts[j+1]-pts[best[ac[l]]])*ac[l] > dp[i-1][l-1] + (pts[j+1]-pts[l])*ac[l])
							best[ac[l]] = l-1;
					}
					last[k] = j;
				}
			}
			dp[i][j] = 1e18;
			if(i > j) continue;
			for(int k = 0; k <= n; k++) {
				dp[i][j] = min(dp[i][j], dp[i-1][best[k]] + (pts[j+1]-pts[best[k]+1])*ac[best[k]+1]);
			}
		}
	}
	for(int i = 0; i < s; i++) cout << dp[i][t-1] << '\n';
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 580 KB Output is correct
2 Correct 11 ms 576 KB Output is correct
3 Correct 12 ms 468 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 1364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 13 ms 580 KB Output is correct
4 Correct 11 ms 576 KB Output is correct
5 Correct 12 ms 468 KB Output is correct
6 Incorrect 53 ms 1364 KB Output isn't correct
7 Halted 0 ms 0 KB -