oj.uz

Submission #63102

# Submission time Handle Problem Language Result Execution time Memory
63102 2018-07-31T16:53:53 Z bazsi700 Popeala (CEOI16_popeala) C++14
26 / 100
 2000 ms 221564 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];
	}
	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;
		}
	}
	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]);
		}
	}
	if(t > 20000 || n > 50 || s > 50) {
		return 0;
	}
	vector<int> solves (n);
	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) {
				currsiz++;
				if(currsiz > i-j+1) {
					break;
				}
				while(ind < n && solves[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 4 ms 1040 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 6576 KB Output is correct
2 Correct 54 ms 6576 KB Output is correct
3 Correct 59 ms 6576 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 25264 KB Output is correct
2 Correct 347 ms 34232 KB Output is correct
3 Correct 405 ms 45196 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 1040 KB Output is correct
3 Correct 57 ms 6576 KB Output is correct
4 Correct 54 ms 6576 KB Output is correct
5 Correct 59 ms 6576 KB Output is correct
6 Correct 263 ms 25264 KB Output is correct
7 Correct 347 ms 34232 KB Output is correct
8 Correct 405 ms 45196 KB Output is correct
9 Correct 548 ms 72784 KB Output is correct
10 Correct 948 ms 94992 KB Output is correct
11 Correct 1778 ms 221180 KB Output is correct
12 Correct 1705 ms 221400 KB Output is correct
13 Execution timed out 2081 ms 221564 KB Time limit exceeded
14 Halted 0 ms 0 KB -