Submission #536945

#	Time	Username	Problem	Language	Result	Execution time	Memory
536945		errorgorn	Popeala (CEOI16_popeala)	C++17	100 / 100	1606 ms	60640 KiB

popeala

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

#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));(s)<(e)?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int k,n,s;
int arr[20005];
int pre[20005];
string ac[51];

int memo[2][20005];
int ver[51][20005];

struct node{
	int table[15][20005];
	
	void init(int v[20005]){
		int n=k+1;
		
		rep(x,0,n) table[0][x]=v[x];
		
		int layer=0;
		n--;
		while (n>0){
			rep(x,0,n)
				table[layer+1][x]=min(table[layer][x],table[layer][x+(1<<layer)]);
			
			layer++;
			n-=1<<layer;
		}
	}
	
	int query(int i,int j){
		int len=j-i+1;
		int layer=31-__builtin_clz(len);
		
		return min(table[layer][i],table[layer][j-(1<<layer)+1]);
	}
} root[51];

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k>>s;
	rep(x,1,k+1) cin>>arr[x];
	rep(x,1,k+1) pre[x]=pre[x-1]+arr[x];
	
	rep(x,0,n) cin>>ac[x];
	rep(x,0,n) ac[x]="$"+ac[x];
	
	memset(memo,63,sizeof(memo));
	
	int a=0,b=1;
	memo[a][0]=0;
	
	rep(zzz,0,s){
		memset(memo[b],63,sizeof(memo[b]));
		
		rep(x,0,n+1){
			rep(y,0,k+1) ver[x][y]=memo[a][y]-x*pre[y];
			root[x].init(ver[x]);
		}
		
		vector<ii> imp;
		rep(x,-1,n) imp.pub({0,x});
		
		rep(x,1,k+1){
			vector<ii> temp;
			for (auto it:imp) if (it.se==-1 || ac[it.se][x]=='1') temp.pub(it);
			rep(y,0,n) if (ac[y][x]=='0') temp.pub({x,y});
			
			swap(imp,temp);
			
			imp.pub({x,-1});
			
			int best=2e9+100;
			int curr=0;
			rep(y,n+1,0){
				if (imp[y].fi!=imp[y+1].fi){
					//cout<<"debug2: "<<n-y<<" "<<imp[y+1]<<" "<<imp[y]-1<<endl;
					//cout<<root[n-y].query(imp[y+1],imp[y]-1)<<endl;
					best=min(best,root[y].query(imp[y].fi,imp[y+1].fi-1)+curr);
				}
				curr-=pre[x];
			}
			best+=n*pre[x];
			
			memo[b][x]=best;
			imp.pob();
		}
		
		swap(a,b);
		//rep(x,0,k+1) cout<<memo[a][x]<<" "; cout<<endl;
		
		cout<<memo[a][k]<<endl;
	}
}

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