Kyoto University Programming Contest 2019 F問題 - カズマ王国の陥落

Source

Kyoto University Programming Contest 2019
問題文

問題概要

省略

解法

省略

cLay（version 20191102-1）のコード

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

int N, A[3000], M, L[3000], R[3000], B[3000];
ll dp[2][3000][3001];

ll solve(int f, int g, int s){
  int i, j, k;
  ll res = 0;
  if(dp[f][g][s] >= 0) return dp[f][g][s];

  if(f && s < M && L[s] <= g){
    res = solve(f, g, s+1);
    if(g <= R[s]) res += B[s];
  } else {
    if(g+1 < N) res >?= solve(0, g+1, s);
    if(f==0)    res >?= solve(1, g, s) - A[g];
  }

  return dp[f][g][s] = res;
}

{
  rd(N,A(N),M,(L--,R--,B)(M));
  sortA(M,L,R,B);
  rep(k,2) rep(i,N) rep(j,M+1) dp[k][i][j] = -1;
  wt(solve(0, 0, 0));
}

Current time: 2024年04月26日13時15分48秒
Last modified: 2019年11月02日12時05分27秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)