結果

問題 No.561 東京と京都
コンテスト
ユーザー miwawa
提出日時 2024-02-18 14:41:58
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 16 ms / 2,000 ms
コード長 1,308 bytes
コンパイル時間 339 ms
コンパイル使用メモリ 32,896 KB
実行使用メモリ 22,016 KB
最終ジャッジ日時 2024-09-29 00:30:10
合計ジャッジ時間 1,378 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define rep(i,a,b) for(i=a;i<b;i++)

int cha(const void*a,const void*b){
  if(*(int*)a >*(int*)b){
    return 1;
  }else if(*(int*)a <*(int*)b){
    return -1;
  }else{
    return 0;
  }
}


int main(void){
    int d,i,j,kk=0,ma,mb,p;
  int mini=1000,k=0,qi=0,qj=0,n;
  int s=0,h=0;
  int a[110],b[110],c[5010],w=0;
  int heavy=1e9;
  int x_size = 1;  // 1次元のサイズ
  int y_size = 5010;  // 2次元のサイズ
  int z_size = 15010;  // 3次元のサイズ

  // 三次元配列の動的確保
  int ***dp;

  dp = (int ***)malloc(x_size * sizeof(int**));
  for (int i = 0; i < x_size; ++i) {
      dp[i] = (int **)malloc(y_size * sizeof(int*));
      for (int j = 0; j < y_size; ++j) {
          dp[i][j] = (int *)malloc(z_size * sizeof(int));
      }
  }
scanf("%d%d",&n,&d);
  int dpp[110][110],t=0;
  rep(i,1,n+1){
    scanf("%d%d",&a[i],&b[i]);
    dpp[0][i]=0;
    dpp[i][0]=0;
  }
  dpp[0][0]=0;
  rep(i,1,n+1){
   if(dpp[i-1][0]>dpp[0][i-1]-d){
     dpp[i][0]+=dpp[i-1][0]+a[i];
   }else{
     dpp[i][0]+=dpp[0][i-1]-d+a[i];
   }
  if(dpp[i-1][0]-d>dpp[0][i-1] ||i==1){
    dpp[0][i]+=dpp[i-1][0]-d+b[i];
     }else{
       dpp[0][i]+=dpp[0][i-1]+b[i];
     }
  }
  s=fmax(dpp[n][0],dpp[0][n]);
  printf("%d\n",s);
  
  free(dp);
  }
0