oj.uz

Submission #753814

# Submission time Handle Problem Language Result Execution time Memory
753814 2023-06-06T06:12:02 Z bgnbvnbv Let's Win the Election (JOI22_ho_t3) C++14
10 / 100
 1544 ms 8268 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e8;
const ll mod=1e9+7;

ll n,k;
struct qq
{
    ll a,b;
    bool operator<(const qq&o)
    {
        return b<o.b;
    }
}a[maxN];
using ld=long double;
ld dp[2][505][505];
void solve()
{
    cin >> n >> k;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i].a >> a[i].b;
        if(a[i].b==-1) a[i].b=1e14;
    }
    sort(a+1,a+n+1);
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=k;j++) dp[0][i][j]=inf;
    }
    dp[0][0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            for(int q=0;q<=k;q++)
            {
                dp[i&1][j][q]=dp[(i-1)&1][j][q];
                //lay vote
                if(q>=1) dp[i&1][j][q]=min(dp[i&1][j][q],dp[(i-1)&1][j][q-1]+(ld)a[i].a/(j+1));
                //lay nguoi
                if(j>=1&&q>=1) dp[i&1][j][q]=min(dp[i&1][j][q],dp[(i-1)&1][j-1][q-1]+(ld)a[i].b/(j));
            }
        }
    }
    ld ans=inf;
    //cout << dp[1][1][1]<<'\n';
    for(int j=0;j<=n;j++)
    {
        ans=min(ans,dp[n&1][j][k]);
    }
    cout << fixed<< setprecision(5)<<ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 161 ms 5140 KB Output is correct
6 Correct 477 ms 6276 KB Output is correct
7 Correct 777 ms 8240 KB Output is correct
8 Correct 1260 ms 8248 KB Output is correct
9 Correct 1502 ms 8248 KB Output is correct
10 Correct 1116 ms 8248 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 161 ms 5140 KB Output is correct
6 Correct 477 ms 6276 KB Output is correct
7 Correct 777 ms 8240 KB Output is correct
8 Correct 1260 ms 8248 KB Output is correct
9 Correct 1502 ms 8248 KB Output is correct
10 Correct 1116 ms 8248 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 481 ms 6660 KB Output is correct
13 Correct 531 ms 6664 KB Output is correct
14 Correct 449 ms 6664 KB Output is correct
15 Correct 1073 ms 8268 KB Output is correct
16 Correct 1091 ms 8252 KB Output is correct
17 Correct 1098 ms 8268 KB Output is correct
18 Correct 1516 ms 8252 KB Output is correct
19 Correct 1529 ms 8248 KB Output is correct
20 Correct 1518 ms 8268 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1544 ms 8256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 161 ms 5140 KB Output is correct
6 Correct 477 ms 6276 KB Output is correct
7 Correct 777 ms 8240 KB Output is correct
8 Correct 1260 ms 8248 KB Output is correct
9 Correct 1502 ms 8248 KB Output is correct
10 Correct 1116 ms 8248 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 481 ms 6660 KB Output is correct
13 Correct 531 ms 6664 KB Output is correct
14 Correct 449 ms 6664 KB Output is correct
15 Correct 1073 ms 8268 KB Output is correct
16 Correct 1091 ms 8252 KB Output is correct
17 Correct 1098 ms 8268 KB Output is correct
18 Correct 1516 ms 8252 KB Output is correct
19 Correct 1529 ms 8248 KB Output is correct
20 Correct 1518 ms 8268 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 324 KB Output is correct
28 Correct 1 ms 324 KB Output is correct
29 Incorrect 1 ms 340 KB Output isn't correct
30 Halted 0 ms 0 KB -