oj.uz

답안 #63099

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
63099 2018-07-31T16:51:51 Z bazsi700 조교 (CEOI16_popeala) C++14
26 / 100
 2000 ms 223500 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]);
		}
		//cout << (dp[i][1] > MOD ? -1 : dp[i][1]) << " ";
	}
	//cout << endl;
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 1124 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 6452 KB Output is correct
2 Correct 49 ms 6452 KB Output is correct
3 Correct 57 ms 6452 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 257 ms 25088 KB Output is correct
2 Correct 380 ms 34172 KB Output is correct
3 Correct 544 ms 45148 KB Output is correct

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 1124 KB Output is correct
3 Correct 70 ms 6452 KB Output is correct
4 Correct 49 ms 6452 KB Output is correct
5 Correct 57 ms 6452 KB Output is correct
6 Correct 257 ms 25088 KB Output is correct
7 Correct 380 ms 34172 KB Output is correct
8 Correct 544 ms 45148 KB Output is correct
9 Correct 672 ms 72736 KB Output is correct
10 Correct 1058 ms 94928 KB Output is correct
11 Correct 1719 ms 221136 KB Output is correct
12 Correct 1674 ms 222544 KB Output is correct
13 Execution timed out 2093 ms 223500 KB Time limit exceeded
14 Halted 0 ms 0 KB -