답안 #428715

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
428715	2021-06-15T14:02:16 Z	shenxy	Sparklers (JOI17_sparklers)	C++11	0 / 100	37 ms	8132 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 = 10000000000 / 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	8100 KB	Output is correct
2	Correct	26 ms	8096 KB	Output is correct
3	Correct	30 ms	8012 KB	Output is correct
4	Correct	37 ms	8088 KB	Output is correct
5	Correct	24 ms	8100 KB	Output is correct
6	Correct	24 ms	8012 KB	Output is correct
7	Correct	23 ms	8056 KB	Output is correct
8	Correct	26 ms	8100 KB	Output is correct
9	Correct	24 ms	8012 KB	Output is correct
10	Correct	27 ms	8100 KB	Output is correct
11	Correct	23 ms	8104 KB	Output is correct
12	Correct	24 ms	8104 KB	Output is correct
13	Correct	26 ms	8132 KB	Output is correct
14	Correct	25 ms	8012 KB	Output is correct
15	Correct	36 ms	8012 KB	Output is correct
16	Correct	27 ms	8084 KB	Output is correct
17	Correct	26 ms	8104 KB	Output is correct
18	Correct	28 ms	8012 KB	Output is correct
19	Incorrect	22 ms	8104 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #2

0 / 20.0

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

Subtask #3

0 / 50.0

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