結果
問題 | No.1391 ±1 Abs Sum |
ユーザー |
|
提出日時 | 2021-02-12 23:04:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 1,301 bytes |
コンパイル時間 | 1,539 ms |
コンパイル使用メモリ | 167,296 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-20 00:28:40 |
合計ジャッジ時間 | 4,723 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include<bits/stdc++.h> // #include<atcoder/all> using namespace std; // using namespace atcoder; using lint = long long; template<class T>using graph = vector<vector<T>>; #define endl '\n' int const INF = 1<<30; lint const INF64 = 1LL<<62; lint const mod = 1e9+7; //long const mod = 998244353; int main(){ lint n,k; cin >> n >> k; lint a[n]; for(int i=0;i<n;i++)cin >> a[i]; lint summ = 0; lint plus = 0; for(int i=0;i<n;i++){ summ += abs(a[i] - a[0]); if(i<k)plus += abs(a[i]-a[0]); } int left = 0; int right = k-1; if(k==0)plus = 0; lint ans = plus*2 - summ; for(lint i=1;i<n;i++){ lint center = a[i]; lint diff = a[i] - a[i-1]; summ += (i - 1 - (n-1-i)) * diff; plus += (i - left - 1 - right + i) * diff; while(right < n-1){ if(k==0)break; if(abs(a[left] - center) > abs(a[right+1] - center)){ plus -= abs(a[left] - center); plus += abs(a[right+1] - center); left++; right++; }else{ break; } } // cout << plus << endl; if(k==0)plus = 0; ans = min(ans, plus*2 - summ); } cout << ans << endl; }