제출 #405066

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
405066	2021-05-15 16:31:20	rainboy	Shortcut (IOI16_shortcut)	C11	0 / 100	1 ms	212 KiB

shortcut

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
27
28
29
30
#include "shortcut_c.h"
#define N 1000000
#define INF 0x3f3f3f3f3f3f3f3f
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
long long abs_(long long a) { return a > 0 ? a : -a; }
long long find_shortcut(int n, int *ll, int *dd, int c) {
  static long long xx[N];
  int i, j, k, l;
  long long lower, upper;
  for (i = 1; i < n; i++)
    xx[i] = xx[i - 1] + ll[i - 1];
  lower = -1, upper = xx[n - 1] + 2000000000;
  while (upper - lower > 1) {
    long long d = (lower + upper) / 2, w, x, y, z;
    int can;
    w = x = y = z = INF;
    for (k = 0; k < n; k++)
      for (l = k + 1; l < n; l++)
        if (dd[k] + dd[l] + xx[l] - xx[k] > d) {
          /* dd[k] + dd[l] + |xx[k] - xx[i]| + c + |xx[l] - xx[j]| <= d
           *
           * max(xx[k] - xx[i], xx[i] - xx[k]) + max(xx[l] - xx[j], xx[j] - xx[l])
           * <= d - (dd[k] + dd[l] + c)
           *
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3