結果
問題 |
No.738 平らな農地
|
ユーザー |
|
提出日時 | 2018-09-28 23:41:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 118 ms / 2,000 ms |
コード長 | 1,591 bytes |
コンパイル時間 | 1,811 ms |
コンパイル使用メモリ | 200,348 KB |
最終ジャッジ日時 | 2025-01-06 14:01:54 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 87 |
ソースコード
//================================= // Created on: 2018/09/28 23:16:26 //================================= #include <bits/stdc++.h> using ll = long long; int main() { int N, K; std::cin >> N >> K; std::vector<ll> A(N); for (int i = 0; i < N; i++) { std::cin >> A[i]; } if (K == 1) { return std::cout << 0 << std::endl, 0; } std::multiset<ll> a, b; ll sa = 0, sb = 0; const int H = K / 2; auto in = [&](const ll v) { if (a.size() < H) { a.insert(v); sa += v; } else { if (*a.rbegin() > v) { sa -= *a.rbegin(), sb += *a.rbegin(); b.insert(*a.rbegin()); auto it = a.end(); it--; a.erase(it); a.insert(v); sa += v; } else { b.insert(v); sb += v; } } }; auto out = [&](const ll v) { auto bit = b.find(v); if (bit != b.end()) { b.erase(bit); sb -= v; } else { sa -= v; a.erase(a.find(v)); auto it = b.begin(); sa += *it, sb -= *it; a.insert(*it), b.erase(it); } }; for (int i = 0; i < K; i++) { in(A[i]); } ll med = *b.begin(), ans = med * H - sa + sb - med * (K - H); for (int i = 0; i + K < N; i++) { out(A[i]), in(A[i + K]); const ll med = *b.begin(); ans = std::min(ans, med * H - sa + sb - med * (K - H)); } std::cout << ans << std::endl; return 0; }