oj.uz

Submission #536945

# Submission time Handle Problem Language Result Execution time Memory
536945 2022-03-14T07:58:54 Z errorgorn Popeala (CEOI16_popeala) C++17
100 / 100
 1606 ms 60640 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3564 KB Output is correct
2 Correct 33 ms 3412 KB Output is correct
3 Correct 34 ms 3572 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 7972 KB Output is correct
2 Correct 216 ms 10324 KB Output is correct
3 Correct 293 ms 13132 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct
3 Correct 33 ms 3564 KB Output is correct
4 Correct 33 ms 3412 KB Output is correct
5 Correct 34 ms 3572 KB Output is correct
6 Correct 158 ms 7972 KB Output is correct
7 Correct 216 ms 10324 KB Output is correct
8 Correct 293 ms 13132 KB Output is correct
9 Correct 491 ms 20412 KB Output is correct
10 Correct 670 ms 26424 KB Output is correct
11 Correct 1460 ms 58260 KB Output is correct
12 Correct 1606 ms 60552 KB Output is correct
13 Correct 1582 ms 60620 KB Output is correct
14 Correct 1605 ms 60636 KB Output is correct
15 Correct 1573 ms 60640 KB Output is correct