#1180757 (C) No.3656 Game Scores and Costs

提出ソース
結果

問題	No.3656 Game Scores and Costs
コンテスト
ユーザー	nekoti
提出日時	2026-08-30 13:54:55
言語	C (gcc 15.3.0) コンパイル: `gcc-15 -O2 -DONLINE_JUDGE -o a.out _filename_ -lm` 実行: `./a.out`
結果	AC
実行時間	52 ms / 2,000 ms
	+ 850µs
コード長	9,163 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	863 ms
コンパイル使用メモリ	39,808 KB
実行使用メモリ	49,664 KB
最終ジャッジ日時	2026-08-30 13:55:08
合計ジャッジ時間	3,571 ms
ジャッジサーバーID （参考情報）	judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 21
権限があれば一括ダウンロードができます
ソースコード

raw source code
//【優先度付きキュー（削除可能）】
#define _DEBUG 0

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

#define _HEAP_TYPE int//★型の確認必須
#define _HEAP_NUM_MAX (3000010)//削除をする場合は制約よりも確実に大きくなる★確認必須

//変数短縮
#define _TABLE_TOP &pq[0][0][0]
#define _NUM_TOP &pqNum[0][0]
#define _TABLE_MIN_ADD &pq[0][0][0]
#define _TABLE_MIN_DEL &pq[0][1][0]
#define _TABLE_MAX_ADD &pq[1][0][0]
#define _TABLE_MAX_DEL &pq[1][1][0]
#define _NUM_MIN_ADD &pqNum[0][0]
#define _NUM_MIN_DEL &pqNum[0][1]
#define _NUM_MAX_ADD &pqNum[1][0]
#define _NUM_MAX_DEL &pqNum[1][1]
//引数短縮
#define __PUSH_ADD &pq[0][0][0],&pqNum[0][0]
#define __PUSH_DEL &pq[0][1][0],&pqNum[0][1]
#define __MIN_TOP _HEAP_MIN,_TABLE_TOP,_NUM_TOP
#define __MAX_TOP _HEAP_MAX,_TABLE_TOP,_NUM_TOP
#define __MIN_ADD _HEAP_MIN,_TABLE_MIN_ADD,_NUM_MIN_ADD
#define __MIN_DEL _HEAP_MIN,_TABLE_MIN_DEL,_NUM_MIN_DEL
#define __MAX_ADD _HEAP_MAX,_TABLE_MAX_ADD,_NUM_MAX_ADD
#define __MAX_DEL _HEAP_MAX,_TABLE_MAX_DEL,_NUM_MAX_DEL

enum{
  _HEAP_ADD=0,
  _HEAP_DEL,
  _HEAP_ADDDEL_NUM
};
enum{
  _HEAP_MIN=0,
  _HEAP_MAX,
  _HEAP_MINMAX_NUM
};

