oj.uz

Submission #604499

# Submission time Handle Problem Language Result Execution time Memory
604499 2022-07-25T07:05:48 Z Monchito Popeala (CEOI16_popeala) C++14
8 / 100
 2000 ms 200252 KB 
//-Si puedes imaginarlo, puedes programarlo- Alejandro Taboada
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#define fst first
#define snd second
#define pb push_back
#define sz(x) (int)x.size()
#define rep(i,x,n) for(__typeof(n)i=(x);i!=(n);i+=1-2*((x)>(n)))
#define dbg(x) cout << #x << "=" << x << " ";
#define line cout << "\n.......................................................\n";

const int INF = 2e9 + 3;

int N, T, S;
vector<int> points;
vector<string> results;

int dp[1000][1000][51];

int calc(int l, int r){
	int ret=0;
	int s=0;
	rep(i,l,r+1) s+=points[i];

	rep(i,0,N){
		bool can=true;
		rep(j,l,r+1) can &= (results[i][j]=='1');
		if(can) ret+=s;
	}
	return ret;
}
int f(int l, int r, int k){
	if(r == T){
		if(l == T && k == 0) return 0;
		else return INF;
	}
	if(k <= 0) return INF;
	int& ret = dp[l][r][k];
	if(ret != -1) return ret;

	ret = INF;
	ret = min(f(l, r+1, k), f(r+1, r+1, k-1) + calc(l, r));

	return ret;
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>N>>T>>S;
	points = vector<int>(T);
	results = vector<string>(N);
	rep(i,0,T) cin>>points[i];
	rep(i,0,N) cin>>results[i];
	memset(dp, -1, sizeof(dp));
	rep(i, 1, S+1) cout << f(0, 0, i) << "\n";	

	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 199884 KB Output is correct
2 Correct 87 ms 199920 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2099 ms 199876 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 2077 ms 200252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 199884 KB Output is correct
2 Correct 87 ms 199920 KB Output is correct
3 Execution timed out 2099 ms 199876 KB Time limit exceeded
4 Halted 0 ms 0 KB -