結果
問題 | No.738 平らな農地 |
ユーザー |
![]() |
提出日時 | 2019-02-23 18:27:10 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 91 ms / 2,000 ms |
コード長 | 2,030 bytes |
コンパイル時間 | 688 ms |
コンパイル使用メモリ | 78,992 KB |
実行使用メモリ | 8,576 KB |
最終ジャッジ日時 | 2024-11-30 22:04:10 |
合計ジャッジ時間 | 7,158 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 87 |
ソースコード
#include <iostream>#include <algorithm>#include <cstring>#include <sstream>#include <map>#include <queue>#include <set>#include <vector>#include <stack>#include <cstdio>#include <cmath>#define mk make_pair#define pb push_back#define printf printf_s#define scanf scanf_susing namespace std;typedef long long int ll;typedef pair<ll, ll> pos;const ll MOD = 1000000007, N = 200010, dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }, MIN = -72340172838076673, MAX = 72340172838076673;ll mn(ll a, ll b) {if (a == -1)return b;if (b == -1)return a;return min(a, b);}ll gcd(ll v1, ll v2) {if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);}ll pw(ll v1, ll v2) {ll v3 = 1;while (v2 > 0) {if (v2 % 2)v3 = (v3*v1) % MOD;v1 = (v1*v1) % MOD;v2 /= 2;}return v3;}struct ab {ll a, b;bool operator<(const ab& right) const {return right.b*a - right.a*b < 0;}};ll n, k,a[N],sv1=0,sv2=0;multiset<ll> st1, st2;void ev() {while (st1.size() > st2.size() + 1) {ll v1 = *st1.begin();sv1 -= v1;st2.insert(-v1);sv2 += -v1;st1.erase(st1.begin());}while (st1.size() < st2.size()) {ll v1 = *st2.begin();sv1 += -v1;sv2 -= v1;st2.erase(st2.begin());st1.insert(-v1);}while(!st2.empty()&&-*st1.begin()>*st2.begin()) {ll v1 = *st1.begin(),v2=*st2.begin();sv1 += -v1 - v2;sv2 += -v1 - v2;st1.erase(st1.begin());st2.erase(st2.begin());st1.insert(-v2);st2.insert(-v1);}}void ad(ll v1) {st1.insert(-v1); sv1 += -v1;ev();}void dl(ll v1) {if (!st2.empty()&&*st2.begin() <= v1) {sv2 -= v1;st2.erase(st2.find(v1));}else {sv1 += v1;st1.erase(st1.find(-v1));}ev();}ll ans = -1;int main() {cin >> n >> k;for (int i = 1; i <= n; i++) {cin >> a[i];ad(a[i]);if (i > k) { dl(a[i - k]); }if (i >= k) {ll v1 = -*st1.begin()*st1.size() + sv1;v1 += sv2 - (-*st1.begin()*st2.size());ans = mn(ans, v1);}}cout << ans << endl;return 0;}