Submission #428722

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
428722	2021-06-15 14:03:56	shenxy	Sparklers (JOI17_sparklers)	C++11	50 / 100	457 ms	8260 KiB

sparklers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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 = 0, 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;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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