Submission #534676

#	Time	Username	Problem	Language	Result	Execution time	Memory
534676		Cookie197	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	1004 ms	2372 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[505][505][505];

// 看到第i個人，選了j個B類
double dp[505][505];

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;
    int good=n; 
    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 = 1e9, good--;
    }

    
    double best = 1e9;
    sort(arr+1,arr+1+n,comp);
    for (int goal=0;goal<=k;goal++){
        if (goal>good) continue;
        for (int i=0;i<=n+3;i++) for (int j=0;j<=n+3;j++) dp[i][j] = 1e9;
        dp[1][0] = 1.0*arr[1].first/(goal+1); dp[1][1] = arr[1].second; dp[0][0] = 0;

        for (int i=1;i<=k;i++) for (int j=0;j<=goal;j++){
            chmin(dp[i+1][j], dp[i][j] + 1.0*arr[i+1].first/(1+goal));
            if (arr[i].second != 1e9) chmin(dp[i+1][j+1], dp[i][j] + 1.0*arr[i+1].second/(1+j));
        }

        double now = 1e9;
        for (int pos=goal;pos<=k;pos++){ // position of last collaborator
            vector<int> tmp;
            for (int i=pos+1;i<=n;i++){ // 還要選k-pos個A類
                tmp.push_back(arr[i].first);
                //if (goal==0) cout<<pos<<" : "<<arr[i].first<<endl;
            }
            sort(tmp.begin(),tmp.end());
            double cost = 0;
            for (int i=0;i<k-pos;i++) cost += 1.0*tmp[i];
            cost /= (goal+1);
            now = min(now, cost + dp[pos][goal]);
        }
        best = min(now, best);
    }
    cout<<fixed<<setprecision(9)<<best<<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