Submission #527879

#	Time	Username	Problem	Language	Result	Execution time	Memory
527879		Jasiekstrz	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	111 ms	2376 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int INF=1e6+7;
const int N=500;
pair<int,int> t[N+10];
double dp[N+10][N+10];
double solve(int n,int k,int m)
{
	for(int j=1;j<=m;j++)
		dp[0][j]=INF;
	for(int i=1;i<=k;i++)
	{
		dp[i][0]=dp[i-1][0]+(double)t[i].fi/(m+1);
		//cerr<<dp[i][0]<<" ";
		for(int j=1;j<=m;j++)
		{
			dp[i][j]=min(dp[i-1][j]+(double)t[i].fi/(m+1),dp[i-1][j-1]+(double)t[i].se/j);
			if(j>i)
				dp[i][j]=INF;
			//cerr<<dp[i][j]<<" \n"[j==m];
		}
	}
	priority_queue<int> pq;
	for(int i=n;i>k;i--)
		pq.push(-t[i].fi);
	int w=0;
	double ans=INF;
	for(int i=k;i>=m;i--)
	{
		ans=min(ans,dp[i][m]+(double)w/(m+1));
		pq.push(-t[i].fi);
		w-=pq.top();
		pq.pop();
	}
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>t[i].fi>>t[i].se;
		if(t[i].se==-1)
			t[i].se=INF;
	}
	sort(t+1,t+n+1,[](pair<int,int> a,pair<int,int> b){ return a.se<b.se; });
	double ans=INF;
	//cerr<<solve(n,k,3)<<"\n";
	//return 0;
	for(int m=0;m<=k;m++)
	{
		//cerr<<"m="<<m<<": "<<solve(n,k,m)<<"\n";
		ans=min(ans,solve(n,k,m));
	}
	cout<<fixed<<setprecision(4)<<ans<<"\n";
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 33 / 33
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23