Submission #119247

#	Time	Username	Problem	Language	Result	Execution time	Memory
119247		someone_aa	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	81 ms	7384 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
const int maxn = 17;
ll dp[maxn][(1<<maxn)], n;

bool comparator(pii a, pii b) {
    return a.second <= b.first && b.second > a.first;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    n = (int) s.size();
    if(n <= 16) {
        for(int i=1;i<(1<<n);i++) {
            //cout<<i<<": \n";
            for(int c=0;c<n;c++) {
                if(!((1<<c)&i)) continue;

                dp[c][i] = LLONG_MAX;
                if(__builtin_popcount(i) == 1) {
                    dp[c][i] = 0;
                }
                else {
                    for(int p=0;p<n;p++) {
                        if(!((1<<p)&i) || c == p) continue;
                        ll cost = max(0LL, 1LL * t[p] - s[c]);
                        dp[c][i] = min(dp[c][i], dp[p][(i^(1<<c))] + cost);
                    }
                }
                //cout<<c<<" - "<<dp[c][i]<<"\n";
            }
        }

        ll result = LLONG_MAX;
        for(int i=0;i<n;i++) {
            result = min(result, dp[i][(1<<n)-1]);
        }
        return result;
    }
    else {
        vector<pair<int,int> > v;
        for(int i=0;i<n;i++) {
            v.pb(mp(s[i], t[i]));
        }

        sort(v.begin(), v.end(), comparator);

        for(int i=0;i<n-1;i++) {
            if(v[i].second > v[i+1].first) return 1;
        }

        return 0;
    }
}

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