結果
問題 | No.1391 ±1 Abs Sum |
ユーザー |
|
提出日時 | 2021-02-12 22:43:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,914 bytes |
コンパイル時間 | 929 ms |
コンパイル使用メモリ | 85,892 KB |
実行使用メモリ | 12,032 KB |
最終ジャッジ日時 | 2024-07-19 23:37:51 |
合計ジャッジ時間 | 5,174 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 WA * 3 TLE * 1 -- * 25 |
ソースコード
#include<iostream>#include<string>#include<iomanip>#include<cmath>#include<vector>#include<algorithm>#include<utility>#include<cassert>using namespace std;#define int long long#define endl "\n"constexpr long long INF = (long long)1e18;constexpr long long MOD = 1'000'000'007;struct fast_io {fast_io(){std::cin.tie(nullptr);std::ios::sync_with_stdio(false);};} fio;int f(const vector<int> &A, const vector<int> &B, int x){int sum = 0;int N = A.size();for(int i = 0; i < N; i++){sum += B[i] * abs(A[i] - x);}return sum;}int minf(const vector<int> &A, const vector<int> &B, int K){int sum = 0, res = INF;int N = A.size();int a = 0, b = 0;int ca = 0, cb = 0;int sa = 0, sb = 0;for(int i = 0; i < N; i++){if(B[i] > 0) {sa += A[i];} else {sb += A[i];}}for(int i = 0; i < N; i++){sum = 0;sum += (sa - a) - A[i] * (K - ca);sum -= (sb - b) - A[i] * (N - K - cb);sum += A[i] * ca - a;sum -= A[i] * cb - b;if(B[i] > 0) {ca++;a += A[i];} else {cb++;b += A[i];}assert(f(A, B, A[i]) == sum);res = min(res, sum);}return res;}void test(){int N, K;int res = INF;vector<int> A, B;cin>>N>>K;A.resize(N);B.resize(K, 1);for(int i = K; i < N; i++){B.push_back(-1);}for(int i = 0; i < N; i++){cin>>A[i];}res = minf(A, B, K);B.clear();B.resize(N - K, -1);for(int i = 0; i < K; i++){B.push_back(1);}res = min(res, minf(A, B, K));cout<<res<<endl;}signed main(){cout<<fixed<<setprecision(10);test();return 0;}