제출 #608756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
608756		CSQ31	조교 (CEOI16_popeala)	C++17	0 / 100	428 ms	504 KiB

popeala

#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],mx[2*MAXN],lazy[2*MAXN];
int last[50];
void tran(){
	for(int i=0;i<n;i++)last[i] = 0;
	for(int i=1;i<=t;i++){
		for(int j=0;j<n;j++){
			if(stu[j][i-1] == '1'){
				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];x<i;x++){
						for(int k=last[j];k<x;k++)dp1[k]-=pt[x];
					}
				}
				last[j] = i;
				
			}
		}
		for(int x=0;x<i;x++)dp2[i] = min(dp2[i],dp1[x]);
	}
}
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++)dp2[i] = 1e15;
	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: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74