Submission #1245295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245295		nasjes	Let's Win the Election (JOI22_ho_t3)	C++20	21 / 100	238 ms	5164 KiB

Main

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 3*1e3+7;
//const ll mod = 1e9 + 7;
const ld inf = 10000000;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, m;
pll a[dim];
ld dp[600][600];
int main() {
    ll t, u0, v0;
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        cin>>a[i].se>>a[i].fi;// se- a fi-b
        if(a[i].fi==-1)a[i].fi=inf;
    }
    for(int i=0; i<=n; i++){
        for(int j=1; j<=n; j++){
            dp[i][j]=(ld)inf;
        }
    }
    for(int i=0; i<=n; i++){
        dp[i][0]=(ld)0;
    }
    sort(a+1, a+1+n);
    multiset<ll> op;
    ld ans=(ld)inf;
   for(int i=1; i<=n; i++){
        ll sum=0;
        op.clear();
        for(int j=i+1; j<=n; j++){
            op.insert(a[j].se);
        }
        for(int j=i+1; j<=m; j++){
            sum+=(*op.begin());
            op.erase(op.begin());
        }
        for(int k=m; k>=0; k--){
            for(int j=k; j>=1; j--){
                ld op1=+(ld)a[i].se/ (ld)(k+1);
                ld op2=+(ld)a[i].fi/ (ld)j;
                dp[k][j]=min<ld>(dp[k][j]+op1, dp[k][j-1]+op2);
            }
            dp[k][0]=dp[k][0]+(ld)(a[i].se)/(ld)(k+1);
            if(k==0){
              //  cout<<dp[0][0]<<endl;
            }
             ans=min<ld>(ans, dp[k][k] +(ld)sum/(k+1));
        }

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

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 11 / 11
• Subtask 7: 0 / 23