Submission #71627

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
71627	2018-08-25 09:13:58	top34051	Shortcut (IOI16_shortcut)	C++17	0 / 100	3 ms	492 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 = 1e5 + 5;
const ll inf = 1e16;
int n;
ll cost, len[maxn], val[maxn];
ll pos[maxn];
int a[maxn], b[maxn];
ll tree[maxn];
bool check(ll k) {
//    printf("check %lld\n",k);
    ll r1 = -inf, r2 = inf, c1 = -inf, c2 = inf;
    ll mx = -inf, mn = inf;
    for(int i=0,j=-1;i<n;i++) {
        int x = a[i];
//        printf("x = %d : %lld\n",x,val[a[i]]+pos[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];
//            printf("\ty = %d\n",y);
            mx = max(mx, pos[y]+val[y]);
            mn = min(mn, pos[y]-val[y]);
        }
        r1 = max(r1, pos[x] + val[x] - k + cost + mx);
        c2 = min(c2, pos[x] - val[x] + k - cost - mx);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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