Submission #1025167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025167		slivajan	Shortcut (IOI16_shortcut)	C++17	31 / 100	2025 ms	592 KiB

shortcut

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

typedef long long un;
typedef vector<un> vuc;


#define REP(i, a, b) for(un i = a; i < b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()

constexpr un INF = INT64_MAX;


un spocti_kartac(int n, std::vector<int> l, std::vector<int> d, un start, un smer){

    un ptr = start;
    un ret = 0;

    un soucet = 0;

    while((ptr >= 0) and (ptr < n)){
        ret = max(ret, soucet + d[ptr]);
        if (smer == 1) soucet += l[ptr];
        else if (smer == -1) soucet += l[ptr-1];

        ptr += smer;
    }

    return ret;

}

un eval_range(int n, std::vector<int> l, std::vector<int> d, int a, int b){
    un ret = 0;

    REP(i, a, b+1){
        un j = i;
        un soucet = 0;

        while(j < b){
            soucet += l[j];
            j++;
            ret = max(ret, d[i] + d[j] + soucet);
        }
    }

    return ret;
}

tuple<vuc, vuc> change_to_loop(int n, std::vector<int> l, std::vector<int> d, int c, int a, int b){

    un new_n = b-a+1;

    vuc new_l (new_n);
    vuc new_d (new_n);

    REP(i, 0, new_n-1){
        new_l[i] = l[a+i];
        new_d[i] = d[a+i];
    }

    new_l[new_n-1] = c;
    new_d[new_n-1] = d[a+new_n-1];

    new_d[0] = max(new_d[0], spocti_kartac(n, l, d, a, -1));
    new_d[new_n-1] = max(new_d[new_n-1], spocti_kartac(n, l, d, b, 1));
    
    return {new_l, new_d};

}

un eval_loop(int n, std::vector<un> l, std::vector<un> d){

    un celkovy = 0;
    REP(i, 0, n) celkovy += l[i];

    un ret = 0;

    REP(i, 0, n){
        un j = (i+1) % n;
        un soucet = l[i];

        while(j != i){
            ret = max(ret, d[i] + d[j] + min(soucet, celkovy-soucet));
            soucet += l[j];
            j = (j+1) %n;
        }
    }

    return ret;
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    un ret = INF;

    REP(a, 0, n) REP(b, a+1, n) {
        vuc loop_l, loop_n;
        tie(loop_l, loop_n) = change_to_loop(n, l, d, c, a, b);
        ret = min(ret, max({eval_loop((un)loop_l.size(), loop_l, loop_n), eval_range(n, l, d, 0, a), eval_range(n, l, d, b, n-1)}));
    }

    return ret;
}

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