Submission #257746

#	Time	Username	Problem	Language	Result	Execution time	Memory
257746		amiratou	Popeala (CEOI16_popeala)	C++14	100 / 100	1673 ms	50692 KiB

popeala

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ld long double
#define ll long long
//#define int ll
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define pb push_back
#define EPS 1e-9
const int INF = 2000000009;
const int MOD = 1000000007; // 998244353
const int MX_t = 20003 , MX_n = 53;
int n,t,s,p[MX_t],A[MX_t][MX_n],dp[MX_n][MX_t],pre[MX_n][MX_t],par[MX_t];
string S;
vii ranges[MX_n][MX_t];
int find_set(int i){
	if(par[i]==i)return i;
	return par[i]=find_set(par[i]);
}
int32_t main(){
	boost;
	//freopen(".in","r",stdin);
	cin>>n>>t>>s;
	for (int i = 1; i <= t; ++i)
	{
		cin>>p[i];
		if(i)p[i]+=p[i-1];
	}
	for (int i = 0; i < n; ++i)
	{
		cin>>S;
		for (int j = 1; j <= t; ++j)
		{
			if(S[j-1]=='0')A[j][i]=j;
			else A[j][i]=A[j-1][i];
		}
	}
	for (int i = 1; i <= t; ++i)
	{
		A[i][n]=i;
		sort(A[i],A[i]+n+1);
	}
	for (int i = 0; i < MX_n; ++i)
		for (int j = 0; j <= t; ++j)
			dp[i][j]=INF,pre[i][j]=INF;
	dp[0][0]=0;
	for (int j = 1; j <= t; ++j)
	{
		if(A[j][0])ranges[0][A[j][0]].pb({1,j});
		for (int i = 0; i <= n; ++i)
			if((A[j][i]+1) <= A[j][i+1])
				ranges[i+1][A[j][i+1]].pb({A[j][i]+1,j});
	}
	for (int k = 1; k <= s; ++k)
	{
		for (int x = 0; x <= n; ++x)
		{
			stack<int> st;
			for (int j = 1; j <= t; ++j)
				par[j]=j;
			for (int j = 1; j <= t; ++j)
			{
				int val;
				if(dp[k-1][j-1]!=INF)val=dp[k-1][j-1]-p[j-1]*x;
				else val=INF;
				while(!st.empty() && ((dp[k-1][st.top()-1]==INF)?INF:(dp[k-1][st.top()-1]-p[st.top()-1]*x)) > val){
					par[st.top()]=j;
					st.pop();
				}
				st.push(j);
				for(auto it:ranges[x][j]){
					int h=find_set(it.fi);
					if(dp[k-1][h-1]!=INF)pre[x][it.se]=dp[k-1][h-1]-p[h-1]*x;
					else pre[x][it.se]=INF;
				}
			}
		}
		for (int j = 1; j <= t; ++j)
			for (int x = 0; x <= n; ++x)
				if(pre[x][j]!=INF)dp[k][j]=min(dp[k][j],pre[x][j]+p[j]*x);
		cout<<dp[k][t]<<"\n";
	}
	return 0;
}

//do smth instead of nothing and stay organized
//long long
//array bounds
//special cases
//binary search

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