Submission #291616

#	Time	Username	Problem	Language	Result	Execution time	Memory
291616		shayan_p	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	79 ms	8696 KiB

railroad

// Oh damn! Suddenly you're free to fly...

#include<bits/stdc++.h>
#include "railroad.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 2e5 + 10, mod = 1e9 + 7;
const ll inf = 1e18 + 10;

ll dp[1<<16][16];

void minim(ll &a, ll b){
    a = min(a, b);
}

ll plan_roller_coaster(vector<int> a, vector<int> b){    
    int n = sz(a);
    for(int msk = 0; msk < (1<<n); msk++){
	for(int i = 0; i < n; i++){
	    dp[msk][i] = inf;
	    if(bit(msk, i) && __builtin_popcount(msk) == 1)
		dp[msk][i] = 0;
	}
    }
    for(int msk = 1; msk < (1<<n); msk++){
	for(int i = 0; i < n; i++){
	    if(bit(msk, i) == 0)
		continue;
	    for(int j = 0; j < n; j++){
		if(i == j || bit(msk, j))
		    continue;
		minim(dp[msk | (1<<j)][j], dp[msk][i] + max(int(0), b[i] - a[j]));
	    }
	}
    }
    ll ans = inf;
    for(int i = 0; i < n; i++){
	ans = min(ans, dp[(1<<n)-1][i]);
    }
    return ans;	
}

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