結果

問題 No.1391 ±1 Abs Sum
ユーザー gunmaneko
提出日時 2021-02-12 23:19:03
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 7,675 bytes
コンパイル時間 1,908 ms
コンパイル使用メモリ 180,452 KB
実行使用メモリ 5,584 KB
最終ジャッジ日時 2024-07-20 00:56:41
合計ジャッジ時間 5,059 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 17 WA * 17
権限があれば一括ダウンロードができます

ソースコード

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

#include "bits/stdc++.h"
//#include <atcoder/all>
//using namespace atcoder;
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;
const long long INF = 1LL << 60;
long long fac[MAX], finv[MAX], inv[MAX];
//
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++) {
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
//
long long COM(int n, int k) {
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/**/
long long int maxtime(long long int x, long long int y) {
return(x + y - 1) / y;
}
/**/
long long int lcm(long long int number1, long long int number2) {
long long int m = number1;
long long int n = number2;
if (number2 > number1) {
m = number2;
n = number1;
}
long long int s = -1;
while (s != 0) {
s = m % n;
m = n;
n = s;
}
return m;
}
/**/
long long int gcd(long long int number1, long long int number2) {
long long int m = number1;
long long int n = number2;
return m / lcm(m, n) * n;
}
/**/
long long int modinv(long long a, long long m) {
long long int b = m, u = 1, v = 0;
while (b) {
long long int t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
u %= m;
if (u < 0) u += m;
return u;
}
long long mod(long long val, long long m) {
long long res = val % m;
if (res < 0) res += m;
return res;
}
//()
const int MAX_N = 10000000;
//
int n,dat[2*MAX_N - 1];
//
void init(int n_){
//
n = 1;
while(n < n_) {
n *= 2;
}
//INT_MAX
for(int i = 0; i < 2 * n - 1; i++){
//dat[i] = INT_MAX;
dat[i] = 0;
}
}
// k(0-indexed)a
void update(int k,int a){
//
k += n - 1;
dat[k] = a;
//
while(k > 0){
k = (k - 1) / 2;
dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2]);
}
}
// [a, b)
// 
//k, l, r[l, r)
// query(a, b, 0, 0, n)
int query(int a, int b, int k = 0, int l = 0, int r = n){
// [a, b)[l, r)INT_MAX
if (r <= a || b <= l){
return 0;
}
// [a, b)[l, r)
if (a <= l && r <= b){
return dat[k];
}else{
//2
int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
return max(vl,vr);
}
}
//Union-Find 
int par[MAX_N]; //
int ranks[MAX_N]; //
//n
void initunion(int n){
for(int i = 0;i < n;i++){
par[i] = i;
ranks[i] = 0;
}
}
//
int find(int x){
if (par[x] == x){
return x;
}else{
return par[x] = find(par[x]);
}
}
//xy
void unite(int x,int y){
x = find(x);
y = find(y);
if(x == y){
return;
}
if(ranks[x] < ranks[y]){
par[x] = y;
}else{
par[y] = x;
if(ranks[x] == ranks[y]){
ranks[x]++;
}
}
}
//xy
bool same(int x,int y){
return find(x) == find(y);
}
//
// index
vector<long long int >meguru;
// index
bool isOK(int index, int key) {
if (meguru[index] >= key) return true;
else return false;
}
//
int binary_search(int key) {
int left = -1; //index = 0 -1
int right = (int)meguru.size(); // index = a.size()-1 a.size()
/* */
while (right - left > 1) {
int mid = left + (right - left) / 2;
if (isOK(mid, key)) right = mid;
else left = mid;
}
/* left right */
return right;
}
long long modpow(long long a, long long n, long long mod) {
long long res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
struct Edge {
long long to;
long long cost;
};
using Graph = vector<vector<Edge>>;
using P = pair<long, int>;
/* dijkstra(G,s,dis)
G, s, dis
O(|E|log|V|)
dis
*/
void dijkstra(const Graph &G, int s, vector<long long> &dis) {
int N = G.size();
dis.resize(N, INF);
priority_queue<P, vector<P>, greater<P>> pq; // ,
dis[s] = 0;
pq.emplace(dis[s], s);
while (!pq.empty()) {
P p = pq.top();
pq.pop();
int v = p.second;
if (dis[v] < p.first) { //
continue;
}
for (auto &e : G[v]) {
if (dis[e.to] > dis[v] + e.cost) { // priority_queue
dis[e.to] = dis[v] + e.cost;
pq.emplace(dis[e.to], e.to);
}
}
}
}
int main(){
long long int n,k;
cin >> n >> k;
vector<long long int >av;
for(long long int i = 0;i < n;i++){
long long int a;
cin >> a;
av.push_back(a);
}
long long int tmp = (n-(n-k)*2+1)/2;
tmp = max(0ll,tmp);
long long int x = av[tmp];
long long int ans = INF;
long long int sum = 0;
long long int count = k;
for(long long int i = 0;i < n;i++){
if(count > 0){
sum = sum + abs(x-av[i]);
count--;
}else{
sum = sum - abs(x-av[i]);
}
}
ans = min(ans,sum);
reverse(av.begin(),av.end());
count = k;
sum = 0;
x = av[tmp];
for(long long int i = 0;i < n;i++){
if(count > 0){
sum = sum + abs(x-av[i]);
count--;
}else{
sum = sum - abs(x-av[i]);
}
}
ans = min(ans,sum);
count = k;
sum = 0;
x = av[tmp+1];
for(long long int i = 0;i < n;i++){
if(count > 0){
sum = sum + abs(x-av[i]);
count--;
}else{
sum = sum - abs(x-av[i]);
}
}
ans = min(ans,sum);
reverse(av.begin(),av.end());
count = k;
sum = 0;
x = av[tmp+1];
for(long long int i = 0;i < n;i++){
if(count > 0){
sum = sum + abs(x-av[i]);
count--;
}else{
sum = sum - abs(x-av[i]);
}
}
ans = min(ans,sum);
cout << ans <<endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0