oj.uz

Submission #444590

# Submission time Handle Problem Language Result Execution time Memory
444590 2021-07-14T10:00:31 Z Jasiekstrz Popeala (CEOI16_popeala) C++17
26 / 100
 2000 ms 25796 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];
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.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2048 KB Output is correct
2 Correct 51 ms 2020 KB Output is correct
3 Correct 55 ms 2044 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 4148 KB Output is correct
2 Correct 337 ms 5248 KB Output is correct
3 Correct 445 ms 6548 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 1100 KB Output is correct
3 Correct 58 ms 2048 KB Output is correct
4 Correct 51 ms 2020 KB Output is correct
5 Correct 55 ms 2044 KB Output is correct
6 Correct 233 ms 4148 KB Output is correct
7 Correct 337 ms 5248 KB Output is correct
8 Correct 445 ms 6548 KB Output is correct
9 Correct 795 ms 9828 KB Output is correct
10 Correct 1067 ms 12504 KB Output is correct
11 Execution timed out 2074 ms 25796 KB Time limit exceeded
12 Halted 0 ms 0 KB -