Submission #1118350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118350		crafticat	Shortcut (IOI16_shortcut)	C++17	0 / 100	2 ms	352 KiB

shortcut

#include <bits/stdc++.h>
#ifndef DEBUG
#include "shortcut.h"
#endif

using namespace std;

template<typename T>
using V = vector<T>;
using ll = long long;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
using pl = pair<ll, ll>;
constexpr int INF = 1e9 + 7;
#define ckmax(a,b) a = max(a,b)
#define ckmin(a,b) a = min(a,b)

#define F0R(i, n) for (int i = 0; i < n;i++)
#define FOR(i, j , n) for (int i = j ;i < n;i++)

int n;

pl findFar(ll a, ll l, ll r, vl d, vl leng) {
    pl results = {d[a],a};
    ll path = 0;
    for (ll i = a + 1; i <= r; ++i) {
        path += leng[i - 1];
        ckmax(results, make_pair(path + d[i],i));
    }
    path = 0;
    for (ll i = a - 1; i >= l; --i) {
        path += leng[i];
        ckmax(results, make_pair(path + d[i],i));
    }
    return results;
}

ll solveSep(ll a, ll b, vl d, vl leng) {
    ll x = findFar(a, a, b , d, leng).second;
    pl results = findFar(x, a, b, d, leng);
    return results.first + (results.second != x ? d[x] : 0);
}

ll test(ll a, ll b, vl leng, vl d, ll c) {
    ll cycle = c;
    FOR(i, a, b) {
        cycle += leng[i];
    }

    ll ans = 0;
    if (a - 0 > 0) ckmax(ans, solveSep(0, a, d, leng));
    if (n - 1 - b > 0) ckmax(ans, solveSep(b, n - 1, d, leng));

    ll farA = d[a], farB = d[b], distA = 0, distB = 0;
    for (int i = a - 1; i >= 0; --i) {
        distA += leng[i];
        ckmax(farA, distA + d[i]);
    }
    for (int i = b + 1; i < n; ++i) {
        distB += leng[i - 1];
        ckmax(farB, distB + d[i]);
    }
    d[a] = farA;
    d[b] = farB;

    FOR(i, a, b + 1) {
        ll dist = 0;
        FOR(j, i + 1, b + 1) {
            dist += leng[j - 1];
            ckmax(ans, min(dist, cycle - dist) + d[j] + d[i]);
        }
    }

    ll results = max(ans, farA + farB + c);

    return max(ans, farA + farB);
}

long long find_shortcut(int N, std::vector<int> l2, std::vector <int> d2, int c) {
    vl l(N - 1), d(N);
    F0R(i, N) {
        if (i != N - 1) l[i] = l2[i];
        d[i] = d2[i];
    }
    n = N;

    ll ans = 1e9;
    F0R(i, N) {
        FOR(j,i + 1, N) {
            ckmin(ans, test(i, j ,l, d, c));
        }
    }
    return ans;
}

#if DEBUG
int main()
{
    int n, c;
    assert(2 == scanf("%d%d", &n, &c));

    std::vector<int> l(n - 1);
    std::vector<int> d(n);
    for (int i = 0; i < n - 1; i++)
        assert(1 == scanf("%d", &l[i]));
    for (int i = 0; i < n; i++)
        assert(1 == scanf("%d", &d[i]));

    long long t = find_shortcut(n, l, d, c);

    printf("%lld\n", t);

    return 0;
}
#endif

Compilation message (stderr)

shortcut.cpp: In function 'll test(ll, ll, vl, vl, ll)':
shortcut.cpp:75:8: warning: unused variable 'results' [-Wunused-variable]
   75 |     ll results = max(ans, farA + farB + c);
      |        ^~~~~~~

• 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