Submission #483756

#	Time	Username	Problem	Language	Result	Execution time	Memory
483756		minhcool	Popeala (CEOI16_popeala)	C++17	100 / 100	362 ms	19652 KiB

popeala

#include<bits/stdc++.h>

using namespace std; 

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define eb emplace_back
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 2e4 + 5, MAXN = 1e7 + 5;
 
const long long oo = 1e18 + 7, mod = 1e9 + 7;

int t, n, s, a[N];
int pref[N];
int nxt[55][N];
vector<int> vc[N];

int f[N], g[N], cnt[N];

int mx[N];

void process(){
	cin >> n >> t >> s;
	for(int i = 1; i <= t; i++) cin >> a[i];
	for(int i = 1; i <= t; i++) pref[i] = (pref[i - 1] + a[i]);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= t; j++){
			char x;
			cin >> x;
			if(x == '0') nxt[i][j] = j;
			else nxt[i][j] = oo; 
		}
		if(nxt[i][t] != oo) vc[nxt[i][t]].pb(t);
		for(int j = t - 1; j >= 1; j--){
			nxt[i][j] = min(nxt[i][j], nxt[i][j + 1]);
			if(nxt[i][j] != oo) vc[nxt[i][j]].pb(j);
		}
	}
	//for(int i = 1; i <= t; i++) sort(vc[i].begin(), vc[i].end());
	g[0] = 0;
	for(int i = 1; i <= t; i++) g[i] = -oo;
	//cout << pref[t] * n - g[t] << "\n";
	for(int i = 1; i <= s; i++){
		for(int j = 0; j <= t; j++) cnt[j] = 0;
		for(int j = 0; j <= t; j++){
			f[j] = g[j];
			g[j] = -oo;
		}
		for(int j = 0; j <= n; j++) mx[j] = -oo;
		for(int j = 1; j <= t; j++){
			mx[0] = max(mx[0], f[j - 1]);
			//cout << mx[0] << "\n";
			for(auto it : vc[j]){
				cnt[it]++;
				assert(cnt[it] <= n);
				mx[cnt[it]] = max(mx[cnt[it]], f[it - 1] - pref[it - 1] * cnt[it]);
				//mx = max(mx, f[it - 1] + cnt[it] *)
			}
			for(int k = 0; k <= n; k++) g[j] = max(g[j], mx[k] + pref[j] * k);
			//cout << i << " " << j << " " << g[j] << "\n";
		}
		//dnc(1, t, 0, t - 1);
		
		//for(int j = 0; j <= t; j++) cout << g[j] << " ";
		//cout << "\n";
		cout << pref[t] * n - g[t] << "\n";
	}
}
 
signed main(){
	ios_base::sync_with_stdio(0);

	#ifdef nqm
		freopen("input.inp", "r", stdin);
		freopen("output.out", "w", stdout);
	#endif
	#ifndef nqm
		
	#endif

	process();
}

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