제출 #1179335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179335		ByeWorld	조교 (CEOI16_popeala)	C++20	100 / 100	1146 ms	20828 KiB

popeala

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
// #define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 2e4+10;
const int MAXA = 1e9;
const int INF = 2e9+100;
const int SQRT = 500;
const int LOG = 19;
const int MOD = 998244353;
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }
int sum(int a, int b){ a %= MOD; b %= MOD; return (a+b)%MOD; }
void chsum(int &a, int b){ a %= MOD; b %= MOD; a = (a+b)%MOD; }
void chsub(int &a, int b){ a %= MOD; b %= MOD; a = (a+MOD-b)%MOD; }
int mul(int a, int b){ a %= MOD; b %= MOD; return a*b%MOD;}
void chmul(int &a, int b){ a = a*b%MOD; }
int expo(int a, int b){
	if(b==0) return 1;
	int te = expo(a, b/2); te = mul(te, te);
	return (b%2 ? mul(te, a) : te);
}

int n, t, S;
int val[MAXN], a[MAXN], pr[52][MAXN], ba[52][MAXN], cost[MAXN];
int dp[MAXN][52], pref[MAXN][52], npref[MAXN][52];

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>t>>S;
	for(int i=1; i<=t; i++) cin>>a[i];
	for(int i=1; i<=t; i++) val[i] = val[i-1]+a[i];

	for(int i=1; i<=n; i++){
		string s; cin>>s; s = '.'+s;
		vector<int>zer; zer.pb(0);
		for(int j=1; j<=t; j++){
			pr[i][j] = pr[i][j-1] + (s[j]=='1' ? 1:0);
			if(pr[i][j] == j) cost[j]++;
			if(s[j]=='0') zer.pb(j);
		}
		zer.pb(t+1);
		for(int x=0; x+1<zer.size(); x++){
			int nx = zer[x+1];
			for(int j=zer[x]; j<nx; j++) 
				ba[i][j] = zer[x];
		}

		// for(int j=1; j<=t; j++) cout << ba[i][j] << ' ';
		// 	cout << "j" << ' ' << i << " inij\n";
	}
	for(int k=0; k<=S; k++)
		for(int r=0; r<=t; r++) dp[r][k] = INF;
	for(int r=1; r<=t; r++) dp[r][1] = cost[r] * val[r];
	
	for(int r=0; r<=t; r++){
		for(int p=0; p<=n; p++){
			pref[r][p] = INF; npref[r][p] = INF;
			if(r==0) continue;
			pref[r][p] = min(pref[r-1][p], 
				dp[r][1] - p*val[r]);
		}
	}

	for(int k=2; k<=S; k++){
		for(int r=1; r<=t; r++){
			// dp[r][k]
			vector<int>idx;
			for(int i=1; i<=n; i++) 
				idx.pb(ba[i][r]); // idx back yg kena 0 (buat i)
			sort(idx.begin(), idx.end());

			for(int p=0; p<n; p++){
				int l = idx[p];
				if(l==0) continue;
				chmn(dp[r][k], pref[l-1][p] + p*val[r]);
			}
			chmn(dp[r][k], pref[r-1][n] + n*val[r]);

			for(int p=0; p<=n; p++)
				npref[r][p] = min(npref[r-1][p], 
					dp[r][k] - p*val[r]);
		}
		for(int r=1; r<=t; r++)
			for(int p=0; p<=n; p++)
				pref[r][p] = npref[r][p], 
				npref[r][p] = INF;
	}
	for(int i=1; i<=S; i++)
		cout << dp[t][i] << '\n';
}

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