結果
問題 | No.1391 ±1 Abs Sum |
ユーザー |
![]() |
提出日時 | 2021-02-13 16:10:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 945 bytes |
コンパイル時間 | 1,128 ms |
コンパイル使用メモリ | 93,220 KB |
最終ジャッジ日時 | 2025-01-18 20:08:39 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <iostream>#include <vector>#include <string>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>using namespace std;using ll = long long;int main() {ios::sync_with_stdio(false);cin.tie(0);int n, k;cin >> n >> k;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}vector<ll> s(n + 1, 0);for (int i = 0; i < n; i++) {s[i + 1] = s[i] + a[i];}ll r = 1LL << 60;int l = 0;for (int i = 0; i < n; i++) {ll x = a[i];while (l + k < n && abs(x - a[l]) > abs(x - a[l + k])) l++;ll t = 0;if (l < i) t += -(s[min(i, l + k)] - s[l]) + x * (min(i, l + k) - l);if (l + k > i) t += (s[l + k] - s[max(i, l)]) - x * (l + k - max(i, l));t *= 2;t -= (s[n] - s[i]) - x * (n - i) - (s[i] - s[0]) + x * i;r = min(r, t);}cout << r << endl;return 0;}