Submission #335772

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
335772	2020-12-14T00:30:56 Z	ChrisT	None (JOI16_ho_t1)	C++17	70 / 100	19 ms	620 KB

2016_ho_t1

#include <bits/stdc++.h>
using namespace std;
const int MN = 1e4 + 5;
int a[MN];long long dp[MN];
int main() { 
	int n,m,k;
	scanf ("%d %d %d",&n,&m,&k);
	for (int i = 1; i <= n; i++) {
		scanf ("%d",&a[i]); int mx = a[i], mn = a[i], ed = max(1,i-m+1); dp[i] = 2e18;
		for (int j = i; j >= ed; j--) {
			mx = max(mx,a[j]); mn = min(mn,a[j]);
			dp[i] = min(dp[i],dp[j-1] + k + (long long)(i-j+1) * (mx - mn));
		}
	}
	printf ("%lld\n",dp[n]);
	return 0;
}

Compilation message

2016_ho_t1.cpp: In function 'int main()':
2016_ho_t1.cpp:7:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    7 |  scanf ("%d %d %d",&n,&m,&k);
      |  ~~~~~~^~~~~~~~~~~~~~~~~~~~~
2016_ho_t1.cpp:9:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 |   scanf ("%d",&a[i]); int mx = a[i], mn = a[i], ed = max(1,i-m+1); dp[i] = 2e18;
      |   ~~~~~~^~~~~~~~~~~~

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	0 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	3 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct

Subtask #3

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	0 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	1 ms	364 KB	Output is correct
21	Correct	3 ms	364 KB	Output is correct
22	Correct	1 ms	364 KB	Output is correct
23	Correct	1 ms	384 KB	Output is correct
24	Correct	1 ms	364 KB	Output is correct
25	Correct	1 ms	364 KB	Output is correct
26	Correct	1 ms	364 KB	Output is correct
27	Correct	1 ms	364 KB	Output is correct
28	Correct	1 ms	364 KB	Output is correct
29	Correct	1 ms	364 KB	Output is correct
30	Correct	1 ms	364 KB	Output is correct
31	Execution timed out	19 ms	620 KB	Time limit exceeded (wall clock)
32	Halted	0 ms	0 KB	-