Submission #1267725

#TimeUsernameProblemLanguageResultExecution timeMemory
1267725julia_08Let's Win the Election (JOI22_ho_t3)C++20
0 / 100
33 ms328 KiB
#include <bits/stdc++.h>
#define int long long

using namespace std;

using ld = long double;

const int MAXN = 510;
const ld INF = 1e9;

struct state{

  ld a, b; int i; 

  bool operator < (state other){
    if(b != other.b) return b < other.b;
    if(a != other.a) return a > other.a;
    return i < other.i;
  }

} s[MAXN];

int n, k; 

ld solve(int i){

  ld sum_a = 0;

  vector<int> A;

  for(int j=(i + 1); j<=n; j++){
    A.push_back(s[j].a);
  }

  sort(A.begin(), A.end());

  for(int j=0; j<k-i; j++) sum_a += A[j];

  ld ans = INF;
    
  ld sum_b = 0;
  
  for(int j=1; j<=i; j++){

    if(s[j].b == INF) return INF;

    sum_b += s[j].b / j;

    ld cur_ans = 0;

    for(int k=(j + 1); k<=i; k++){
      cur_ans += s[k].a / (k - j);
    } 
 
    if(j == i) cur_ans = max(cur_ans, sum_a / (j + 1));
    else cur_ans = max(cur_ans, sum_a / j);

    ans = min(ans, cur_ans + sum_b);

  }

  return ans;

}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> k;

  ld ans = 0;

  for(int i=1; i<=n; i++){

    cin >> s[i].a >> s[i].b;
    s[i].i = i;

    if(s[i].b == -1) s[i].b = INF;

    ans += s[i].a;

  }

  sort(s + 1, s + n + 1);

  for(int i=1; i<=k; i++){
    ans = min(ans, solve(i));
  }

  cout << fixed << setprecision(10) << ans << "\n";

  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...