oj.uz

Submission #445835

# Submission time Handle Problem Language Result Execution time Memory
445835 2021-07-19T19:55:46 Z Jasiekstrz Popeala (CEOI16_popeala) C++17
26 / 100
 2000 ms 26184 KB 
#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];
Ev ev[N+10][T+10];
int siz[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++)
		siz[i]=0;
	for(int i=0;i<=t;i++)
	{
		int lst=i+1,k=n;
		for(auto v:srt[i+1])
		{
			ev[k][siz[k]++]={lst,dp[s][i]-k*pref[i],v};
			lst=v;
			k--;
		}
		ev[k][siz[k]++]={lst,dp[s][i]-k*pref[i],t+1};
	}
	for(int i=0;i<=n;i++)
		sort(ev[i],ev[i]+siz[i]);
	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=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(int it=0;it<siz[k];it++)
			{
				Ev v=ev[k][it];
				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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 2 ms 1308 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2236 KB Output is correct
2 Correct 45 ms 2160 KB Output is correct
3 Correct 48 ms 2272 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 4340 KB Output is correct
2 Correct 294 ms 5684 KB Output is correct
3 Correct 439 ms 6776 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 2 ms 1308 KB Output is correct
3 Correct 51 ms 2236 KB Output is correct
4 Correct 45 ms 2160 KB Output is correct
5 Correct 48 ms 2272 KB Output is correct
6 Correct 216 ms 4340 KB Output is correct
7 Correct 294 ms 5684 KB Output is correct
8 Correct 439 ms 6776 KB Output is correct
9 Correct 671 ms 10076 KB Output is correct
10 Correct 983 ms 12696 KB Output is correct
11 Execution timed out 2032 ms 26184 KB Time limit exceeded
12 Halted 0 ms 0 KB -