Submission #1025101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025101		slivajan	Shortcut (IOI16_shortcut)	C++17	0 / 100	1 ms	344 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()

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;

}

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 = 0;

    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 = max(ret, eval_loop((un)loop_l.size(), loop_l, loop_n));
    }

    return ret;
}

• 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