Submission #393414

#	Time	Username	Problem	Language	Result	Execution time	Memory
393414		SonicML	Rabbit Carrot (LMIO19_triusis)	C++11	0 / 100	1 ms	336 KiB

triusis

#include <iostream>

using namespace std;

typedef long long ll;

struct val{
  int cost;
  ll height;
};

int const INF = 2e9+7;

int const NMAX = 2e5;
val dp[1 + NMAX];

int main() {

  ll n, m, c;
  cin >> n >> m;
  for(ll i = 1;i <= n;i++){
    cin >> c;
    dp[i].cost = INF;
    for(ll j = 0;j < i;j++){
      if(dp[j].height + m * (i - j) >= c){
        if(dp[i].cost == dp[j].cost + (i - j - 1)){
          dp[i].height = c;
        }else if(dp[i].cost > dp[j].cost + (i - j - 1)){
          dp[i].cost = dp[j].cost + (i - j - 1);
          dp[i].height = c;
        }
      }
    }
    if(dp[i].cost > dp[i-1].cost + 1){
      dp[i].cost = dp[i-1].cost + 1;
      dp[i].height = dp[i-1].height + m;
    }
  }
  cout << dp[n].cost;
  return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37