Submission #824516

#	Time	Username	Problem	Language	Result	Execution time	Memory
824516		peteza	Let's Win the Election (JOI22_ho_t3)	C++14	21 / 100	679 ms	312 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
bool vis[505];
int n, k;
int as, bs;
vector<pair<int, int>> a, b;
 
int todo=0,ptr=0;
long double cans=1e18, ans = 1e18, csum = 0;
vector<int> vec;
int av[1005], bv[1005];

int main() {
    cin >> n >> k;
    for(int i=0;i<n;i++) {
        cin >> as >> bs; av[i] = as; bv[i] = bs;
        a.emplace_back(as, i);
        if(bs!=-1) b.emplace_back(bs, i);
        vec.push_back(i);
    }
    sort(vec.begin(), vec.end(), [&](int i, int j){
        if(bv[i] == -1) return (bool)0;
        if(bv[j] == -1) return (bool)1;
        if(bv[i]-av[i] == bv[j]-av[j]) return av[i] > av[j];
        return bv[j]-av[i] > bv[j]-av[j];
    });
    //blablbalbllba
    sort(b.begin(), b.end());
    for(int K=0;K<1000;K++) {
        ans = 1e18; csum = 0;
        sort(a.begin(), a.end());
        for(int selb=0;selb<=b.size();selb++) {
            vector<bool> vis(n, 0);
            todo = k; csum = 0; ptr = 0;
            bool broke = 0;
            for(int i=0;i<selb;i++) {
                if(b[i].first == INT_MAX) broke = 1;
                vis[b[i].second] = 1;
                csum += 1.00*b[i].first/(i+1); todo--;
            }
            if(broke) break;
            while(ptr<n&&todo > 0){
                if(vis[a[ptr].second]){ptr++; continue;}
                csum += 1.00*a[ptr].first/(selb+1);
                todo--; ptr++;
            }
            if(todo<=0) ans = min(ans, csum);
        }
        cans = min(cans, ans);
        random_shuffle(b.begin(), b.end());
    }
    cout << cans;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:33:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int selb=0;selb<=b.size();selb++) {
      |                        ~~~~^~~~~~~~~~

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