oj.uz

Submission #483756

# Submission time Handle Problem Language Result Execution time Memory
483756 2021-11-01T03:36:35 Z minhcool Popeala (CEOI16_popeala) C++17
100 / 100
 362 ms 19652 KB 
#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.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1484 KB Output is correct
2 Correct 8 ms 1356 KB Output is correct
3 Correct 8 ms 1504 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3020 KB Output is correct
2 Correct 52 ms 3900 KB Output is correct
3 Correct 76 ms 4920 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 8 ms 1484 KB Output is correct
4 Correct 8 ms 1356 KB Output is correct
5 Correct 8 ms 1504 KB Output is correct
6 Correct 36 ms 3020 KB Output is correct
7 Correct 52 ms 3900 KB Output is correct
8 Correct 76 ms 4920 KB Output is correct
9 Correct 103 ms 7056 KB Output is correct
10 Correct 143 ms 9184 KB Output is correct
11 Correct 325 ms 18756 KB Output is correct
12 Correct 349 ms 19092 KB Output is correct
13 Correct 358 ms 19476 KB Output is correct
14 Correct 362 ms 19512 KB Output is correct
15 Correct 360 ms 19652 KB Output is correct