Submission #465279

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
465279	2021-08-15T13:29:18 Z	dattranxxx	Stove (JOI18_stove)	C++11	50 / 100	147 ms	199076 KB

stove

/*
 * Author :  shora
 */
#include <bits/stdc++.h>
#define print(_v) for (auto &_ : _v) {cerr << _ << ' ';} cerr << endl;
using namespace std;
using ll = long long;
const int oo = 1e9;
const int N = 5000;
int a[N+1];
int n, k;
int dp[N+1][N+1];
int main() {
  cin.tie(0)->sync_with_stdio(0); cout.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; ++i)
  	cin >> a[i];
  // dp[j][i] = a[i] + min(dp[j-1][u-1] - a[u]) + 1 : u <= i
  // dp[j][i] = a[i] + g[j-1] + 1 voi g[i] = min(dp[i][p-1] + a[p]) 
  // dp[i] la mot day tang 
  // a[i] la mot day tang
	memset(dp, 0x3f, sizeof(dp));
	int res = oo;
	for (int i = 0; i <= k; ++i) dp[i][0] = 0;
  for (int i = 1; i <= k; ++i) {
  	int mn = oo;
  	for (int j = 1; j <= n; ++j) {
  		mn = min(mn, dp[i-1][j-1] - a[j]);
  		dp[i][j] = a[j] + mn + 1;
  		if (j == n)
  			res = min(res, dp[i][j]);
		}
	}
	cout << res;
  
  
  return 0;
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	98116 KB	Output is correct
2	Correct	45 ms	98108 KB	Output is correct
3	Correct	44 ms	98176 KB	Output is correct
4	Correct	46 ms	98128 KB	Output is correct
5	Correct	46 ms	98116 KB	Output is correct
6	Correct	46 ms	98120 KB	Output is correct
7	Correct	45 ms	98076 KB	Output is correct
8	Correct	44 ms	98116 KB	Output is correct
9	Correct	44 ms	98148 KB	Output is correct

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	98116 KB	Output is correct
2	Correct	45 ms	98108 KB	Output is correct
3	Correct	44 ms	98176 KB	Output is correct
4	Correct	46 ms	98128 KB	Output is correct
5	Correct	46 ms	98116 KB	Output is correct
6	Correct	46 ms	98120 KB	Output is correct
7	Correct	45 ms	98076 KB	Output is correct
8	Correct	44 ms	98116 KB	Output is correct
9	Correct	44 ms	98148 KB	Output is correct
10	Correct	45 ms	98200 KB	Output is correct
11	Correct	45 ms	98180 KB	Output is correct
12	Correct	51 ms	98104 KB	Output is correct
13	Correct	64 ms	98200 KB	Output is correct
14	Correct	60 ms	98160 KB	Output is correct
15	Correct	57 ms	98220 KB	Output is correct

Subtask #3

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	98116 KB	Output is correct
2	Correct	45 ms	98108 KB	Output is correct
3	Correct	44 ms	98176 KB	Output is correct
4	Correct	46 ms	98128 KB	Output is correct
5	Correct	46 ms	98116 KB	Output is correct
6	Correct	46 ms	98120 KB	Output is correct
7	Correct	45 ms	98076 KB	Output is correct
8	Correct	44 ms	98116 KB	Output is correct
9	Correct	44 ms	98148 KB	Output is correct
10	Correct	45 ms	98200 KB	Output is correct
11	Correct	45 ms	98180 KB	Output is correct
12	Correct	51 ms	98104 KB	Output is correct
13	Correct	64 ms	98200 KB	Output is correct
14	Correct	60 ms	98160 KB	Output is correct
15	Correct	57 ms	98220 KB	Output is correct
16	Runtime error	147 ms	199076 KB	Execution killed with signal 11
17	Halted	0 ms	0 KB	-