Submission #71608

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
71608	2018-08-25 08:31:34	top34051	Shortcut (IOI16_shortcut)	C++17	0 / 100	5 ms	460 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.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 3e5 + 5;
const ll inf = 1e16;
int n;
ll cost, len[maxn], val[maxn];
ll pos[maxn];
int a[maxn], b[maxn];
bool check(ll k) {
//    printf("check %lld\n",k);
    ll r1 = -inf, r2 = inf, c1 = -inf, c2 = inf;
    ll mx = -inf;
    for(int i=0,j=-1;i<n;i++) {
        int x = a[i];
        while(j+1<n && val[a[i]]-pos[a[i]] > k-(val[b[j+1]]+pos[b[j+1]])) {
            j++;
            int y = b[j];
            mx = max(mx,pos[y]+val[y]);
        }
        r1 = max(r1, pos[x] + val[x] - k + cost + mx);
        c1 = max(c1, -pos[x] + val[x] - k + cost + mx);
    }
    ll mn = inf;
    for(int i=0,j=-1;i<n;i++) {
        int x = a[i];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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