Submission #1267729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267729		julia_08	Let's Win the Election (JOI22_ho_t3)	C++20	10 / 100	33 ms	328 KiB

Main

#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;

  vector<int> A;

  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;

    A.push_back(s[i].a);

  }

  sort(s + 1, s + n + 1);
  sort(A.begin(), A.end());

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

  ld ans = sum_a;

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

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

  return 0;
}

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