diverta 2019 Programming Contest 2 D問題 - Squirrel Merchant

Source

diverta 2019 Programming Contest 2
問題文

問題概要

省略

解法

省略

cLay（version 20190902-1）のコード

C++に変換後のコードはこちら

int N, G[2], S[2], B[2];
int dp[5001];

ll solve(ll N, int A[]){
  return N + (N / A[0]) * (A[1] - A[0]);
}

ll solve(ll N, int A[], int B[]){
  ll i, j, k, res = 0;

  rep(i,5001){
    k = N - A[0] * i;
    if(k < 0) break;
    j = k / B[0];
    res >?= N + i * (A[1]-A[0]) + j * (B[1]-B[0]);
  }

  rep(i,5001){
    k = N - B[0] * i;
    if(k < 0) break;
    j = k / A[0];
    res >?= N + i * (B[1]-B[0]) + j * (A[1]-A[0]);
  }

  return res;
}

{
  int i, j, k;
  ll res;
  int a[2][2], sz;
  rd(N,(G,S,B)(2));

  if(G[0] >= G[1] && S[0] >= S[1] && B[0] >= B[1]){
    swap(G[0], G[1]);
    swap(S[0], S[1]);
    swap(B[0], B[1]);
  }
  if(G[0] <= G[1] && S[0] <= S[1] && B[0] <= B[1]){
    rep(i,N+1) dp[i] = i;
    rep(i,G[0],N+1) dp[i] >?= dp[i-G[0]] + G[1];
    rep(i,S[0],N+1) dp[i] >?= dp[i-S[0]] + S[1];
    rep(i,B[0],N+1) dp[i] >?= dp[i-B[0]] + B[1];
    res = dp[N];
  } else {
    res = N;
    rep(2){
      sz = 0;
      if(G[0] < G[1]) a[sz][0] = G[0], a[sz][1] = G[1], sz++;
      if(S[0] < S[1]) a[sz][0] = S[0], a[sz][1] = S[1], sz++;
      if(B[0] < B[1]) a[sz][0] = B[0], a[sz][1] = B[1], sz++;
      if(sz==1) res = solve(res, a[0]);
      if(sz==2) res = solve(res, a[0], a[1]);
      swap(G[0], G[1]);
      swap(S[0], S[1]);
      swap(B[0], B[1]);
    }
  }
  wt(res);
}

Current time: 2024年04月24日10時47分28秒
Last modified: 2019年09月04日00時13分11秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)