oj.uz

Submission #45286

# Submission time Handle Problem Language Result Execution time Memory
45286 2018-04-12T13:47:48 Z sorry_Benq Popeala (CEOI16_popeala) C++17
8 / 100
 2000 ms 1012 KB 
#include <bits/stdc++.h>
using namespace std;

int N, T, S; 
int points[20005];
int prefixpoints[20005];
bool solves[20005][52];
int presolve[20005][52];
int DP[52][20005];

int INF = 2e9 + 5;

int score(int i, int j){
	//value of zero indexed [i, j] inclusive interval
	int val = prefixpoints[j] - prefixpoints[i - 1];
	int res = 0;
	for (int x = 1; x <= N; x++){
		if (presolve[x][j] - presolve[x][i - 1] == j - i + 1){
			res += val;
		}
	} 
	return res;
}

int main(){
	cin >> N >> T >> S;
	for (int i = 1; i <= T; i++){
		cin >> points[i];
	}
	prefixpoints[0] = 0;
	for (int i = 1; i <= T; i++){
		prefixpoints[i] = prefixpoints[i - 1] + points[i];
	}
	for (int i = 1; i <= N; i++){
		string s; cin >> s;
		for (int j = 1; j <= T; j++){
			solves[i][j] = (s[j - 1] - '0');
		}
		presolve[i][0] = 0;
		for (int j = 1; j <= T; j++){
			presolve[i][j] = solves[i][j] + presolve[i][j - 1];
		}
	}
	for (int j = 1; j <= T; j++){
		DP[1][j] = score(1, j);
	}
	cout << DP[1][T] << endl;
	for (int i = 2; i <= S; i++){
		for (int j = i; j <= T; j++){
			DP[i][j] = INF;
			for (int k = i; k <= j; k++){
				DP[i][j] = min(DP[i][j], DP[i - 1][k - 1] + score(k, j));
			}
		}
		cout << DP[i][T] << endl;
	}
}

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 624 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 340 ms 808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 1012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 624 KB Output is correct
3 Incorrect 340 ms 808 KB Output isn't correct
4 Halted 0 ms 0 KB -