Submission #1241092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241092		damoon	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	1002 ms	8504 KiB

Main

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

//#pragma GCC optimize("O3,unroll-loops") //main
//#pragma GCC target("avx2") //cf...
//#pragma GCC target("sse4") //Quera

#define ld long double
#define ll long long
typedef pair<ld,ld> pii;
#define f first
#define s second

#define lc 2*id
#define rc 2*id+1
#define all(x) x.begin(),x.end()

#define pb push_back
#define pp pop_back
#define unicorn(x) x.resize(unique(x.begin(),x.end())-x.begin())

string pr(int* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr( ll* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr(vector<int> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr( vector<ll> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr(pii* vv,int l,int r){for(int i=l;i<r;i++)cout<<"( "<<vv[i].f<<","<<vv[i].s<<" )    ";return "";}
string pr(vector<pii> vv){for(auto i:vv)cout<<"( "<<i.f<<","<<i.s<<" )    ";return "";}

const int L = 500+10,mod = 1e9+7;
const int inf = 1e9+10;
int n,k;
pii inp[L];
ld a[L],b[L];
ld dp[2][L][L];
ld ans = inf;
vector<ld> sf;

int main(){
    //ofstream cout ("out.out");
    //ifstream cin ("in.in");

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>inp[i].s>>inp[i].f;
        if(inp[i].f == -1){
            inp[i].f = inf;
        }
    }

    sort(inp+1,inp+n+1);
    for(int i=1;i<=n;i++){
        a[i] = inp[i].s;
        b[i] = inp[i].f;
    }

    for(int i=0;i<=k;i++){
        dp[0][0][k] = 0;
    }
    for(int i=1;i<=k;i++){
        for(int j=0;j<=k;j++){
            dp[0][i][j] = inf;
        }
    }

    sf.clear();
    for(int i=1;i<=n;i++){
        sf.pb(a[i]);
    }

    sort(all(sf));
    ans = 0;
    for(int i=0;i<k;i++){
        ans += sf[i];
    }

    for(int i=1;i<=k;i++){
        int id = i%2;
        for(int j=0;j<=k;j++){
            for(int h=0;h<=k;h++){
                dp[id][j][h] = dp[!id][j][h]+a[i]/(h+j+1);
                if(j != 0 and h != k){
                    dp[id][j][h] = min(dp[id][j][h], dp[!id][j-1][h+1] + b[i]/j);
                }
            }
        }

        sf.clear();
        for(int j=i+1;j<=n;j++){
            sf.pb(a[j]);
        }
        sort(all(sf));
        ld sum = 0;
        for(int j=0;j+1+i<=k;j++){
            sum += sf[j];
        }

        for(int j=0;j<=k;j++){
            ans = min(ans,dp[id][j][0] + sum/(j+1));
        }
    }

    cout<<setprecision(10)<<fixed<<ans<<endl;
}

• 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