Submission #604517

#	Time	Username	Problem	Language	Result	Execution time	Memory
604517		Monchito	Popeala (CEOI16_popeala)	C++17	17 / 100	1032 ms	262144 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;

vector<int> pref_points;
vector<vector<int>> pref_results;

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

int calc(int l, int r){
	int ret=0;
	int s = pref_points[r+1] - pref_points[l];

	rep(i,0,N){
		bool can = (pref_results[i][r+1] - pref_results[i][l]) == (r - l + 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));

	pref_points = vector<int>(T+1, 0);		
	rep(i,1,T+1) pref_points[i] = pref_points[i-1] + points[i-1];

	pref_results = vector<vector<int>>(N, vector<int>(T+1,0));
	rep(i,0,N) rep(j,1,T+1) 
		pref_results[i][j] = pref_results[i][j-1] + (results[i][j-1] == '1');

	rep(i, 1, S+1) cout << f(0, 0, i) << "\n";	

	return 0;
}

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