結果

問題 No.2390 Udon Coupon (Hard)
ユーザー Nzt3Nzt3
提出日時 2023-07-23 00:11:26
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,681 bytes
コンパイル時間 4,472 ms
コンパイル使用メモリ 205,656 KB
実行使用メモリ 89,560 KB
最終ジャッジ日時 2023-10-24 06:45:41
合計ジャッジ時間 4,452 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 1 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 1 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 2 ms
4,348 KB
testcase_12 AC 2 ms
4,348 KB
testcase_13 AC 2 ms
4,348 KB
testcase_14 AC 2 ms
4,348 KB
testcase_15 AC 2 ms
4,348 KB
testcase_16 AC 1 ms
4,348 KB
testcase_17 AC 2 ms
4,348 KB
testcase_18 AC 1 ms
4,348 KB
testcase_19 AC 2 ms
4,348 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 AC 15 ms
20,320 KB
testcase_40 AC 18 ms
18,012 KB
testcase_41 AC 31 ms
23,088 KB
testcase_42 AC 15 ms
14,188 KB
testcase_43 AC 14 ms
18,208 KB
testcase_44 AC 12 ms
12,008 KB
testcase_45 AC 30 ms
13,924 KB
testcase_46 AC 4 ms
4,820 KB
testcase_47 AC 7 ms
8,448 KB
testcase_48 AC 20 ms
12,672 KB
testcase_49 AC 2 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll N;
  cin>>N;
  array<ll,3>A,B;
  for(int i=0;i<3;i++){
    cin>>A[i]>>B[i];
  }
  array<ll,3>A_lcm,B_lcm;
  A_lcm[0]=lcm(A[1],A[2]);
  A_lcm[1]=lcm(A[0],A[2]);
  A_lcm[2]=lcm(A[0],A[1]);
  ll A012=lcm(A[0],lcm(A[1],A[2]));
  ll D012=max({A012/A[0]*B[0],A012/A[1]*B[1],A012/A[2]*B[2]});
  B_lcm[0]=max(A_lcm[0]/A[1]*B[1],A_lcm[0]/A[2]*B[2]);
  B_lcm[1]=max(A_lcm[1]/A[0]*B[0],A_lcm[1]/A[2]*B[2]);
  B_lcm[2]=max(A_lcm[2]/A[0]*B[0],A_lcm[2]/A[1]*B[1]);
  ll ans_base=N/A012*D012;
  N%=A012;
  vector<ll>D01(A_lcm[2]+1),D12(A_lcm[0]+1),D02(A_lcm[1]+1);
  for(int i=0;i<A_lcm[0];i++){
    if(i+A[1]<=A_lcm[0]){
      D12[i+A[1]]=max(D12[i+A[1]],D12[i]+B[1]);
    }
    if(i+A[2]<=A_lcm[0]){
      D12[i+A[2]]=max(D12[i+A[2]],D12[i]+B[2]);
    }
  }
  for(int i=0;i<A_lcm[1];i++){
    if(i+A[0]<=A_lcm[1]){
      D02[i+A[0]]=max(D02[i+A[0]],D02[i]+B[0]);
    }
    if(i+A[2]<=A_lcm[1]){
      D02[i+A[2]]=max(D02[i+A[2]],D02[i]+B[2]);
    }
  }
  for(int i=0;i<A_lcm[2];i++){
    if(i+A[1]<=A_lcm[2]){
      D01[i+A[1]]=max(D01[i+A[1]],D01[i]+B[1]);
    }
    if(i+A[0]<=A_lcm[2]){
      D01[i+A[0]]=max(D01[i+A[0]],D01[i]+B[0]);
    }
  }
  ll ans_add=0;
  for(int i=0;i<=N/A[0];i++){
    ans_add=max(ans_add,B[0]*i+(N-A[0]*i)/A_lcm[0]*B_lcm[0]+D12[(N-A[0]*i)%A_lcm[0]]);
  }
  for(int i=0;i<=N/A[1];i++){
    ans_add=max(ans_add,B[1]*i+(N-A[1]*i)/A_lcm[1]*B_lcm[1]+D02[(N-A[1]*i)%A_lcm[1]]);
  }
  for(int i=0;i<=N/A[2];i++){
    ans_add=max(ans_add,B[2]*i+(N-A[2]*i)/A_lcm[2]*B_lcm[2]+D01[(N-A[2]*i)%A_lcm[2]]);
  }
  cout<<ans_base+ans_add<<'\n';
}
0