Submission #45287

#	Time	Username	Problem	Language	Result	Execution time	Memory
45287		sorry_Benq	Popeala (CEOI16_popeala)	C++17	8 / 100	2059 ms	1028 KiB

popeala

#include <bits/stdc++.h>
#define int long long
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;
}

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;
	}
}

Compilation message (stderr)

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

• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74