Submission #604499

#	Time	Username	Problem	Language	Result	Execution time	Memory
604499		Monchito	Popeala (CEOI16_popeala)	C++14	8 / 100	2099 ms	200252 KiB

popeala

//-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 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74