oj.uz

Submission #624158

# Submission time Handle Problem Language Result Execution time Memory
624158 2022-08-07T10:40:40 Z slime Let's Win the Election (JOI22_ho_t3) C++14
11 / 100
 2500 ms 993680 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 3e5 + 10;
const int MOD = 998244353;
#define ll __int128
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
ll read() { int x; cin >> x; return (ll)x; }
long long bm(long long b, long long p) {
  if(p==0) return 1 % MOD;
  long long r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
long long inv(long long b) { 
  return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) { 
  long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}
long long fib[MAXN], lucas[MAXN];
void precomp() { 
  for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD); 
  lucas[0] = 2;
  lucas[1] = 1;
  for(int i=2; i<MAXN; i++) lucas[i] = (lucas[i-2] + lucas[i-1]) % MOD;
  fib[0] = 0;
  fib[1] = 1;
  for(int i=2; i<MAXN; i++) fib[i] = (fib[i-2] + fib[i-1]) % MOD;
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void google(int i) { cout << "Case #" << i << ": "; }
int csb(int l, int r, int k) { // count number of [l, r] such that i & 2^k > 0
  if(l > r) return 0;
  if(l == 0) {
    int s = r / (1ll << (k+1)); // number of complete cycles
    int t = r % (1ll << (k+1));
    int ans = s * (1ll << k);
    ans += (t >= (1ll << k) ? t - (1ll << k) + 1 : 0);
    return ans;
  }
  else return csb(0, r, k) - csb(0, l - 1, k);
}
int lis(vector<int> a) {
  int n = a.size();
  int bucket[n+1];
  for(int i=1; i<=n; i++) bucket[i] = 1e18;
  int ans = 1;
  for(int x: a) {
    auto it = lower_bound(bucket + 1, bucket +n +1, x);
    int d = distance(bucket, it);
    ans = max(ans, d);
    bucket[d] = min(bucket[d], x);
  }
  return ans;
}
int n, k;
int a[MAXN], b[MAXN];
double compute_ans() {
  


  double dp[k+1][n+2][n+1];
  for(int i=0; i<=k; i++) for(int j=0; j<n+2; j++) for(int l=0; l<n+1; l++) dp[i][j][l] = 1e18;
  dp[0][1][0] = 0;
  for(int i=1; i<=k; i++) {
    for(int j=1; j<=n+1; j++) {
      for(int l=1; l<=n; l++) {
        // include l, 'A'
        dp[i][j][l] = dp[i-1][j][l-1] + a[l] * 1.0 / j;
        // include l, 'B'
        if(b[l] != 1226 && j > 1) dp[i][j][l] = min(dp[i][j][l], dp[i-1][j-1][l-1] + b[l] * 1.0 / (j-1));
        // don't include l
        dp[i][j][l] = min(dp[i][j][l], dp[i][j][l-1]);
      }
    }
  }
  double ans = 1e18;
  for(int i=1; i<=n+1; i++) ans = min(ans, dp[k][i][n]);
  return ans;
  cout << fixed << setprecision(6) << ans << "\n";
}
void solve(int tc) {
  cin >> n >> k;
  pair<int, int> p[n+1];
  for(int i=1; i<=n; i++) {
    cin >> p[i].first >> p[i].second;
    if(p[i].second == -1) p[i].second = 1226;
  }
  sort(p+1, p+n+1);
  double ans = 1e18;
  do {
    for(int i=1; i<=n; i++) a[i] = p[i].first, b[i] = p[i].second;
    ans = min(ans, compute_ans());
    
  } while(next_permutation(p+1, p+n+1));
  cout << fixed << setprecision(10) << ans << "\n";
  

} 
int32_t main() {
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// I don't know geometry.
// Teaming is unfair.

/*
7
5
31 33 (2)
19 27 (8)
28 36 (8)
38 51 (13)
20 35 (15)
25 56 (31)
11 57 (46)

7
5
19 27
31 33
20 35
28 36
38 51
25 56
11 57

optimal order:
7
5
19 27
31 33
28 36
38 51
25 56
11 57
20 35
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7380 KB Output is correct
2 Correct 8 ms 7336 KB Output is correct
3 Correct 7 ms 7380 KB Output is correct
4 Correct 7 ms 7380 KB Output is correct
5 Execution timed out 2556 ms 107724 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7380 KB Output is correct
2 Correct 8 ms 7336 KB Output is correct
3 Correct 7 ms 7380 KB Output is correct
4 Correct 7 ms 7380 KB Output is correct
5 Execution timed out 2556 ms 107724 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7380 KB Output is correct
2 Correct 11 ms 7292 KB Output is correct
3 Correct 11 ms 7288 KB Output is correct
4 Correct 13 ms 7384 KB Output is correct
5 Correct 14 ms 7292 KB Output is correct
6 Correct 14 ms 7380 KB Output is correct
7 Correct 16 ms 7380 KB Output is correct
8 Correct 14 ms 7380 KB Output is correct
9 Correct 14 ms 7384 KB Output is correct
10 Correct 13 ms 7380 KB Output is correct
11 Correct 14 ms 7380 KB Output is correct
12 Correct 13 ms 7384 KB Output is correct
13 Correct 13 ms 7376 KB Output is correct
14 Correct 7 ms 7380 KB Output is correct
15 Correct 17 ms 7384 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7380 KB Output is correct
2 Correct 11 ms 7292 KB Output is correct
3 Correct 11 ms 7288 KB Output is correct
4 Correct 13 ms 7384 KB Output is correct
5 Correct 14 ms 7292 KB Output is correct
6 Correct 14 ms 7380 KB Output is correct
7 Correct 16 ms 7380 KB Output is correct
8 Correct 14 ms 7380 KB Output is correct
9 Correct 14 ms 7384 KB Output is correct
10 Correct 13 ms 7380 KB Output is correct
11 Correct 14 ms 7380 KB Output is correct
12 Correct 13 ms 7384 KB Output is correct
13 Correct 13 ms 7376 KB Output is correct
14 Correct 7 ms 7380 KB Output is correct
15 Correct 17 ms 7384 KB Output is correct
16 Execution timed out 2592 ms 7380 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7380 KB Output is correct
2 Correct 11 ms 7292 KB Output is correct
3 Correct 11 ms 7288 KB Output is correct
4 Correct 13 ms 7384 KB Output is correct
5 Correct 14 ms 7292 KB Output is correct
6 Correct 14 ms 7380 KB Output is correct
7 Correct 16 ms 7380 KB Output is correct
8 Correct 14 ms 7380 KB Output is correct
9 Correct 14 ms 7384 KB Output is correct
10 Correct 13 ms 7380 KB Output is correct
11 Correct 14 ms 7380 KB Output is correct
12 Correct 13 ms 7384 KB Output is correct
13 Correct 13 ms 7376 KB Output is correct
14 Correct 7 ms 7380 KB Output is correct
15 Correct 17 ms 7384 KB Output is correct
16 Execution timed out 2592 ms 7380 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2622 ms 993680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7380 KB Output is correct
2 Correct 8 ms 7336 KB Output is correct
3 Correct 7 ms 7380 KB Output is correct
4 Correct 7 ms 7380 KB Output is correct
5 Execution timed out 2556 ms 107724 KB Time limit exceeded
6 Halted 0 ms 0 KB -