Submission #428715

#	Time	Username	Problem	Language	Result	Execution time	Memory
428715		shenxy	Sparklers (JOI17_sparklers)	C++11	0 / 100	37 ms	8132 KiB

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 (stderr)

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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50