Submission #1065573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065573		onbert	Shortcut (IOI16_shortcut)	C++17	31 / 100	2009 ms	604 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 5, INF = 1e18;
int n, c;
pair<int,int> a[maxn];

pair<int,int> calc(vector<pair<int,int>> vec) {
    int sz = vec.size();
    int sum = 0;
    for (auto [L, D]:vec) sum += L;
    int mid = 0, dist = 0;
    while (dist + vec[mid].first <= sum - dist - vec[mid].first) {
        dist += vec[mid].first;
        mid++;
    }
    int mx = 0, mxi = 0;
    dist = 0;
    for (int i=1;i<=mid;i++) {
        dist += vec[i-1].first;
        if (vec[i].second + dist > mx) mxi = i, mx = vec[i].second + dist;
    }
    // cout << mx << " " << mxi << endl;
    dist = 0;
    for (int i=sz-1;i>mid;i--) {
        dist += vec[i].first;
        if (vec[i].second + dist > mx) mxi = i, mx = vec[i].second + dist;
    }
    // cout << mx << " " << mxi << endl;
    // cout << "test\n";
    // for (auto [x, y]:vec) cout << x << " " << y << endl;
    // cout << "ret " << mx << " " << mxi << endl;
    // cout << endl;
    return {mx + vec[0].second, mxi};
}

int calc2(vector<pair<int,int>> vec) {
    int sz = vec.size();
    int ps[sz]; ps[0] = 0;
    for (int i=1;i<sz;i++) ps[i] = ps[i-1] + vec[i-1].first;
    int sum = ps[sz-1] + c;
    int mx = 0;
    for (int i=0;i<sz;i++) for (int j=i+1;j<sz;j++) {
        int dist = ps[j] - ps[i];
        if (sum - dist < dist) dist = sum - dist;
        mx = max(dist + vec[i].second + vec[j].second, mx);
    }
    return mx;
}

int cnt(int l, int r) {
    if (l==r) return INF;
    int sz = r-l+1;
    vector<pair<int,int>> cur;
    int dist = 0, mx = 0;
    int ps[n]; ps[0] = 0;
    for (int i=1;i<n;i++) ps[i] = ps[i-1] + a[i-1].first;
    for (int i=l;i>=0;i--) {
        // if (i!=l) MX += a[i].first;
        // lhs = max(a[i].second + MX, lhs);
        // MX = max(a[i].second, MX);
        mx = max(ps[l] - ps[i] + a[i].second, mx);
    }
    cur.push_back({a[l].first, mx});
    
    for (int i=l+1;i<r;i++) cur.push_back({a[i].first, a[i].second});

    dist = mx = 0;
    for (int i=r;i<n;i++) {
        // if (i!=r) MX += a[i-1].first;
        // rhs = max(a[i].second + MX, rhs);
        // MX = max(a[i].second, MX);
        mx = max(ps[i] - ps[r] + a[i].second, mx);
    }
    cur.push_back({c, mx});
    

    int lhs = 0;
    for (int i=0;i<=l;i++) for (int j=i+1;j<=l;j++) lhs = max(ps[j]-ps[i] + a[i].second + a[j].second, lhs);
    int rhs = 0;
    for (int i=r;i<n;i++) for (int j=i+1;j<n;j++) rhs = max(ps[j]-ps[i] + a[i].second + a[j].second, rhs);
    int both = 0;
    for (int i=0;i<=l;i++) for (int j=r;j<n;j++) {
        int dist = ps[j] - ps[i] - (ps[r] - ps[l]) + min(ps[r] - ps[l], c);
        both = max(dist + a[i].second + a[j].second, both);
    }
    return max({calc2(cur), lhs, rhs, both});

    // int start = calc(cur).second;
    // vector<pair<int,int>> cur2;
    // for (int i=0;i<sz;i++) cur2.push_back(cur[(i+start)%sz]);
    // int val = calc(cur2).first;
}

long long find_shortcut(int32_t N, vector<int32_t> L, vector<int32_t> d, int32_t C) {
    if (N >= 1000) return 69420;
    n = N, c = C;
    for (int i=0;i<n-1;i++) a[i] = {L[i], d[i]};
    a[n-1] = {-1, d[n-1]};

    int ps[n]; ps[0] = 0;
    for (int i=1;i<n;i++) ps[i] = ps[i-1] + a[i-1].first;

    int ans = 0;
    for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) ans = max(ps[j]-ps[i] + a[i].second + a[j].second, ans);
    for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) ans = min(cnt(i, j), ans);
    return ans;

    for (int i=0;i<n-1;i++) {
        // for (int j=i+1;j<n;j++) cout << cnt(i, j) << " ";
        // cout << endl;
        int l = i, r = n-1;
        while (l<r) {
            int mid = (l+r)/2;
            if (cnt(i, mid) < cnt(i, mid+1)) r = mid;
            else l = mid+1;
        }
        ans = min(cnt(i, l), ans);
    }
    return ans;
}

Compilation message (stderr)

shortcut.cpp: In function 'long long int cnt(long long int, long long int)':
shortcut.cpp:54:9: warning: unused variable 'sz' [-Wunused-variable]
   54 |     int sz = r-l+1;
      |         ^~
shortcut.cpp:56:9: warning: variable 'dist' set but not used [-Wunused-but-set-variable]
   56 |     int dist = 0, mx = 0;
      |         ^~~~

• 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