oj.uz

Submission #891886

# Submission time Handle Problem Language Result Execution time Memory
891886 2023-12-24T11:17:53 Z 8pete8 Let's Win the Election (JOI22_ho_t3) C++17
21 / 100
 968 ms 6604 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<float.h>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<pii,int>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
//#define int long long
#define double long double
const int mod=998244353,mxn=2e5+5,lg=30,inf=1e9,minf=-1e9,Mxn=100000;
//bool use[mxn+10];
double dp[600][600];
int32_t main(){
    fastio
    int n,k;cin>>n>>k;
    double ans=inf;
    vector<pii>v(n);
    for(int i=0;i<n;i++){
        cin>>v[i].f>>v[i].s;
        v[i].s=(v[i].s==-1)?inf:v[i].s;
        swap(v[i].s,v[i].f);
    }
    sort(all(v));
    vector<vector<int>>sum(600,vector<int>(600,inf));
    for(int i=0;i<=n;i++)sum[i][0]=0;
    for(int i=n-1;i>=0;i--)for(int j=k;j>=1;j--)sum[i][j]=min(sum[i+1][j],sum[i+1][j-1]+v[i].s);
    dp[0][0]=0;
    for(int use=1;use<=k;use++){
        for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)dp[i][j]=inf;
        dp[0][0]=0;
        for(int j=0;j<k;j++){
            for(int g=0;g<use;g++){
                dp[j+1][g]=min(dp[j][g]+(v[j].s*1.0/use),dp[j+1][g]);
                if(v[j].f!=inf)dp[j+1][g+1]=min(dp[j+1][g+1],dp[j][g]+(v[j].f*1.0/(g+1)));
            }
            ans=min(ans,dp[j+1][use-1]+sum[j+1][k-j-1]*1.0/use);
        }
    }
    cout<<setprecision(12);
    cout<<ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1904 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 52 ms 6492 KB Output is correct
6 Correct 129 ms 6492 KB Output is correct
7 Correct 279 ms 6604 KB Output is correct
8 Correct 459 ms 6584 KB Output is correct
9 Correct 683 ms 6588 KB Output is correct
10 Correct 416 ms 6584 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1904 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 52 ms 6492 KB Output is correct
6 Correct 129 ms 6492 KB Output is correct
7 Correct 279 ms 6604 KB Output is correct
8 Correct 459 ms 6584 KB Output is correct
9 Correct 683 ms 6588 KB Output is correct
10 Correct 416 ms 6584 KB Output is correct
11 Correct 1 ms 1880 KB Output is correct
12 Correct 164 ms 6584 KB Output is correct
13 Correct 162 ms 6580 KB Output is correct
14 Correct 162 ms 6488 KB Output is correct
15 Correct 488 ms 6580 KB Output is correct
16 Correct 482 ms 6488 KB Output is correct
17 Correct 443 ms 6588 KB Output is correct
18 Correct 968 ms 6580 KB Output is correct
19 Correct 874 ms 6584 KB Output is correct
20 Correct 755 ms 6432 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 33.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 934 ms 6584 KB Output is correct
2 Correct 926 ms 6588 KB Output is correct
3 Correct 903 ms 6584 KB Output is correct
4 Correct 902 ms 6588 KB Output is correct
5 Correct 905 ms 6580 KB Output is correct
6 Correct 917 ms 6592 KB Output is correct
7 Correct 911 ms 6492 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1904 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 52 ms 6492 KB Output is correct
6 Correct 129 ms 6492 KB Output is correct
7 Correct 279 ms 6604 KB Output is correct
8 Correct 459 ms 6584 KB Output is correct
9 Correct 683 ms 6588 KB Output is correct
10 Correct 416 ms 6584 KB Output is correct
11 Correct 1 ms 1880 KB Output is correct
12 Correct 164 ms 6584 KB Output is correct
13 Correct 162 ms 6580 KB Output is correct
14 Correct 162 ms 6488 KB Output is correct
15 Correct 488 ms 6580 KB Output is correct
16 Correct 482 ms 6488 KB Output is correct
17 Correct 443 ms 6588 KB Output is correct
18 Correct 968 ms 6580 KB Output is correct
19 Correct 874 ms 6584 KB Output is correct
20 Correct 755 ms 6432 KB Output is correct
21 Incorrect 1 ms 1884 KB Output isn't correct
22 Halted 0 ms 0 KB -