結果
問題 | No.738 平らな農地 |
ユーザー |
![]() |
提出日時 | 2018-09-28 21:54:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 85 ms / 2,000 ms |
コード長 | 2,340 bytes |
コンパイル時間 | 2,188 ms |
コンパイル使用メモリ | 202,764 KB |
最終ジャッジ日時 | 2025-01-06 13:54:40 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 87 |
ソースコード
#include<bits/stdc++.h> using namespace std; using P = pair<int, int>; int main() { int n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; priority_queue<P> lower; priority_queue<P, vector<P>, greater<P>> upper; long long lower_sum = 0, upper_sum = 0; for (int i = 0; i < k; ++i) { upper.push(P(a[i], i)); upper_sum += a[i]; } while (lower.size() < upper.size()) { lower_sum += upper.top().first; upper_sum -= upper.top().first; lower.push(upper.top()); upper.pop(); } int lc = lower.size(); int uc = upper.size(); long long ans = 1e18; for (int i = k - 1; i < n; ++i) { if (i >= k) { if (P(a[i - k], i - k) > lower.top()) { --uc; upper_sum -= a[i - k]; } else { --lc; lower_sum -= a[i - k]; } P p = P(a[i], i); if (lower.top() > p) { ++lc; lower.push(p); lower_sum += a[i]; } else { ++uc; upper.push(p); upper_sum += a[i]; } while (lc > uc + 1) { if (lower.top().second <= i - k) { lower.pop(); continue; } upper_sum += lower.top().first; lower_sum -= lower.top().first; ++uc; upper.push(lower.top()); --lc; lower.pop(); } while (lc < uc) { if (upper.top().second <= i - k) { upper.pop(); continue; } lower_sum += upper.top().first; upper_sum -= upper.top().first; ++lc; lower.push(upper.top()); --uc; upper.pop(); } } while (lower.top().second <= i - k) { lower.pop(); } long long m = lower.top().first; ans = min(ans, m * lc - lower_sum + upper_sum - m * uc); // cout << m * lc - lower_sum + upper_sum - m * uc << "\n"; } cout << ans << "\n"; return 0; }