Submission #624254

#TimeUsernameProblemLanguageResultExecution timeMemory
624254slimeLet's Win the Election (JOI22_ho_t3)C++14
61 / 100
2588 ms254440 KiB
#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; } bool cmp(pair<int, int> x, pair<int, int> y) { return x.second < y.second; } int n, k, a[MAXN], b[MAXN]; double fun(int bcnt) { double dp[k - bcnt + 1][bcnt + 1][n + 1]; // type A, type B, prefix for(int i=0; i<=k-bcnt; i++) { for(int j=0; j<=bcnt; j++) { for(int l=0; l<=n; l++) { dp[i][j][l] = 1e9; } } } for(int i=0; i<=n; i++) dp[0][0][i] = 0; for(int i=0; i<=k-bcnt; i++) { for(int j=0; j<=bcnt; j++) { if(i == 0 && j == 0) continue; for(int l=1; l<=n; l++) { // register as type A if(i > 0) dp[i][j][l] = dp[i-1][j][l-1] + a[l] * 1.0 / (bcnt + 1); // register as type B if(j > 0 && b[l] != 1226) dp[i][j][l] = min(dp[i][j][l], dp[i][j-1][l-1] + b[l] * 1.0 / j); // register as neither dp[i][j][l] = min(dp[i][j][l], dp[i][j][l-1]); } } } return dp[k-bcnt][bcnt][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, cmp); for(int i=1; i<=n; i++) { a[i] = p[i].first, b[i] = p[i].second; } int lb = 0, rb = k; while(lb < rb) { int mid = (lb + rb) >> 1; if(fun(mid) > fun(mid+1)) lb = mid+1; else rb = mid; } cout << fixed << setprecision(10) << fun(lb) << "\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. /* 8 7 3 15 19 40 11 62 7 72 16 27 33 53 14 50 17 24 */

Compilation message (stderr)

Main.cpp: In function 'int lis(std::vector<int>)':
Main.cpp:54:39: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   54 |   for(int i=1; i<=n; i++) bucket[i] = 1e18;
      |                                       ^~~~
#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...