Submission #1118397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118397		crafticat	Shortcut (IOI16_shortcut)	C++17	31 / 100	2036 ms	604 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 = {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];
}

void computeDCDP(vl &opt, vl &dp, ll l, ll r, ll boundA, ll boundB, function<ll(ll a,ll b)> f) {
    if (r -l <= 0) return;

    ll mid = (l + r) / 2;
    FOR(i, max(boundA, mid + 1), boundB) {
        ll v = f(mid, i);
        if (v > dp[mid]) {
            dp[mid] = v;
            opt[mid] = i;
        }
    }

    computeDCDP(opt, dp, l, mid, boundA, opt[mid] + 1,f);
    computeDCDP(opt, dp, mid + 1, r, opt[mid], boundB,f);
}

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;

    vl prefix(n + 1);
    F0R(i, n - 1) {
        prefix[i + 1] = prefix[i] + leng[i];
    }

    vl opt(n, b), dp(n, 0);
    computeDCDP(opt, dp, a, b + 1, a, b + 1,[prefix, d,cycle](ll a,ll b) {
        ll dist = prefix[b] - prefix[a];
        return min(dist, cycle - dist) + d[a] + d[b];
    });
    F0R(i, n) {
        ckmax(ans, dp[i]);
    }

    if (ans == 100) {
        int stop = 25;
    }
    FOR(i, a + 1, b + 1) {
        if (opt[i] < opt[i - 1] && opt[i] != 0 && opt[i - 1] != 0)  {
            int stop = 25;
        }
    }
    return ans;
}

vl l, d;
ll c;

ll compute2(ll i, ll j) {
    return test(i, j ,l, d, c);
}

ll compute(ll i) {
    ll ans = 1e18;
    FOR(j, i + 1, n) {
        ckmin(ans, compute2(i, j));
    }

    return ans;
}

bool getSlope(ll x) {
    if (x + 1 >= n) return false;

    ll next = compute(x + 1);
    ll cur = compute(x);
    if (next > cur) return false;
    if (next < cur) return true;
    if (next == cur) return getSlope(x + 1);
    exit(5); // not pos
}

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

    ll ans = 1e18;

    F0R(i, N)
        ckmin(ans, compute(i));

    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:102:13: warning: unused variable 'stop' [-Wunused-variable]
  102 |         int stop = 25;
      |             ^~~~
shortcut.cpp:106:17: warning: unused variable 'stop' [-Wunused-variable]
  106 |             int stop = 25;
      |                 ^~~~

• 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