oj.uz

Submission #63100

# Submission time Handle Problem Language Result Execution time Memory
63100 2018-07-31T16:52:38 Z bazsi700 Popeala (CEOI16_popeala) C++14
26 / 100
 2000 ms 221352 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 && t == 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 3 ms 376 KB Output is correct
2 Correct 5 ms 1128 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6460 KB Output is correct
2 Correct 52 ms 6460 KB Output is correct
3 Correct 57 ms 6544 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 25252 KB Output is correct
2 Correct 372 ms 34216 KB Output is correct
3 Correct 424 ms 45224 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 1128 KB Output is correct
3 Correct 60 ms 6460 KB Output is correct
4 Correct 52 ms 6460 KB Output is correct
5 Correct 57 ms 6544 KB Output is correct
6 Correct 317 ms 25252 KB Output is correct
7 Correct 372 ms 34216 KB Output is correct
8 Correct 424 ms 45224 KB Output is correct
9 Correct 563 ms 72744 KB Output is correct
10 Correct 957 ms 94804 KB Output is correct
11 Correct 1879 ms 221096 KB Output is correct
12 Correct 1890 ms 221352 KB Output is correct
13 Execution timed out 2074 ms 221352 KB Time limit exceeded
14 Halted 0 ms 0 KB -