oj.uz

Submission #63104

# Submission time Handle Problem Language Result Execution time Memory
63104 2018-07-31T16:56:01 Z bazsi700 Popeala (CEOI16_popeala) C++14
100 / 100
 1119 ms 228184 KB 
#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
#define ll long long int
#define vi vector<int>
#define vii vector< vector<int> >
#define PI 3.1415926535897932384626433832795
#define INF 9223372036854775807LL

bool solved[51][20001];
int dp[20001][51];
int minval[20002][52][52];
int prefsum[20002];
int conssolved[51][20001]; //[x][y]=z means, the xth solved y-z+1,y-z+2,...,y tasks but not the y-z th

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n,t,s;
	cin >> n >> t >> s;
	vi p(t+1);
	for(int i = 1; i <= t; i++) {
		cin >> p[i];
		prefsum[i] = prefsum[i-1]+p[i];
	}
	vector<vector<int> > solves (t+1,vi(n));
	for(int i = 1; i <= n; i++) {
		int lastnotsolv = 0;
		for(int j = 1; j <= t; j++) {
			char ch;
			cin >> ch;
			solved[i][j] = (ch == '1');
			if(!solved[i][j]) {
				lastnotsolv = j;
			}
			conssolved[i][j] = j-lastnotsolv;
		}
	}
	for(int i = 1; i <= t; i++) {
		for(int st = 1; st <= n; st++) {
			solves[i][st-1] = (conssolved[st][i]);
		}
		sort(solves[i].begin(),solves[i].end());
	}
	int sum = 0;
	for(int j = 0; j <= s; j++) {
		for(int i = 0; i <= t; i++) {
			for(int per = 0; per <= n; per++) {
				minval[i][j][per] = 2*MOD;
			}
		}
	}
	for(int i = 1; i <= t; i++) {
		sum+= p[i];
		int solv = 0;
		for(int j = 1; j <= n; j++) {
			if(conssolved[j][i] == i) {
				solv++;
			}
		}
		dp[i][1] = solv*sum;
		for(int pers = 0; pers <= n; pers++) {
			minval[i][2][pers] = min(minval[i-1][2][pers]+pers*p[i],dp[i][1]);
		}
	}
	for(int j = 2; j <= s; j++) {
		for(int i = 1; i <= t; i++) {
		//	for(int st = 1; st <= n; st++) {
		//		solves[st-1] = (conssolved[st][i]);
		//	}
		//	sort(solves.begin(),solves.end());
			int ind = 0;
			sum = prefsum[i]-prefsum[i-1];
			dp[i][j] = minval[i-1][j][n-ind]+sum*(n-ind);
			for(int currsiz : solves[i]) {
				currsiz++;
				if(currsiz > i-j+1) {
					break;
				}
				while(ind < n && solves[i][ind] < currsiz) {
					ind++;
				}
				sum = prefsum[i]-prefsum[i-currsiz];
				if(dp[i][j] == dp[i][j-1]) {
					break;
				}
				dp[i][j] = min(dp[i][j],minval[i-currsiz][j][n-ind]+sum*(n-ind));
			}
			for(int pers = 0; pers <= n; pers++) {
				minval[i][j+1][pers] = min(minval[i-1][j+1][pers]+pers*p[i],dp[i][j]);
			}
		}
	}
	for(int i = 1; i <= s; i++) {
		cout << dp[t][i] << "\n";
	}
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 1080 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6576 KB Output is correct
2 Correct 20 ms 6652 KB Output is correct
3 Correct 19 ms 6652 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 25688 KB Output is correct
2 Correct 149 ms 34796 KB Output is correct
3 Correct 204 ms 46236 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 1080 KB Output is correct
3 Correct 21 ms 6576 KB Output is correct
4 Correct 20 ms 6652 KB Output is correct
5 Correct 19 ms 6652 KB Output is correct
6 Correct 105 ms 25688 KB Output is correct
7 Correct 149 ms 34796 KB Output is correct
8 Correct 204 ms 46236 KB Output is correct
9 Correct 254 ms 74184 KB Output is correct
10 Correct 477 ms 96768 KB Output is correct
11 Correct 1064 ms 225660 KB Output is correct
12 Correct 912 ms 226024 KB Output is correct
13 Correct 1027 ms 226024 KB Output is correct
14 Correct 1053 ms 227228 KB Output is correct
15 Correct 1119 ms 228184 KB Output is correct