oj.uz

Submission #45435

# Submission time Handle Problem Language Result Execution time Memory
45435 2018-04-13T17:30:08 Z sorry_Benq Popeala (CEOI16_popeala) C++17
17 / 100
 2000 ms 2436 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
 
int N, T, S; 
int points[20005];
int prefixpoints[20005];
bool solves[52][20005];
int presolve[52][20005];
int DP[52][20005];
 
int INF = 2000000005;
 
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;
}
 
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));
			}
			assert(DP[i][j] != INF);
		}
		cout << DP[i][T] << endl;
	}
}

Compilation message

popeala.cpp:26:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 1440 KB Output is correct
2 Correct 425 ms 1488 KB Output is correct
3 Correct 518 ms 1580 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 2436 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 2 ms 744 KB Output is correct
3 Correct 436 ms 1440 KB Output is correct
4 Correct 425 ms 1488 KB Output is correct
5 Correct 518 ms 1580 KB Output is correct
6 Execution timed out 2076 ms 2436 KB Time limit exceeded
7 Halted 0 ms 0 KB -