Codeforces Round #687 (based on Technocup 2021 Elimination Round 2) DIV1 D問題/Round2 F問題 - Cakes for Clones

Source

Codeforces Round #687 (based on Technocup 2021 Elimination Round 2) DIV1 D問題 (2250pt)
Technocup 2021 - Elimination Round 2 F問題 (3000pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20201205-1）のコード

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

//no-unlocked
int N; ll T[5001], X[5001];
char ok[5003][5003];
ll dp[5003];
{
  ll tt, r;
  rd(N,(T,X)(N));
  arrInsert(0, N, T, 0LL, X, 0LL);
  ok[0][0] = 1;

  rep(i,N-1) rep(j,N) if(ok[i][j]){
    if(j==i+1){
      if(i==N-2 && j==N-1) wt("YES"), return 0;

      tt = T[i+2] - T[i];
      r = tt - abs(X[i+2] - X[i]);
      r <?= T[i+2] - T[i+1];
      if(r >= 0) ok[i+2][0] = 1, dp[i+2] >?= r;

      rep(k,i+3,N) if(tt >= abs(X[i] - X[k]) + abs(X[k] - X[i+2]) && T[i+2] - T[i+1] >= abs(X[k] - X[i+2])) ok[i+2][k] = 1;
    } else if(j==0){
      tt = dp[i] + T[i+1] - T[i];
      r = tt - abs(X[i+1] - X[i]);
      r <?= T[i+1] - T[i];
      if(r >= 0) ok[i+1][0] = 1, dp[i+1] >?= r;

      rep(k,i+2,N) if(tt >= abs(X[i] - X[k]) + abs(X[k] - X[i+1]) && T[i+1] - T[i] >= abs(X[k] - X[i+1])) ok[i+1][k] = 1;
    } else {
      if(T[i+1] - T[i] >= abs(X[i+1] - X[i])) ok[i+1][j] = 1;
    }
  }

  rep(i,N) if(ok[N-1][i]) wt("YES"), return 0;
  wt("NO");
}

Current time: 2024年04月25日02時37分05秒
Last modified: 2020年12月05日15時43分14秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF687 CF_DIV1_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン：