Submission #444590

#	Time	Username	Problem	Language	Result	Execution time	Memory
444590		Jasiekstrz	Popeala (CEOI16_popeala)	C++17	26 / 100	2074 ms	25796 KiB

popeala

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int T=2e4;
const int N=50,S=50;
const int INF=1e9+7;
struct Ev
{
	int x,c;
	int en;
	bool operator<(const Ev &oth) const
	{
		return c<oth.c;
	}
};
int pref[T+10];
bool ok[N+10][T+10];
int nxt[N+10][T+10];
vector<int> srt[T+10];
int dp[S+10][T+10];
vector<Ev> ev[N+10];
int fau[T+10];
int f(int x)
{
	//if(fau[x]!=x)
	//	fau[x]=f(fau[x]);
	//return fau[x];
	return (fau[x]!=x ? fau[x]=f(fau[x]):fau[x]);
}
void u(int x,int y)
{
	fau[f(x)]=f(y);
	return;
}
void gen_event(int n,int t,int s)
{
	for(int i=0;i<=n;i++)
		ev[i].clear();
	for(int i=0;i<=t;i++)
	{
		int lst=i+1,k=n;
		for(auto v:srt[i+1])
		{
			ev[k].push_back({lst,dp[s][i]-k*pref[i],v});
			lst=v;
			k--;
		}
		ev[k].push_back({lst,dp[s][i]-k*pref[i],t+1});
	}
	for(int i=0;i<=n;i++)
		sort(ev[i].begin(),ev[i].end());
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,t,s;
	cin>>n>>t>>s;
	for(int i=0;i<=n;i++)
		ev[i].reserve(t+10);
	for(int i=1;i<=t;i++)
	{
		cin>>pref[i];
		pref[i]+=pref[i-1];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=t;j++)
		{
			char c;
			cin>>c;
			ok[i][j]=(c=='1');
		}
	}
	for(int i=1;i<=n;i++)
		nxt[i][t+1]=t+1;
	for(int j=t;j>=1;j--)
	{
		for(int i=1;i<=n;i++)
			nxt[i][j]=(ok[i][j] ? nxt[i][j+1]:j);
	}
	for(int j=1;j<=t+1;j++)
	{
		srt[j].resize(n);
		for(int i=1;i<=n;i++)
			srt[j][i-1]=nxt[i][j];
		sort(srt[j].begin(),srt[j].end());
	}
	for(int i=1;i<=t;i++)
		dp[0][i]=INF;
	dp[0][0]=0;
	for(int si=1;si<=s;si++)
	{
		gen_event(n,t,si-1);
		for(int i=0;i<=t;i++)
			dp[si][i]=INF;
		for(int k=0;k<=n;k++)
		{
			for(int i=0;i<=t+1;i++)
				fau[i]=i;
			for(auto v:ev[k])
			{
				for(int i=f(v.x);i<v.en;fau[i]=f(i+1),i=fau[i])
					dp[si][i]=min(dp[si][i],v.c+k*pref[i]);
			}
		}
		cout<<dp[si][t]<<"\n";
	}
	return 0;
}

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