oj.uz

Submission #936929

# Submission time Handle Problem Language Result Execution time Memory
936929 2024-03-03T04:09:04 Z Marco_Escandon Let's Win the Election (JOI22_ho_t3) C++11
5 / 100
 2110 ms 9048 KB 
#include<bits/stdc++.h>
#define optimizar_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(3);
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
#define x first
#define y second
pair<double,double> cad[501];
pair<double,double> dp[3][503][503];
int main()
{
    optimizar_io
    ll n,m;
    cin>>n>>m;
    cad[0]={-1,-1};
    for(int i=1; i<=n; i++)
        cin>>cad[i].second>>cad[i].first;
    sort(cad,cad+n);
    for(int i=0; i<2; i++)
        for(int j=0; j<=n; j++)
            for(int k=0; k<=m+2; k++)
                dp[i][j][k]={1e9,1e9};
    dp[0][1][1]={0,0};
    double bs=1e9;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            for(int k=1; k<=m+1; k++)
            {
                pair<double,double> temp={1e9,1e9};
                temp=min(temp,dp[0][j][k]);
                temp=min(temp,{dp[0][j][k-1].x+cad[i].y/j,dp[0][j][k-1].y});
                if(cad[i].first!=-1&&j!=1)
                    temp=min(temp,{(dp[0][j-1][k-1].x-dp[0][j-1][k-1].y)*(j-1)/j+dp[0][j-1][k-1].y+cad[i].x/(j-1),dp[0][j-1][k-1].y+cad[i].x/(j-1)});
                dp[1][j][k]=temp;
                if(k==m+1) bs=min(bs,dp[1][j][k].first);
            }
            //cout<<"\n";
        }
        swap(dp[0],dp[1]);
        //cout<<"\n\n";
    }
    cout<<bs;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Correct 3 ms 8380 KB Output is correct
3 Correct 4 ms 8388 KB Output is correct
4 Correct 4 ms 8280 KB Output is correct
5 Correct 305 ms 8808 KB Output is correct
6 Correct 504 ms 8836 KB Output is correct
7 Correct 834 ms 8852 KB Output is correct
8 Correct 1193 ms 9048 KB Output is correct
9 Correct 1524 ms 8836 KB Output is correct
10 Correct 1113 ms 8828 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Correct 3 ms 8380 KB Output is correct
3 Correct 4 ms 8388 KB Output is correct
4 Correct 4 ms 8280 KB Output is correct
5 Correct 305 ms 8808 KB Output is correct
6 Correct 504 ms 8836 KB Output is correct
7 Correct 834 ms 8852 KB Output is correct
8 Correct 1193 ms 9048 KB Output is correct
9 Correct 1524 ms 8836 KB Output is correct
10 Correct 1113 ms 8828 KB Output is correct
11 Correct 4 ms 8284 KB Output is correct
12 Correct 742 ms 8832 KB Output is correct
13 Correct 668 ms 9044 KB Output is correct
14 Correct 619 ms 8832 KB Output is correct
15 Correct 1514 ms 8792 KB Output is correct
16 Correct 1335 ms 8852 KB Output is correct
17 Correct 1173 ms 8796 KB Output is correct
18 Incorrect 2056 ms 8832 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8280 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Correct 6 ms 8284 KB Output is correct
4 Correct 5 ms 8284 KB Output is correct
5 Correct 5 ms 8284 KB Output is correct
6 Correct 5 ms 8284 KB Output is correct
7 Correct 5 ms 8284 KB Output is correct
8 Correct 6 ms 8284 KB Output is correct
9 Correct 5 ms 8280 KB Output is correct
10 Correct 5 ms 8284 KB Output is correct
11 Correct 5 ms 8280 KB Output is correct
12 Correct 5 ms 8280 KB Output is correct
13 Correct 7 ms 8280 KB Output is correct
14 Incorrect 5 ms 8436 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8280 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Correct 6 ms 8284 KB Output is correct
4 Correct 5 ms 8284 KB Output is correct
5 Correct 5 ms 8284 KB Output is correct
6 Correct 5 ms 8284 KB Output is correct
7 Correct 5 ms 8284 KB Output is correct
8 Correct 6 ms 8284 KB Output is correct
9 Correct 5 ms 8280 KB Output is correct
10 Correct 5 ms 8284 KB Output is correct
11 Correct 5 ms 8280 KB Output is correct
12 Correct 5 ms 8280 KB Output is correct
13 Correct 7 ms 8280 KB Output is correct
14 Incorrect 5 ms 8436 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8280 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Correct 6 ms 8284 KB Output is correct
4 Correct 5 ms 8284 KB Output is correct
5 Correct 5 ms 8284 KB Output is correct
6 Correct 5 ms 8284 KB Output is correct
7 Correct 5 ms 8284 KB Output is correct
8 Correct 6 ms 8284 KB Output is correct
9 Correct 5 ms 8280 KB Output is correct
10 Correct 5 ms 8284 KB Output is correct
11 Correct 5 ms 8280 KB Output is correct
12 Correct 5 ms 8280 KB Output is correct
13 Correct 7 ms 8280 KB Output is correct
14 Incorrect 5 ms 8436 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Correct 3 ms 8380 KB Output is correct
3 Correct 4 ms 8388 KB Output is correct
4 Correct 4 ms 8280 KB Output is correct
5 Correct 305 ms 8808 KB Output is correct
6 Correct 504 ms 8836 KB Output is correct
7 Correct 834 ms 8852 KB Output is correct
8 Correct 1193 ms 9048 KB Output is correct
9 Correct 1524 ms 8836 KB Output is correct
10 Correct 1113 ms 8828 KB Output is correct
11 Correct 4 ms 8284 KB Output is correct
12 Correct 742 ms 8832 KB Output is correct
13 Correct 668 ms 9044 KB Output is correct
14 Correct 619 ms 8832 KB Output is correct
15 Correct 1514 ms 8792 KB Output is correct
16 Correct 1335 ms 8852 KB Output is correct
17 Correct 1173 ms 8796 KB Output is correct
18 Incorrect 2056 ms 8832 KB Output isn't correct
19 Halted 0 ms 0 KB -