結果
問題 | No.1391 ±1 Abs Sum |
ユーザー |
![]() |
提出日時 | 2021-02-12 23:08:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,910 bytes |
コンパイル時間 | 2,880 ms |
コンパイル使用メモリ | 197,316 KB |
最終ジャッジ日時 | 2025-01-18 19:39:26 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 WA * 13 |
ソースコード
// #pragma GCC target("avx2")// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>#define rep(i, n) for (int i = 0; i < (int)n; ++i)#define rrep(i, n) for (int i = (int)n - 1; i >= 0; --i)#define ALL(v) v.begin(), v.end()#define pb push_back#define eb emplace_back#define fi first#define se secondusing namespace std;using ll = long long;using ld = long double;const array<int, 8> di = {0, 1, 0, -1, 1, 1, -1, -1}, dj = {1, 0, -1, 0, 1, -1, -1, 1};const array<string, 2> YESNO = {"NO", "YES"};const array<string, 2> YesNo = {"No", "Yes"};const array<string, 2> yesno = {"no", "yes"};void YES(bool b = true) { cout << YESNO[b] << '\n'; }void Yes(bool b = true) { cout << YesNo[b] << '\n'; }void yes(bool b = true) { cout << yesno[b] << '\n'; }template<typename T, typename U>inline bool chmax(T& a, const U& b) {if (a < b){a = b;return true;}return false;}template<typename T, typename U>inline bool chmin(T& a, const U& b) {if (a > b) {a = b;return true;}return false;}template<typename T>T MAX(const vector<T>& v) { return *max_element(v.begin(), v.end()); }template<typename T>T MIN(const vector<T>& v) { return *min_element(v.begin(), v.end()); }template<typename T>T SUM(const vector<T>& v) { return accumulate(v.begin(), v.end(), T()); }template<typename T>void UNIQUE(vector<T>& v) {sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());}template<typename T>T POW(T a, int n) {T res = 1;for (; n > 0; n >>= 1, a *= a) if (n & 1) res *= a;return res;}template<typename T>int lb(const vector<T>& v, T x) {return distance(v.begin(), lower_bound(v.begin(), v.end(), x));}template<typename T>int ub(const vector<T>& v, T x) {return distance(v.begin(), upper_bound(v.begin(), v.end(), x));}/*** @brief 多次元 vector の作成* @author えびちゃん*/namespace detail {template<typename T, int N>auto make_vec(vector<int>& sizes, T const& x) {if constexpr (N == 1) {return vector(sizes[0], x);} else {int size = sizes[N-1];sizes.pop_back();return vector(size, make_vec<T, N-1>(sizes, x));}}}template<typename T, int N>auto make_vec(int const(&sizes)[N], T const& x = T()) {vector<int> s(N);for (int i = 0; i < N; ++i) s[i] = sizes[N-i-1];return detail::make_vec<T, N>(s, x);}template<typename T>ostream& operator<<(ostream& os, const vector<T>& v) {for (auto it = v.begin(); it != v.end(); ++it) {if (it == v.begin()) os << *it;else os << ' ' << *it;}return os;}template<typename T, typename U>ostream& operator<<(ostream& os, const pair<T, U>& p) {os << p.first << ' ' << p.second;return os;}__attribute__((constructor))void setup() {ios::sync_with_stdio(false);cin.tie(nullptr);cout << fixed << setprecision(15);}// #include <atcoder/all>// using namespace atcoder;// using mint = modint1000000007;// using mint = modint998244353;int main() {int n, k;cin >> n >> k;vector<ll> a(n);rep(i, n) cin >> a[i];ll ans = LLONG_MAX;rep(t, 2) {ll now = 0;rep(i, n) {if (i < n-k) now += -abs(a[0] - a[i]);else now += abs(a[0] - a[i]);}chmin(ans, now);for (int i = 0; i < n-1; ++i) {ll d = a[i+1] - a[i];if (i < n-k) {now -= d * (i+1);now += d * (n-k-i-1);now -= d * k;} else {now -= d * (n-k);now += d * (i-(n-k)+1);now -= d * (n-1-i);}chmin(ans, now);}reverse(ALL(a));rep(i, n) a[i] = -a[i];}cout << ans << '\n';}