Submission #534383

#	Time	Username	Problem	Language	Result	Execution time	Memory
534383		Cookie197	Let's Win the Election (JOI22_ho_t3)	C++14	5 / 100	13 ms	18636 KiB

Main

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<iomanip>
using namespace std;
#define ll long long
#define pii pair<ll,ll> 
#define mp make_pair
#define endl "\n"
#define out(x) cout << #x << " = " << x << endl
#define outp(x) cout << #x << ".first = " << x.first << "  " << #x << ".second = " << x.second << endl
#pragma GCC optimize("Ofast")
#define lll __int128

// enumerate the num of collaborators, from 0 to k-1
// it is optimal to collect all collaborators first, then give speeches
// if we know which collaborators to choose, it's better to choose the ones with smaller b first
void chmin(double &a, double x){
    if (x<a) a=x;
}
ll n,k;
pii arr[505];
bool subtask1 = true, subtask2 = true;
// 看到第i個人，拿到了j票，目前people = p，最少時間
double dp[105][105][105];

bool comp(pii a, pii b){
    if (a.second != b.second) return a.second < b.second;
    return a.first < b.first;
}
signed main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>k;
    for (int i=1;i<=n;i++) {
        cin>>arr[i].first>>arr[i].second;
        if (arr[i].second != -1) subtask1 = false;
        if (arr[i].second != -1 && arr[i].second != arr[i].first) subtask2 = false;
        if (arr[i].second == -1) arr[i].second = 1e9;
    }

    if (subtask1){
        sort(arr+1,arr+n+1);
        int ans = 0;
        for (int i=1;i<=k;i++) ans+=arr[i].first;
        cout<<ans<<endl;
        return 0;
    }

    sort(arr+1,arr+1+n,comp);
    double best = 1e15;
    for (ll goalp=1;goalp<=k;goalp++){ // 枚舉要選幾個collab
        for (int i=1;i<=n;i++) for (int j=0;j<=100;j++) for (int p=0;p<=100;p++) dp[i][j][p] = 1e15;
        dp[1][0][1] = 0; dp[1][1][1] = arr[1].first/goalp; dp[1][1][2] = arr[1].second;
        for (ll i=1;i<=n;i++) for (int j=0;j<=i;j++) for (int p=1;p<=min(goalp,i+1);p++){
            //cout<<i<<"  "<<j<<"  "<<p<<"   "<<dp[i][j][p]<<endl;
            chmin(dp[i+1][j][p], dp[i][j][p]);
            chmin(dp[i+1][j+1][p], dp[i][j][p] + 1.0*arr[i+1].first/goalp); // 「只拿到票的」要等拿完所有collab再選
            if (arr[i+1].second != 1e9) chmin(dp[i+1][j+1][p+1], dp[i][j][p] + 1.0*arr[i+1].second/p);
        }
        best = min(best, dp[n][k][goalp]);
    }

    
    cout<<fixed<<setprecision(13);
    cout<<best<<endl;
}

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