結果

問題 No.1391 ±1 Abs Sum
ユーザー okok
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0