Submission #140162

#	Time	Username	Problem	Language	Result	Execution time	Memory
140162		aminra	Popeala (CEOI16_popeala)	C++17	100 / 100	1090 ms	24316 KiB

popeala

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)55;
const int MAXT = (int)2e5 + 3;
const ll infint = (int)1e9 + 3;
const int MOD = (int)1e9 + 7;
const ll inf = (ll)1e18 + 3;
typedef long long lint;
typedef pair<lint, int> pli;
const int INF = 1 << 30;
const lint LINF = 1ll << 32; 
#define fi first
#define se second
int N, T, S;
int P[MAXT];
char R[MAXN][MAXT];
int sp[MAXT];
lint dp[MAXN][MAXT];
lint seg[MAXN][MAXT];
vector<int> wro[MAXN];
int ch[MAXT][MAXN];
 
int main() {
	ios::sync_with_stdio(false); cin.tie(0);
 
	cin >> N >> T >> S;
	for(int i = 1; i <= T; i++) cin >> P[i];
	for(int i = 0; i < N; i++) cin >> R[i];
 
	for(int i = 1; i <= T; i++) sp[i] = sp[i - 1] + P[i];
	for(int i = 0; i < N; i++) {
		wro[i].push_back(0);
		for(int j = 0; j < T; j++) if(R[i][j] == '0') wro[i].push_back(j + 1);
	}
	for(int i = 1; i <= S; i++) dp[i][0] = LINF;
	for(int i = 1; i <= T; i++) dp[0][i] = LINF;
	for(int j = 1; j <= T; j++) {
		for(int k = 0; k < N; k++) ch[j][k] = *prev(upper_bound(wro[k].begin(), wro[k].end(), j));
		ch[j][N] = 0;
		ch[j][N + 1] = j;
		sort(ch[j], ch[j] + N + 2);
	}
	for(int i = 1; i <= S; i++) {
		for(int j = 0; j <= N; j++) for(int k = 0; k < T; k++) seg[j][k] = dp[i - 1][k] - j * sp[k];
		for(int j = 1; j <= T; j++) dp[i][j] = LINF;
		for(int j = 0; j <= N; j++) {
			deque<pli> dq;
			ch[0][j + 1] = 0;
			for(int k = 1; k <= T; k++) {
				for(int l = ch[k - 1][j + 1]; l < ch[k][j + 1]; l++) {
					while(!dq.empty() && dq.back().fi > seg[j][l]) dq.pop_back();
					dq.push_back(make_pair(seg[j][l], l));
				}
				while(!dq.empty() && dq.front().se < ch[k][j]) dq.pop_front();
				if(!dq.empty()) dp[i][k] = min(dp[i][k], dq.front().fi + sp[k] * j);
			}
		}
	}
 
	for(int i = 1; i <= S; i++) cout << dp[i][T] << "\n";
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74