#952197 (C) No.561 東京と京都

• 問題: No.561 東京と京都
• ユーザー: miwawa
• 提出日時: 2024-02-18 14:41:58
• 言語: C (gcc 12.3.0)
• 結果: AC
• 実行時間: 20 ms / 2,000 ms
• コード長: 1,308 bytes
• コンパイル時間: 304 ms
• コンパイル使用メモリ: 32,640 KB
• 実行使用メモリ: 22,016 KB
• 最終ジャッジ日時: 2024-02-18 14:42:00
• 合計ジャッジ時間: 1,676 ms
• ジャッジサーバーID （参考情報）: judge12 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	15 ms; 21,888 KB
testcase_01	AC	14 ms; 21,888 KB
testcase_02	AC	14 ms; 21,888 KB
testcase_03	AC	14 ms; 21,888 KB
testcase_04	AC	14 ms; 21,888 KB
testcase_05	AC	19 ms; 21,888 KB
testcase_06	AC	14 ms; 21,888 KB
testcase_07	AC	14 ms; 21,888 KB
testcase_08	AC	14 ms; 21,888 KB
testcase_09	AC	14 ms; 21,888 KB
testcase_10	AC	18 ms; 21,888 KB
testcase_11	AC	13 ms; 21,888 KB
testcase_12	AC	14 ms; 22,016 KB
testcase_13	AC	14 ms; 22,016 KB
testcase_14	AC	14 ms; 22,016 KB
testcase_15	AC	15 ms; 22,016 KB
testcase_16	AC	14 ms; 22,016 KB
testcase_17	AC	20 ms; 22,016 KB
testcase_18	AC	14 ms; 22,016 KB
testcase_19	AC	13 ms; 22,016 KB
testcase_20	AC	13 ms; 22,016 KB

ソースコード

#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);
  }