結果
問題 |
No.1391 ±1 Abs Sum
|
ユーザー |
![]() |
提出日時 | 2021-02-13 15:08:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 82 ms / 2,000 ms |
コード長 | 1,584 bytes |
コンパイル時間 | 1,746 ms |
コンパイル使用メモリ | 168,760 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 17:55:54 |
合計ジャッジ時間 | 4,390 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<n;i++) using namespace std; typedef long long ll; const ll inf = 4611686018427387903LL; const int MOD=998244353; int main(){ int N,K; cin >> N >> K; vector<ll> a(N); rep(i, N) cin >> a[i]; int l = 0; int r = K - 1; //[l, r] を +1 にする ll ans = inf; ll now = 0; rep(i,N){ if(l <= i && i <= r) now += abs(a[0] - a[i]); else now -= abs(a[0] - a[i]); } rep(i,N){ // x = A[i] while(r < i || (r + 1 < N && abs(a[l] - a[i]) > abs(a[r + 1] - a[i]))){ // 得をするので動かす now = now - 2 * abs(a[l] - a[i]) + 2 * abs(a[r + 1] - a[i]); l++; r++; } ans = min(ans, now); // i を一つ進める // now += l * a[i]; // now -= max(0, i - l) * a[i]; // now += max(0, r - (i + 1) + 1 ) * a[i]; // now -= max(0, N - 1 - (r + 1) + 1) * a[i]; //xの値を入れ替える // [0, l-1]、[i+1, r]ではxの符号は +、それ以外では - now -= (i - l + 1 + N - 1 - r - (l + (r - i))) * a[i]; if(i + 1 < N){ // now -= l * a[i + 1]; // now += max(0, i - l) * a[i + 1]; // now -= max(0, r - (i + 1 + 1) + 1 ) * a[i + 1]; // now += max(0, N - 1 - (r + 1) + 1) * a[i+ 1]; //次のx now += (i - l + 1 + N - r - (l + (r - i - 1))) * a[i + 1]; now += -2 * a[i + 1]; } } cout << ans << endl; return 0; }