Submission #38854

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
38854	2018-01-07 10:10:40	14kg	Rail (IOI14_rail)	C++11	100 / 100	125 ms	836 KiB

rail

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 "rail.h"
#include <algorithm>
#define N 5001
#define INF 999999999
using namespace std;
int n, zd[N], zero;
int rd[N], rw, r_num, lw, l_num;
int L_len, R_len, S_len, S[N];
pair<int, int> L[N], R[N];
void findLocation(int _n, int _zero, int out1[], int out2[]) {
  int temp = INF, len;
  bool check;
  n = _n, zero = _zero;
  for (int i = 1; i < n; i++) {
    zd[i] = getDistance(0, i);
    if (temp > zd[i]) {
      temp = zd[i], r_num = i;
      rw = zero + temp;
    }
  }
  temp = rw - zero, lw = zero;
  for (int i = 1; i < n; i++)
  if (i != r_num) {
    rd[i] = getDistance(r_num, i);
    if (temp > rd[i])
      temp = rd[i], lw = rw - rd[i], l_num = i;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44