Submission #1013169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013169		ProtonDecay314	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	2063 ms	4180 KiB

railroad

/*
For subtask 3, consider, for each rail, the prefix it can reach

4 2 1 0 -> doesn't work
3 1 1 1

4 2 2 0 -> works
3 2 1 1

4 3 1 0 -> works

4 2 1 1 -> doesn't work

2 2 4 0 -> doesn't work

The cost of a placement is.. hmm

max(t[i] - s[i + 1], 0) + max(t[i - 1] - s[i], 0) -> if separated more than two apart

t[i] t[i + 1] t[i + 2] t[i + 3]
s[i] s[i + 1] s[i + 2] s[i + 3]

c = max(t[i] - s[i + 1], 0) + max(t[i + 1] - s[i + 2], 0) + max(t[i + 2] - s[i + 3], 0)
c' = max(t[i] - s[i + 2], 0) + max(t[i + 2] - s[i + 1], 0) + max(t[i + 1] - s[i + 3], 0)
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

ll plan_roller_coaster(vi s, vi t) {
    ll n = s.size();

    // Construct DP table

    reverse(s.begin(), s.end()); // Lol thanks for the idea StackOverflow HAHAH
    reverse(t.begin(), t.end());
    s.pb(0);
    t.pb(0);
    reverse(s.begin(), s.end()); // Conjugation is crazy
    reverse(t.begin(), t.end());

    s.pb(INF(int));
    t.pb(INF(int));

    // It's time to bubble sort
    LI(rep, 0, n * n) {
        LI(i, 0, n - 1) {
            LI(j, i + 1, n) {
                if(j - i == 1) {
                    /*
                    c = max(t[i] - s[i + 1], 0) + max(t[i + 1] - s[i + 2], 0) + max(t[i + 2] - s[i + 3], 0)
                    c' = max(t[i] - s[i + 2], 0) + max(t[i + 2] - s[i + 1], 0) + max(t[i + 1] - s[i + 3], 0)
                    */
                    int c = max(t[i] - s[i + 1], 0) + max(t[i + 1] - s[i + 2], 0) + max(t[i + 2] - s[i + 3], 0);
                    int cpr = max(t[i] - s[i + 2], 0) + max(t[i + 2] - s[i + 1], 0) + max(t[i + 1] - s[i + 3], 0);

                    if(cpr < c) {
                        swap(t[i + 1], t[i + 2]);
                        swap(s[i + 1], s[i + 2]);
                    }
                } else {
                    
                    int c = max(t[i + 1] - s[i + 2], 0) + max(t[i] - s[i + 1], 0) + max(t[j + 1] - s[j + 2], 0) + max(t[j] - s[j + 1], 0);
                    int cpr = max(t[j + 1] - s[i + 2], 0) + max(t[i] - s[j + 1], 0) + max(t[i + 1] - s[j + 2], 0) + max(t[j] - s[i + 1], 0);

                    if(cpr < c) {
                        swap(t[i + 1], t[j + 1]);
                        swap(s[i + 1], s[j + 1]);
                    }
                }
            }
        }
    }

    ll ans = 0ll;

    LI(i, 0, n + 1) {
        ans = ans + max((ll)(t[i]) - (ll)(s[i + 1]), 0ll);
    }

    return ans;
}

#ifdef DEBUG
int main() {
    int n;
    cin >> n;

    vi s(n, 0);
    vi t(n, 0);

    LI(i, 0, n) {
        cin >> s[i] >> t[i];
    }

    cout << plan_roller_coaster(s, t) << endl;
}
#endif

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36