Submission #533347

#	Time	Username	Problem	Language	Result	Execution time	Memory
533347		arnold518	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	139 ms	3288 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 500;

int N, K;
pii A[MAXN+10];

int sum[MAXN+10][MAXN+10];
double dp[MAXN+10][MAXN+10];

int main()
{
	scanf("%d%d", &N, &K);
	for(int i=1; i<=N; i++)
	{
		scanf("%d%d", &A[i].first, &A[i].second);
		if(A[i].second==-1) A[i].second=9876543;
	}
	sort(A+1, A+N+1, [&](const pii &p, const pii &q)
		{
			if(p.second!=q.second) return p.second<q.second;
			return p.first>q.first;
		});

	for(int i=0; i<=N; i++)
	{
		vector<int> V;
		for(int j=i+1; j<=N; j++) V.push_back(A[j].first);
		sort(V.begin(), V.end());
		for(int j=1; j<=V.size(); j++)
		{
			sum[i][j]=sum[i][j-1]+V[j-1];
		}
	}

	double ans=987654321;

	for(int i=0; i<=K; i++)
	{
		dp[0][0]=0;
		for(int k=1; k<=i; k++) dp[0][k]=987654321;
		ans=min(ans, dp[0][i]+(double)sum[0][K]/(i+1));
		for(int j=1; j<=K; j++)
		{
			dp[j][0]=dp[j-1][0]+(double)A[j].first/(i+1);
			for(int k=1; k<=i; k++)
			{
				dp[j][k]=min(dp[j-1][k]+(double)A[j].first/(i+1), dp[j-1][k-1]+(double)A[j].second/k);
			} 
			if(j<=K)
			{
				ans=min(ans, dp[j][i]+(double)sum[j][K-j]/(i+1));
			}
		}
	}
	printf("%.20f\n", ans);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int j=1; j<=V.size(); j++)
      |                ~^~~~~~~~~~
Main.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%d%d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   scanf("%d%d", &A[i].first, &A[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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