제출 #157011

#제출 시각아이디문제언어결과실행 시간메모리
157011DrumpfTheGodEmperorCake 3 (JOI19_cake3)C++14
0 / 100
2 ms376 KiB
#include <bits/stdc++.h> #define int long long #define bp __builtin_popcountll #define pb push_back #define in(s) freopen(s, "r", stdin); #define out(s) freopen(s, "w", stdout); #define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\ freopen((string(s) + "." + end2).c_str(), "w", stdout); #define fi first #define se second #define bw(i, r, l) for (int i = r - 1; i >= l; i--) #define fw(i, l, r) for (int i = l; i < r; i++) #define fa(i, x) for (auto i: x) using namespace std; const double EPS = 1e-6; const int mod = 1e9 + 7, inf = 1061109567; const long long infll = 4557430888798830399; const int N = 2e5 + 5; int n, k, ans[N]; struct Cake { int v, c; bool operator<(const Cake &rhs) const { return c < rhs.c; } } c[N]; double ansOut = 0; double v2[N], sumV[N], cnt[N]; int solve(double penalty) { fw (i, 0, n) v2[i] = c[i].v, v2[i] -= penalty; fw (i, 0, n) { sumV[i] = (i ? sumV[i - 1] : 0); cnt[i] = (i ? cnt[i - 1] : 0); if (v2[i] > 0) { sumV[i] += v2[i]; cnt[i]++; } } int mxL = -1, ansL, ansR; double mx = -infll, ans = -infll; fw (i, 0, n) { //l and r must be at least 3 elements apart. double val = (i ? sumV[i - 1] : 0) + v2[i] - 2 * c[i].c; if (val + mx > ans) { ans = val + mx; ansL = mxL; ansR = i; } if (v2[i] - sumV[i] + 2 * c[i].c > mx) { mx = v2[i] - sumV[i] + 2 * c[i].c; mxL = i; } } ansOut = ans; return (ansR ? cnt[ansR - 1] : 0) - cnt[ansL] + 2; } double bs(double l, double r) { if (l + EPS > r) return l; double m = (l + r) / 2; int lol = solve(m); if (lol > k) return bs(m, r); //Increase penalty to pick less elements return bs(l, m); } signed main() { #ifdef BLU in("blu.inp"); #endif ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> k; fw (i, 0, n) cin >> c[i].v >> c[i].c; sort(c, c + n); //Minimum sum of depth differences is 2 * (max - min) //Use Alien's trick: Add a penalty for each piece taken until the number of pieces is exactly K. double optPenalty = bs(-2e9, 2e9); solve(optPenalty); cout << (long long)(ansOut + optPenalty * k); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

cake3.cpp: In function 'long long int solve(double)':
cake3.cpp:54:26: warning: 'ansR' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return (ansR ? cnt[ansR - 1] : 0) - cnt[ansL] + 2;
                     ~~~~~^~~
cake3.cpp:54:46: warning: 'ansL' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return (ansR ? cnt[ansR - 1] : 0) - cnt[ansL] + 2;
                                      ~~~~~~~~^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...