oj.uz

Submission #604517

# Submission time Handle Problem Language Result Execution time Memory
604517 2022-07-25T07:14:49 Z Monchito Popeala (CEOI16_popeala) C++17
17 / 100
 1032 ms 262144 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;

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 199792 KB Output is correct
2 Correct 79 ms 199836 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1030 ms 200104 KB Output is correct
2 Correct 910 ms 200104 KB Output is correct
3 Correct 1032 ms 200104 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 450 ms 262144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 199792 KB Output is correct
2 Correct 79 ms 199836 KB Output is correct
3 Correct 1030 ms 200104 KB Output is correct
4 Correct 910 ms 200104 KB Output is correct
5 Correct 1032 ms 200104 KB Output is correct
6 Runtime error 450 ms 262144 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -