# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1072321 | _rain_ | Let's Win the Election (JOI22_ho_t3) | C++14 | 2561 ms | 604 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fixbug true
void SETIO(string name = ""){
if (name=="") return;
freopen((name+".inp").c_str(),"r",stdin);
freopen((name+".ans").c_str(),"w+",stdout);
return;
}
const int maxn = 500;
const int maxk = 500;
const int INF = 1e9 + 7;
int n , k ;
pair<double,double> a[maxn+2];
#define fi first
#define se second
bool f[maxn+2];
vector<pair<int,int>> v;
double ans = INF;
vector<pair<int,int>> store;
void calc(int id){
if (id==k+1){
double cnt = 1 ;
double sum = 0;
for (int i = 0; i < v.size(); ++i){
if (v[i].se == 1) {
sum = sum + a[v[i].fi].fi / cnt;
}
else {
sum = sum + a[v[i].fi].se / cnt;
++cnt;
}
}
ans = min(ans , sum);
return;
}
for (int i = 0; i < n; ++i){
if (!f[i]){
f[i] = 1;
if (a[i].se != -1){
v.push_back({i,0});
calc(id+1);
v.pop_back();
}
v.push_back({i,1});
calc(id+1);
v.pop_back();
f[i] = 0;
}
}
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
SETIO("");
cin >> n >> k;
for (int i = 0; i < n; ++i) {
cin >> a[i].fi >> a[i].se;
if (a[i].se==-1) a[i].se = INF;
}
calc(1);
cout << setprecision(9) << fixed << ans;
}
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... |