Submission #299455

#	Time	Username	Problem	Language	Result	Execution time	Memory
299455		oscarsierra12	Shortcut (IOI16_shortcut)	C++14	23 / 100	2067 ms	512 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std ;

const int N = 3001 ;
const long long oo = 1e17 ;

long long mx[8 * N], lazy[8 * N] ;
long long dstSuf[N] ;
long long ps[N] ;

void propagate ( int node ) {
    lazy [node * 2] += lazy[node] ;
    lazy [node * 2 + 1] += lazy[node] ;
    mx[node] += lazy[node] ;
    lazy[node] = 0;
}

void update ( int node, int l, int r, int a, int b, int v ) {
    if ( r < l ) return ;
    propagate(node) ;
    if ( b < l || r < a ) return ;
    if ( a <= l && r <= b ) {
        lazy[node] = v;
        propagate(node) ;
        return ;
    }
    int m = (l+r) / 2 ;
    update ( node * 2, l, m, a, b, v ) ;
    update ( node * 2 + 1, m+1, r, a,b, v ) ;
    mx[node] = max ( mx[node*2], mx[node*2+1] ) ;
}

long long query ( int node, int l, int r, int a, int b ) {
    if ( r < l ) return 0 ;
    propagate ( node ) ;
    if ( b < l || r < a ) return 0 ;
    if ( a <= l && r <= b ) return mx[node] ;
    int m = (l+r) / 2;
    return max ( query(node*2, l, m, a, b ), query ( node*2+1, m+1, r, a, b) ) ;
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    l.push_back ( 0 ) ;
    for ( int i = n-1 ; i >= 0 ;--i )
        dstSuf[i] = max ( dstSuf[i+1] + l[i], 1ll * d[i+1] + l[i] ) ;
    for ( int i = 1 ; i < n ; ++i )
        ps[i] = ps[i-1] + l[i-1] ;
    long long ans = oo, mx = -oo ;
    for ( int i = 0 ; i < n ; ++i )  {
        for ( int j = 0 ; j < i ; ++j ) {
            mx = -oo ;
            for ( int k = 0 ; k < n ; ++k ) {
                for ( int h = 0 ; h < k ; ++h ) {
                    mx = max ( mx, min(ps[k] - ps[h], min(abs(ps[k] - ps[i]) + abs(ps[h]-ps[j]), abs(ps[k]-ps[j]) + abs(ps[h]-ps[i])) + c ) + d[k] + d[h] ) ;
                }
            }
            ans = min ( ans, mx ) ;
        }
    }
    return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 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