# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1226839 | tgirolami09 | Let's Win the Election (JOI22_ho_t3) | C++20 | 2596 ms | 412 KiB |
#pragma GCC optimize("O2,unroll-loops")
#include <iostream>
#include <vector>
#include <algorithm>
#include <bit>
using namespace std;
struct group{
int first,second;
};
const bool compareSecond (group a, group b){
if (a.second==b.second){
return a.first<b.first;
}
else{
return a.second<b.second;
}
}
// void printVec(vector<group> v){
// for (auto i : v){
// printf("{%d,%d}, ",i.first,i.second);
// }
// printf("\n");
// }
int main(){
int nbStates;
int nbVotesNeeded;
scanf("%d",&nbStates);
scanf("%d",&nbVotesNeeded);
vector<group> states;
for (int i = 0;i<nbStates;++i){
int vote,help;
scanf("%d %d",&vote,&help);
states.push_back({vote,help});
}
sort(states.begin(),states.end(),compareSecond);
// printVec(states);
double bestTime = (1 << 30);
for (u_int32_t mask = 0;mask<(1<<nbStates);++mask){
if (__popcount(mask) > nbVotesNeeded){
continue;
}
// printf("Doing mask %d\n",mask);
vector<int> votes;
double currTime = 0;
int currVotes = 0;
int currHelpers = 1;
for (int i = 0;i<nbStates;++i){
if (mask & (1<<i) and states[i].second!=-1){
// printf("\t %d is set\n",i);
currTime += 1.0*states[i].second/(1.0*currHelpers);
++currVotes;
++currHelpers;
}
else{
votes.push_back(states[i].first);
}
}
if (currVotes<nbVotesNeeded){
sort(votes.begin(),votes.end());
int timeToadd = 0;
for (int i = 0;i<nbVotesNeeded-currVotes;++i){
timeToadd+=votes[i];
}
currTime += 1.0*timeToadd/(1.0*currHelpers);
}
// if (currTime<bestTime){
// bestTime = currTime;
// // printf("Best time with mask %d\n",(int)mask);
// }
bestTime = min(bestTime,currTime);
}
printf("%.3f\n",bestTime);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |