結果

問題 No.2390 Udon Coupon (Hard)
ユーザー Nzt3
提出日時 2023-07-23 00:08:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,681 bytes
コンパイル時間 1,633 ms
コンパイル使用メモリ 197,776 KB
最終ジャッジ日時 2025-02-15 18:16:45
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 RE * 2
other AC * 10 WA * 1 RE * 36
権限があれば一括ダウンロードができます

ソースコード

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