# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
916895 | ace5 | Let's Win the Election (JOI22_ho_t3) | C++17 | 380 ms | 6540 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
typedef long double ld;
const int maxn = 501;
ld dp[maxn][maxn];
int pr[maxn][maxn];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.precision(18);
int n,k;
cin >> n >> k;
vector<pair<int,int>> ab(n);
for(int i = 0;i < n;++i)
{
cin >> ab[i].second >> ab[i].first;
if(ab[i].first == -1)
{
ab[i].first = 1e18;
}
}
sort(ab.begin(),ab.end());
for(int pos = 0;pos < n;++pos)
{
vector<int> cc;
for(int j = pos;j < n;++j)
{
cc.push_back(ab[j].second);
}
sort(cc.begin(),cc.end());
pr[pos][0] = 0;
for(int j = 0;j < cc.size();++j)
{
pr[pos][j+1] = pr[pos][j] + cc[j];
}
}
ld ans = 1e18;
for(int kb = 0;kb <= k;++kb)
{
for(int i = n;i >= 0;--i)
{
for(int j = 0;j <= kb;++j)
{
if(i == n)
{
dp[i][j] = (j == kb ? 0 : 1e18);
}
else if(j == kb)
{
dp[i][j] = (i > k ? 1e18 : ld(pr[i][k-i])/(kb+1));
}
else
{
dp[i][j] = min(dp[i+1][j+1]+ld(ab[i].first)/(j+1),dp[i+1][j]+ld(ab[i].second)/(kb+1));
}
}
}
ans = min(ans,dp[0][0]);
}
cout << ans;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |