Submission #393414

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
393414	2021-04-23T11:45:13 Z	SonicML	Rabbit Carrot (LMIO19_triusis)	C++11	0 / 100	1 ms	336 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	304 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	304 KB	Output is correct
13	Correct	1 ms	308 KB	Output is correct
14	Incorrect	1 ms	204 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #2

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	304 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	304 KB	Output is correct
13	Correct	1 ms	308 KB	Output is correct
14	Incorrect	1 ms	204 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #3

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	304 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	304 KB	Output is correct
13	Correct	1 ms	308 KB	Output is correct
14	Incorrect	1 ms	204 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #4

0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	304 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	304 KB	Output is correct
13	Correct	1 ms	308 KB	Output is correct
14	Incorrect	1 ms	204 KB	Output isn't correct
15	Halted	0 ms	0 KB	-