Submission #136781

#	Time	Username	Problem	Language	Result	Execution time	Memory
136781		MoNsTeR_CuBe	Popeala (CEOI16_popeala)	C++17	8 / 100	2057 ms	764 KiB

popeala

#include <bits/stdc++.h>
using namespace std;

#define int long long 

vector< string > contestant;

int N;

int check(int a, int b){
	int tot = 0;
	for(int i = 1; i <= N; i++){
		//cout << "CONTESTANT " << contestant[i].size() << endl;
		bool verif = false;
		for(int j = a-1; j < b; j++){
			if(contestant[i][j] == '0'){
				verif = true;
				break;
			}
		}
		if(!verif)tot++;
	} 
	return tot;
}

vector< vector< int > > memo;
vector< int > pref_P;

int dp(int n, int k){
	
	if(k == 0 && n == 0) return 0;
	
	if(k == 0 || n == 0){
		return INT_MAX;
	}
	
	if(memo[n][k] != -1) return memo[n][k];
	
	memo[n][k] = INT_MAX;
	
	for(int j = 1; j <= n; j++){
		//cout << "ANS " << check(j,n) << ' ' << pref_P[n] << ' ' << pref_P[j-1] << endl;
		memo[n][k] = min(memo[n][k], dp(j-1, k-1) + check(j,n) * (pref_P[n] - pref_P[j-1]));
	}
	
	//cout << "DP " << n << ' ' << k << ' ' << memo[n][k] << endl;
	
	return memo[n][k];
}

signed main(){
	int n, t, s;
	cin >> n >> t >> s;
	N = n;
	vector< int > points(t+1);
	
	pref_P.resize(t+1);
	
	for(int i = 1; i <= t; i++){
		cin >> points[i];
		pref_P[i] += pref_P[i-1] + points[i];
	}
	
	contestant.resize(n+1);
	
	for(int i = 1; i <= n; i++){
		cin >> contestant[i];
	}
	
	for(int i = 1; i <= s; i++){
		
		memo.assign(t+1, vector< int >(i+1,-1));
		cout << dp(t,i) << endl;
	}
	
}

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