oj.uz

Submission #608801

# Submission time Handle Problem Language Result Execution time Memory
608801 2022-07-27T10:17:20 Z CSQ31 Popeala (CEOI16_popeala) C++17
17 / 100
 2000 ms 624 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e4+1;
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long int ll;
int pt[MAXN],n,t,s;
string stu[50];
ll dp1[MAXN],dp2[MAXN],mn[2*MAXN],lazy[2*MAXN];
int last[50];
void build(int v,int l,int r){
	lazy[v] = 0;
	if(l==r){
		mn[v] = dp1[l];
		return;
	}
	int tm = (l+r)/2;
	build(2*v,l,tm);
	build(2*v+1,tm+1,r);
	mn[v] = min(mn[2*v],mn[2*v+1]);
}
void upd(int v,int l,int r,int tl,int tr,int val){
	if(l>r)return;
	if(l==tl && r==tr){
		mn[v]+=val;
		lazy[v]+=val;
		return;
	}
	int tm = (tl+tr)/2;
	upd(2*v,l,min(tm,r),tl,tm,val);
	upd(2*v+1,max(l,tm+1),r,tm+1,tr,val);
	mn[v] = min(mn[2*v],mn[2*v+1]) + lazy[v];
}
ll query(int v,int l,int r,int tl,int tr){
	if(l>r)return 1e15;
	if(l==tl && r==tr)return mn[v];
	int tm = (tl+tr)/2;
	return min(query(2*v,l,min(tm,r),tl,tm),
	           query(2*v+1,max(l,tm+1),r,tm+1,tr)) + lazy[v];
}
void tran(){
	for(int i=0;i<n;i++)last[i] = 0;
	build(1,0,t);
	for(int i=1;i<=t;i++){
		for(int j=0;j<n;j++){
			if(stu[j][i-1] == '1'){
				upd(1,last[j],i-1,0,t,pt[i]);
				//for(int k=last[j];k<i;k++)dp1[k]+=pt[i];
				//[last[j],i) gets increased by pt[i]
			}else{
				//reverse the change did
				if(i>1 && stu[j][i-2] == '1'){
					//for(int x=last[j]+1;x<i;x++){
					//	for(int k=last[j];k<x;k++)dp1[k]-=pt[x];
					//}
					for(int x=last[j]+1;x<i;x++)upd(1,last[j],x-1,0,t,-pt[x]);
				}
				last[j] = i;
				
			}
		}
		//for(int x=0;x<i;x++)dp2[i] = min(dp2[i],dp1[x]);
		dp2[i] = query(1,0,i-1,0,t);
	}
	//for(int i=0;i<=t;i++)cout<<dp2[i]<<" ";
	//cout<<'\n';
}
int main(){
	owo
	cin>>n>>t>>s;
	for(int i=1;i<=t;i++)cin>>pt[i];
	for(int i=0;i<n;i++)cin>>stu[i];
	
	vector<int>ans(s+1,0);
	for(int i=0;i<=t;i++)dp1[i] = dp2[i]= 1e15;
	dp1[0] = 0;
	for(int i=1;i<=s;i++){
		tran();
		ans[i] = dp2[t];
		for(int j=0;j<=t;j++){
			swap(dp1[j],dp2[j]);
			dp2[j] = 1e15;
		}
	}
	for(int i=1;i<=s;i++)cout<<ans[i]<<'\n';
	
	
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 376 KB Output is correct
2 Correct 269 ms 384 KB Output is correct
3 Correct 299 ms 384 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1456 ms 624 KB Output is correct
2 Execution timed out 2060 ms 596 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 288 ms 376 KB Output is correct
4 Correct 269 ms 384 KB Output is correct
5 Correct 299 ms 384 KB Output is correct
6 Correct 1456 ms 624 KB Output is correct
7 Execution timed out 2060 ms 596 KB Time limit exceeded
8 Halted 0 ms 0 KB -