Submission #538294

#	Time	Username	Problem	Language	Result	Execution time	Memory
538294		hmm789	Popeala (CEOI16_popeala)	C++14	17 / 100	53 ms	1364 KiB

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]])*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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74