void swap(_HEAP_TYPE *pa,_HEAP_TYPE *pb){_HEAP_TYPE tmp=*pa;*pa=*pb;*pb=tmp;}
void heapInit(_HEAP_TYPE *table, int *num)
{ int clearsize = (num[_HEAP_ADD]>num[_HEAP_DEL] ? num[_HEAP_ADD]:num[_HEAP_DEL]);
  for(int i=0;i<4;i++){memset(table + i*_HEAP_NUM_MAX, 0, clearsize*sizeof(_HEAP_TYPE));*(num+i)=0;}
}
void swapMinUp(_HEAP_TYPE *table, int downindex)
{ while((downindex>>1) && *(table + (downindex>>1)) > *(table + downindex) ){
    swap(table + (downindex>>1), table + downindex);downindex>>=1;
  }
}
void swapMaxUp(_HEAP_TYPE *table, int downindex)
{ while((downindex>>1) && *(table + (downindex>>1)) < *(table + downindex) ){
    swap(table + (downindex>>1), table + downindex);downindex>>=1;
  }
}
void swapMinDown(_HEAP_TYPE *table, int endindex)
{ int upindex=1;
  while(upindex*2 < endindex+1){
    int lindex, rindex, swapindex;
    if(upindex*2 == endindex){swapindex=(upindex<<1) + 0;}
    else{
      lindex=(upindex<<1) + 0;rindex=(upindex<<1) + 1;
      swapindex=*(table+lindex)<*(table+rindex) ? lindex:rindex;
    }
    if(*(table+swapindex)<*(table+upindex))swap(table + upindex, table + swapindex);
    upindex=swapindex;
  }
}
void swapMaxDown(_HEAP_TYPE *table, int endindex)
{ int upindex=1;
  while(upindex*2 < endindex+1){
    int lindex, rindex, swapindex;
    if(upindex*2 == endindex){swapindex=(upindex<<1) + 0;}
    else{
      lindex=(upindex<<1) + 0;rindex=(upindex<<1) + 1;
      swapindex=*(table+lindex)>*(table+rindex) ? lindex:rindex;
    }
    if(*(table+swapindex)>*(table+upindex))swap(table + upindex, table + swapindex);
    upindex=swapindex;
  }
}
void heapPush(int minmax, _HEAP_TYPE *table, int *num, _HEAP_TYPE value)
{ (*num)++;*(table + *num) = value;
  if(2<=*num){
    if(_HEAP_MIN==minmax)swapMinUp(table, *num);
    else                 swapMaxUp(table, *num);
  }
}
void heapPushMM(_HEAP_TYPE *table, int *num, _HEAP_TYPE value)
{ heapPush(_HEAP_MIN, table, num, value);                      //MIN
  heapPush(_HEAP_MAX, table + 2*_HEAP_NUM_MAX, num + 2, value);//MAX
}
_HEAP_TYPE heapPop(int minmax, _HEAP_TYPE *table, int *num)
{ swap(table + 1, table + *num);(*num)--;
  if(2<=*num){
    if(_HEAP_MIN==minmax)swapMinDown(table, *num);
    else                 swapMaxDown(table, *num);
  }return 0;
}
_HEAP_TYPE heapOutput(int minmax, _HEAP_TYPE *table, int *num, bool *OK)
{ if(0==*num){*OK=false;return 0;}
  _HEAP_TYPE topValue=0, delValue=0;
  while(*num && *(num+1)){
    topValue=*(table + 1);delValue=*(table + 1*_HEAP_NUM_MAX + 1);
    if(topValue==delValue){
      heapPop(minmax, table, num);
      heapPop(minmax, table + 1*_HEAP_NUM_MAX, num + 1);
    }
    else break;
  }if(0==*num){*OK=false;return 0;}
  return *(table + 1);
}
_HEAP_TYPE heapPopMM(int minmax, _HEAP_TYPE *table, int *num, bool *OK)
{ _HEAP_TYPE popvalue;
  if(_HEAP_MIN==minmax){
    //MINに削除するだけの個数が残っているか確認
    if(0==*num){*OK=false;return 0;}
    //MINを削除し、MAXに予約を入れる
    popvalue=heapOutput(_HEAP_MIN, table, num, OK);
    if(*OK){
      heapPop(_HEAP_MIN, table, num);
      (void)heapOutput(_HEAP_MAX, table + 2*_HEAP_NUM_MAX, num + 2, OK);
      if(*OK && 1<=*(num+2)){
        //MINで削除した値を、MAXの削除予約に登録する
        heapPush(_HEAP_MAX, table + 3*_HEAP_NUM_MAX, num + 3, popvalue);
      }
    }
  }else{
    //MAXに削除するだけの個数が残っているか確認
    if(0==*(num+2)){*OK=false;return 0;}
    //MAXを削除し、MINに予約を入れる
    popvalue=heapOutput(_HEAP_MAX, table + 2*_HEAP_NUM_MAX, num + 2, OK);
    if(*OK){
      heapPop(_HEAP_MAX, table + 2*_HEAP_NUM_MAX, num + 2);
      (void)heapOutput(_HEAP_MIN, table, num, OK);
      if(*OK && 1<=*num){
        //MAXで削除した値を、MINの削除予約に登録する
        heapPush(_HEAP_MIN, table + 1*_HEAP_NUM_MAX, num + 1, popvalue);
      }
    }
  }if(!(*OK))return 0;
  return popvalue;
}
//  heapPushMM(__PUSH_ADD, 2);//minとmaxに2を追加
//  heapPushMM(__PUSH_DEL, 2);//minとmaxから2を削除（予約）
//  結果min=heapOutput(__MIN_ADD, &OK);//追加対象のminのminを返す（minのmaxは取得不可）
//  結果min=heapOutput(__MIN_DEL, &OK);//削除対象のminのminを返す（minのmaxは取得不可）
//  結果max=heapOutput(__MAX_ADD, &OK);//追加対象のmaxのmaxを返す（maxのminは取得不可）
//  結果max=heapOutput(__MAX_DEL, &OK);//追加対象のminのminを返す（minのmaxは取得不可）
//  削除値=heapPopMM(__MIN_TOP, &OK);//minのminを削除（minのmaxは削除不可）
//  削除値=heapPopMM(__MAX_TOP, &OK);//maxのmaxを削除（maxのminは削除不可）
int main (void)
{
  int scan;//scanf警告用
  int ans=0;
  int i, j;
  int q=0;
  
  int pqNum[_HEAP_MINMAX_NUM][_HEAP_ADDDEL_NUM]={{_HEAP_NUM_MAX, _HEAP_NUM_MAX},{_HEAP_NUM_MAX, _HEAP_NUM_MAX}};
  _HEAP_TYPE pq[_HEAP_MINMAX_NUM][_HEAP_ADDDEL_NUM][_HEAP_NUM_MAX];
  heapInit(_TABLE_TOP, _NUM_TOP);//全0初期化
  bool OK=true;
  
  int n,k,x;scan=scanf("%d%d%d",&n,&k,&x);
  int a[200010];for(i=0;i<n;i++)scan=scanf("%d",&a[i]);
  
  int count=0;
  long long temp=0;
  long long costsum=0;
  long long sum=0;
  long long max = -1e18;
  _HEAP_TYPE popValue;
  for(;q<n;q++)
  {
    //■追加
    heapPushMM(__PUSH_ADD, a[q]);
    temp = a[q];
    sum += a[q];
    costsum += x;
    count++;
    
    //■削除
    if(k<count)
    {
      OK=true;popValue=heapPopMM(__MIN_TOP, &OK);//minのmin
      sum -= popValue;
    }
    
    long long total = sum - costsum;
    max = max>total ? max:total;
#if 0
    printf("q=%d : %lld : total = %lld, max = %lld\n",q,sum,total,max);
#endif
  }
  printf("%lld\n",max);
  
//   int min=1123456789;
//   while(i<n)
//   {
//     OK=true;outputMin1=heapOutput(__MIN_ADD, &OK);//OKはtrueにしておくこと
//     OK=true;outputMax1=heapOutput(__MAX_ADD, &OK);//OKはtrueにしておくこと
    
//     min=min<(outputMax1-outputMin1) ? min:(outputMax1-outputMin1);
// #if _DEBUG
//   printf("MIN=%d(%d個) : %d %d %d %d %d\n",outputMin1,pqNum[0][0],pq[0][0][1],pq[0][0][2],pq[0][0][3],pq[0][0][4],pq[0][0][5]);
//   printf("MAX=%d(%d個) : %d %d %d %d %d\n",outputMax1,pqNum[1][0],pq[1][0][1],pq[1][0][2],pq[1][0][3],pq[1][0][4],pq[1][0][5]);
//     printf("i=%d : min/max=%d/%d, min=%d\n",i,outputMin1,outputMax1,min);
// #endif

//     heapPushMM(__PUSH_DEL, stList[i].idx);//minとmaxから先頭を削除（予約）
//     if(n<=i+k)break;
//     heapPushMM(__PUSH_ADD, stList[i+k].idx);//minとmaxに次を追加
//     i++;
//   }

  
  
//   heapPushMM(__PUSH_ADD, 1);
//   heapPushMM(__PUSH_ADD, 4);
//   heapPushMM(__PUSH_ADD, 5);
  
//   bool OK;
//   _HEAP_TYPE outputMin1,outputMin2,outputMax1,outputMax2;
//   _HEAP_TYPE popValue;
  
//   OK=true;outputMin1=heapOutput(__MIN_ADD, &OK);
//   OK=true;outputMin2=heapOutput(__MIN_DEL, &OK);
//   OK=true;outputMax1=heapOutput(__MAX_ADD, &OK);
//   OK=true;outputMax2=heapOutput(__MAX_DEL, &OK);
  
  
  
//   OK=true;popValue=heapPopMM(__MIN_TOP, &OK);//minのmin
//   OK=true;popValue=heapPopMM(__MAX_TOP, &OK);//maxのmax
  

//   OK=true;outputMin1=heapOutput(__MIN_ADD, &OK);
//   OK=true;outputMin2=heapOutput(__MIN_DEL, &OK);
//   OK=true;outputMax1=heapOutput(__MAX_ADD, &OK);
//   OK=true;outputMax2=heapOutput(__MAX_DEL, &OK);
//   printf("MIN=%d(%d個) : %d %d %d %d %d\n",outputMin1,pqNum[0][0],pq[0][0][1],pq[0][0][2],pq[0][0][3],pq[0][0][4],pq[0][0][5]);
//   printf("  MIN=%d(%d個) : %d %d %d %d %d\n",outputMin2,pqNum[0][1],pq[0][1][1],pq[0][1][2],pq[0][1][3],pq[0][1][4],pq[0][1][5]);
//   printf("MAX=%d(%d個) : %d %d %d %d %d\n",outputMax1,pqNum[1][0],pq[1][0][1],pq[1][0][2],pq[1][0][3],pq[1][0][4],pq[1][0][5]);
//   printf("  MAX=%d(%d個) : %d %d %d %d %d\n",outputMax2,pqNum[1][1],pq[1][1][1],pq[1][1][2],pq[1][1][3],pq[1][1][4],pq[1][1][5]);
//   puts("");
  
//   printf("%d %d %d %d\n",pqNum[0][0],pqNum[0][1],pqNum[1][0],pqNum[1][1]);
  
  return 0;
}
yukicoder

結果

ソースコード
