結果

問題 No.1391 ±1 Abs Sum
コンテスト
ユーザー eSeF
提出日時 2020-11-08 13:59:10
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 924 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,918 ms
コンパイル使用メモリ 198,396 KB
最終ジャッジ日時 2025-01-15 21:38:00
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
const ll inf = 4611686018427387903LL;
const int MOD=998244353;
int main()
{
  int N,K;
  cin >> N >> K;
  vector<ll>a(N);rep(i,N)cin >> a[i];
  ll ans=inf;
  int w=25;
  priority_queue<ll>q;
  for(int i=0;i<min(N,w);i++){
    rep(j,N)q.push(abs(a[i]-a[j]));
    ll s=0;
    rep(j,N){
      if(j<N-K)s-=q.top();
      else s+=q.top();
      q.pop();
    }
    ans=min(ans,s);
  }
  for(int i=N-1;i>=max(0,N-1-w);i--){
    rep(j,N)q.push(abs(a[i]-a[j]));
    ll s=0;
    rep(j,N){
      if(j<N-K)s-=q.top();
      else s+=q.top();
      q.pop();
    }
    ans=min(ans,s);
  }
  for(int i=max(0,N/2-w/2);i<min(N,N/2+w/2);i++){
    rep(j,N)q.push(abs(a[i]-a[j]));
    ll s=0;
    rep(j,N){
      if(j<N-K)s-=q.top();
      else s+=q.top();
      q.pop();
    }
    ans=min(ans,s);
  }
  cout << ans << endl;
  return 0;
}
0