Submission #604851

#	Time	Username	Problem	Language	Result	Execution time	Memory
604851		MohamedFaresNebili	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	74 ms	23388 KiB

railroad

#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
 
            using namespace std;
 
            using ll = long long;
            using ii = pair<ll, ll>;
            using vi = vector<int>;
 
            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound
 
            const int oo = 1000 * 1000 * 1000 + 7;
 
                    int N, A[16][2]; ll DP[16][(1 << 16)];
                    ll solve(int i, int mask) {
                        if(__builtin_popcount(mask) == N)
                            return 0;
                        if(DP[i][mask] != -1) return DP[i][mask];
                        ll best = 1000000000000000007;
                        for(int l = 0; l < N; l++) {
                            if(mask & (1 << l)) continue;
                            ll cur = max(0, A[i][1] - A[l][0]);
                            best = min(best, cur + solve(l, mask | (1 << l)));
                        }
                        return DP[i][mask] = best;
                    }
 
                    long long plan_roller_coaster(vector<int> S, vector<int> T) {
                        N = (int)S.size();
                        memset(DP, -1, sizeof DP);
                        ll res = 1000000000000000007;
                        for(int l = 0; l < N; l++)
                            A[l][0] = S[l], A[l][1] = T[l];
                        for(int l = 0; l < N; l++)
                            res = min(res, solve(l, (1 << l)));
                        return res;
                    }

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