Submission #1189650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189650		Dan4Life	Popeala (CEOI16_popeala)	C++20	100 / 100	1943 ms	63248 KiB

popeala

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)

using ll = long long;
template<class T=int> using ar2 = array<T,2>;
template<class T=int> using ar3 = array<T,3>;

const int mxN = (int)2e4+5;
const int mxLg = 15;
const int INF = (int)2e9+1;
const ll LINF = (int)2e18+1;

int n, m, kk;
int pr[55][mxN];
int a[mxN], dp[55][mxN];
int bad[mxN], pref[mxN];
int jmp[52][mxLg][mxN];

int query(int t, int l, int r){
	if(l>r) return INF;
	int LG = __lg(r-l+1);
	return min(jmp[t][LG][l],jmp[t][LG][r-(1<<LG)+1]);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> m >> n >> kk;
	for(int i = 1; i <= n; i++) cin >> a[i], pref[i]=pref[i-1]+a[i];
	for(int i = 0; i < m; i++){
		string s; cin >> s;
		for(int j = 1; j <= sz(s); j++){
			if(s[j-1]=='0') pr[i][j] = j;
			else pr[i][j] = pr[i][j-1];
		}
	}
	int tot = m; 
	for(int i = 0; i <= kk; i++)
		for(int j = 0; j <= n; j++)
			dp[i][j] = INF;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < m; j++) 
			if(pr[j][i] and !pr[j][i-1]) tot--;
		dp[1][i] = tot*pref[i];
	}
	cout << dp[1][n] << "\n";
	for(int _ = 2; _ <= kk; _++){
		for(int i = 0; i <= m; i++){
			for(int j = 1; j <= n; j++)
				jmp[i][0][j] = dp[_-1][j]-i*pref[j];
			for(int j = 1; j < mxLg; j++)
				for(int k = 1; k+(1<<j)-1<=n; k++)
					jmp[i][j][k] = min(jmp[i][j-1][k], jmp[i][j-1][k+(1<<j-1)]); 
		}
		for(int i = 1; i <= n; i++){
			vector<int> v; v.clear(); v.pb(0); v.pb(i);
			for(int j = 0; j < m; j++){
				int x = pr[j][i]; bad[x]++, v.pb(x);
			}
			sort(all(v)); v.erase(unique(all(v)),end(v));
			
			int tot = m;
			for(int j = sz(v)-1; j >= 1; j--){
				tot-=bad[v[j]];
				int xd = query(tot, max(1,v[j-1]),v[j]-1);
				dp[_][i] = min(dp[_][i], xd+tot*pref[i]);
			}
			
			for(int j = 0; j < m; j++) bad[pr[j][i]]--;
		}
		cout << dp[_][n] << "\n";
	}
}

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