Submission #538298

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
538298	2022-03-16T14:31:43 Z	hmm789	Popeala (CEOI16_popeala)	C++14	100 / 100	519 ms	10776 KB

popeala

#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]])*ac[best[n]+1] > 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]]+1])*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	0 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	468 KB	Output is correct
2	Correct	12 ms	544 KB	Output is correct
3	Correct	12 ms	468 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	51 ms	1236 KB	Output is correct
2	Correct	77 ms	1852 KB	Output is correct
3	Correct	96 ms	2408 KB	Output is correct

Subtask #4

74.0 / 74.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	13 ms	468 KB	Output is correct
4	Correct	12 ms	544 KB	Output is correct
5	Correct	12 ms	468 KB	Output is correct
6	Correct	51 ms	1236 KB	Output is correct
7	Correct	77 ms	1852 KB	Output is correct
8	Correct	96 ms	2408 KB	Output is correct
9	Correct	153 ms	3720 KB	Output is correct
10	Correct	217 ms	4720 KB	Output is correct
11	Correct	476 ms	10652 KB	Output is correct
12	Correct	502 ms	10776 KB	Output is correct
13	Correct	519 ms	10760 KB	Output is correct
14	Correct	511 ms	10772 KB	Output is correct
15	Correct	518 ms	10768 KB	Output is correct