답안 #428691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
428691	2021-06-15T13:53:04 Z	shenxy	Sparklers (JOI17_sparklers)	C++11	0 / 100	32 ms	8108 KB

sparklers

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const long long INF = 1LL << 60;
int N, K;
long long T, X[1000], m, dpt[1000][1000];
long long dp(int a, int b) {
	if (a == K - 1 && b == K - 1) return 2 * m * T;
	if (a == b) return -INF;
	if (dpt[a][b] != -1) return dpt[a][b];
	return dpt[a][b] = max(dp(a + 1, b) + (X[a] - X[a + 1]) / 2 < 0 ? -INF : dp(a + 1, b) + (X[a] - X[a + 1]) / 2, dp(a, b - 1) + (X[b - 1] - X[b]) / 2 < 0 ? -INF : dp(a, b - 1) + (X[b - 1] - X[b]) / 2) + 2 * m * T;
}
int main() {
	scanf("%d %d %lld", &N, &K, &T);
	for (int i = 0; i < N; ++i) scanf("%lld", &X[i]), X[i] *= 2;
	long long l = 1, u = 2000000000 / T;
	while (l != u) {
		m = (l + u) / 2;
		memset(dpt, -1, sizeof dpt);
		if (dp(0, N - 1) < 0) l = m + 1;
		else u = m;
	}
	printf("%lld", l);
	return 0;
}

Compilation message

sparklers.cpp: In function 'int main()':
sparklers.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d %d %lld", &N, &K, &T);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:16:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  for (int i = 0; i < N; ++i) scanf("%lld", &X[i]), X[i] *= 2;
      |                              ~~~~~^~~~~~~~~~~~~~~

Subtask #1

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	8012 KB	Output is correct
2	Correct	21 ms	8104 KB	Output is correct
3	Correct	24 ms	8100 KB	Output is correct
4	Correct	22 ms	8108 KB	Output is correct
5	Correct	26 ms	8012 KB	Output is correct
6	Correct	26 ms	8012 KB	Output is correct
7	Correct	25 ms	8012 KB	Output is correct
8	Correct	28 ms	8012 KB	Output is correct
9	Correct	29 ms	8012 KB	Output is correct
10	Correct	27 ms	8088 KB	Output is correct
11	Correct	32 ms	8080 KB	Output is correct
12	Correct	25 ms	8012 KB	Output is correct
13	Correct	26 ms	8104 KB	Output is correct
14	Correct	24 ms	8104 KB	Output is correct
15	Correct	27 ms	8012 KB	Output is correct
16	Correct	30 ms	8088 KB	Output is correct
17	Correct	26 ms	8012 KB	Output is correct
18	Correct	32 ms	8088 KB	Output is correct
19	Incorrect	27 ms	8108 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #2

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	8012 KB	Output is correct
2	Correct	21 ms	8104 KB	Output is correct
3	Correct	24 ms	8100 KB	Output is correct
4	Correct	22 ms	8108 KB	Output is correct
5	Correct	26 ms	8012 KB	Output is correct
6	Correct	26 ms	8012 KB	Output is correct
7	Correct	25 ms	8012 KB	Output is correct
8	Correct	28 ms	8012 KB	Output is correct
9	Correct	29 ms	8012 KB	Output is correct
10	Correct	27 ms	8088 KB	Output is correct
11	Correct	32 ms	8080 KB	Output is correct
12	Correct	25 ms	8012 KB	Output is correct
13	Correct	26 ms	8104 KB	Output is correct
14	Correct	24 ms	8104 KB	Output is correct
15	Correct	27 ms	8012 KB	Output is correct
16	Correct	30 ms	8088 KB	Output is correct
17	Correct	26 ms	8012 KB	Output is correct
18	Correct	32 ms	8088 KB	Output is correct
19	Incorrect	27 ms	8108 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #3

0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	8012 KB	Output is correct
2	Correct	21 ms	8104 KB	Output is correct
3	Correct	24 ms	8100 KB	Output is correct
4	Correct	22 ms	8108 KB	Output is correct
5	Correct	26 ms	8012 KB	Output is correct
6	Correct	26 ms	8012 KB	Output is correct
7	Correct	25 ms	8012 KB	Output is correct
8	Correct	28 ms	8012 KB	Output is correct
9	Correct	29 ms	8012 KB	Output is correct
10	Correct	27 ms	8088 KB	Output is correct
11	Correct	32 ms	8080 KB	Output is correct
12	Correct	25 ms	8012 KB	Output is correct
13	Correct	26 ms	8104 KB	Output is correct
14	Correct	24 ms	8104 KB	Output is correct
15	Correct	27 ms	8012 KB	Output is correct
16	Correct	30 ms	8088 KB	Output is correct
17	Correct	26 ms	8012 KB	Output is correct
18	Correct	32 ms	8088 KB	Output is correct
19	Incorrect	27 ms	8108 KB	Output isn't correct
20	Halted	0 ms	0 KB	-