oj.uz

Submission #136781

# Submission time Handle Problem Language Result Execution time Memory
136781 2019-07-26T08:48:09 Z MoNsTeR_CuBe Popeala (CEOI16_popeala) C++17
8 / 100
 2000 ms 764 KB 
#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.0 / 8.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2044 ms 764 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 256 KB Output is correct
2 Correct 37 ms 376 KB Output is correct
3 Execution timed out 2057 ms 508 KB Time limit exceeded
4 Halted 0 ms 0 KB -