Submission #1295495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295495		hssaan_arif	Let's Win the Election (JOI22_ho_t3)	C++20	0 / 100	2594 ms	340 KiB

Main

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

#define endl "\n"
#define pb push_back
#define fi first
#define dd long double
#define se second

const int N = 5e2 + 5, M = 1e9 + 7, LG = 20;

int n , A[N] , k;

dd x[N] , y[N];


void solve(){
    cin >> n >> k;
  
    for (int i=0 ; i<n ; i++){
        cin >> x[i] >> y[i];
        // if (y>=0){
        //     s.pb({y,i});
        //     u++;
        // }
        
        // t.pb({x,i});
    }
    dd ans = 1e9;
    for (int i=0 ; i<(1<<n) ; i++){
        dd cr = 0 , cm = 1;
        int h = 0;
        for (int j=0 ; j<n ; j++){
            if ((1<<j)&i){
                cr += (y[j]/cm);
                cm++;
                h++;
            }
        }
        vector<dd> f;
        for (int j=0 ; j<n ; j++){
            if (h >= k) break;
            if (!((1<<j)&i)){
                f.pb(x[j]/cm);
                
            }
        }
        sort(f.begin(),f.end());
        int in = 0;
        while(h < k){
            cr += f[in];
            h++;
            in++;
        }
        // if (cr == 0){
        //     cout << i << endl;
        // }
        // cout << cr << ' ' << i << endl;
        ans = min(ans , cr);
    }
    cout << ans << endl;
}

signed main(){
    // freopen("" , "r" , stdin);
    // freopen("" , "w" , stdout);
    cout << setprecision(30);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ts = 1;
    // cin >> ts;
    while(ts--){
        solve();
    }
}

• Subtask 1: 0 / 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