oj.uz

Submission #534270

# Submission time Handle Problem Language Result Execution time Memory
534270 2022-03-08T02:55:03 Z Cookie197 Let's Win the Election (JOI22_ho_t3) C++14
10 / 100
 33 ms 392 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<iomanip>
using namespace std;
#define ll long long
#define pii pair<int,int> 
#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

int n,k;
pii arr[505];
bool subtask1 = true, subtask2 = true;
signed main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>k;
    for (int i=0;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 (subtask1){
        sort(arr,arr+n);
        int ans = 0;
        for (int i=0;i<k;i++) ans+=arr[i].first;
        cout<<ans<<endl;
        return 0;
    }
    
    if (subtask2 || k==n){
        multiset<int> c,s,cc,ss;
        for (int i=0;i<n;i++) {
            if (arr[i].second==-1) ss.insert(arr[i].first);
            else cc.insert(arr[i].first);
        }
        double best = 1e9;
        for (int num=0;num<k;num++){
            c=cc,s=ss;
            int people = 1;
            double now = 0;
            if (num > c.size()) break;
            for (int i=0;i<num;i++){
                now += 1.0 * *(c.begin()) / people;
                people++;
                c.erase(c.begin());
            }
            for (int u:c) s.insert(u);

            for (int i=0;i<k-num;i++){
                now += 1.0 * *(s.begin()) / people;
                s.erase(s.begin());
            }
            best = min(best, now);
        }
        cout<<fixed<<setprecision(9)<<best<<endl;
        return 0;
    }

    

    if (n<=20){
        double best = 1e9;
        int ok[505];
        vector<int> collab,speech;
        for (int bit=0;bit<(1<<n);bit++){ // choose collaborators
            if (__builtin_popcount(bit) >= k) continue;
            double now = 0;
            collab.clear();
            for (int i=0;i<n;i++) ok[i] = false;
            int cnt = 0;
            for (int i=0;i<n;i++) if ((1<<i) & bit) if (arr[i].second != -1) collab.push_back(arr[i].second), ok[i] = true, cnt++;
            
            sort(collab.begin(),collab.end());
            int people = 1;
            for (double d:collab){
                now += d/people;
                people++;
            }

            speech.clear();
            for (int i=0;i<n;i++) if (!ok[i]) speech.push_back(arr[i].first);

            sort(speech.begin(),speech.end());
            for (int i=0;i<k-cnt;i++) now += 1.0 * speech[i] / people;

            best = min(best, now);
        }
        cout<<fixed<<setprecision(9)<<best<<endl;
        return 0;
    }


    

}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             if (num > c.size()) break;
      |                 ~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 8 ms 332 KB Output is correct
13 Correct 6 ms 332 KB Output is correct
14 Correct 4 ms 332 KB Output is correct
15 Correct 22 ms 392 KB Output is correct
16 Correct 14 ms 384 KB Output is correct
17 Correct 5 ms 332 KB Output is correct
18 Correct 24 ms 332 KB Output is correct
19 Correct 12 ms 332 KB Output is correct
20 Correct 6 ms 316 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 8 ms 332 KB Output is correct
13 Correct 6 ms 332 KB Output is correct
14 Correct 4 ms 332 KB Output is correct
15 Correct 22 ms 392 KB Output is correct
16 Correct 14 ms 384 KB Output is correct
17 Correct 5 ms 332 KB Output is correct
18 Correct 24 ms 332 KB Output is correct
19 Correct 12 ms 332 KB Output is correct
20 Correct 6 ms 316 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Incorrect 1 ms 204 KB Output isn't correct
28 Halted 0 ms 0 KB -