Submission #1118352

#TimeUsernameProblemLanguageResultExecution timeMemory
1118352crafticatShortcut (IOI16_shortcut)C++17
31 / 100
2052 ms764 KiB
#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 = {0,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) {
    if (a == 0 && b == 1) {
        int stop = 25;
    }
    ll x = findFar(a, a, b , d, leng).second;
    pl results = findFar(x, a, b, d, leng);
    return results.first + d[x];
}

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;
    ll f1 = solveSep(0, a, d, leng);
    if (a - 0 > 0) ckmax(ans, f1);
    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]);
        }
    }

    if (ans < 15) {
        int stop = 25;
    }
    return ans;
}

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 = 1e18;
    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 solveSep(ll, ll, vl, vl)':
shortcut.cpp:41:13: warning: unused variable 'stop' [-Wunused-variable]
   41 |         int stop = 25;
      |             ^~~~
shortcut.cpp: In function 'll test(ll, ll, vl, vl, ll)':
shortcut.cpp:80:13: warning: unused variable 'stop' [-Wunused-variable]
   80 |         int stop = 25;
      |             ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...