結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 3 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 AC 2 ms
4,348 KB
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 WA -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 AC 2 ms
4,348 KB
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 AC 19 ms
18,012 KB
testcase_41 RE -
testcase_42 AC 19 ms
14,188 KB
testcase_43 AC 16 ms
18,208 KB
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 AC 6 ms
8,448 KB
testcase_48 RE -
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[0]){
      D02[i+A[0]]=max(D02[i+A[0]],D02[i]+B[0]);
    }
    if(i+A[2]<=A_lcm[0]){
      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[0]){
      D01[i+A[1]]=max(D01[i+A[1]],D01[i]+B[1]);
    }
    if(i+A[0]<=A_lcm[0]){
      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