Submission #388594

#	Time	Username	Problem	Language	Result	Execution time	Memory
388594		Keshi	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	55 ms	7232 KiB

railroad

//In the name of God
#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 2e5 + 100;
const ll maxk = 16;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll dp[maxk][1 << maxk];

ll solmask(vector<int> s, vector<int> t){
	ll n = Sz(s);
	for(ll i = 0; i < (1 << n); i++){
		for(ll j = 0; j < n; j++){
			if(!((i >> j) & 1)) continue;
			ll x = i ^ (1 << j);
			dp[j][i] = inf;
			if(x == 0) dp[j][i] = 0;
			for(ll k = 0; k < n; k++){
				if((x >> k) & 1){
					dp[j][i] = min(dp[j][i], dp[k][x] + max(0, t[j] - s[k]));
				}
			}
		}
	}
	ll ans = inf;
	for(ll i = 0; i < n; i++){
		ans = min(ans, dp[i][(1 << n) - 1]);
	}
	return ans;
}

long long plan_roller_coaster(vector<int> s, vector<int> t) {
	ll n = Sz(s);
    if(n <= 16) return solmask(s, t);
    return 0;
}

/*int main(){
    fast_io;



    return 0;
}*/

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