Submission #1020496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020496		vjudge1	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	48 ms	9932 KiB

railroad

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int inf = 1e9 + 100;
const int INF = 1e18 + 100;

int n;
ll dp[1<<16][16];
int s[200100];
int t[200100];

long long plan_roller_coaster(std::vector<int> S, std::vector<int> T){
	n = S.size();
	for(int i = 0; i < n; i++){
		s[i] = S[i];
		t[i] = T[i];
	}
	if(0 && n <= 16){
		for(int x = 0; x < (1<<n); x++){
			fill(dp[x], dp[x] + n, INF);
			if(!x) continue;
			if(__builtin_popcount(x) == 1){
				for(int i = 0; i < n; i++){
					if(x & (1<<i)) dp[x][i] = 0;
				}
			} else{
				for(int i = 0; i < n; i++){
					if(x & (1<<i)){
						int y = x ^ (1<<i);
						for(int j = 0; j < n; j++){
							if(y & (1<<j)){
								dp[x][i] = min(dp[x][i], dp[y][j] + max(0, t[j] - s[i]));
							}
						}
					}
				}
			}
		}
		return *min_element(dp[(1<<n)-1], dp[(1<<n)-1] + n);
	} else{
		vector<int> ord;
		for(int i = 0; i < n; i++){
			ord.push_back(i);
		}
		sort(ord.begin(), ord.end(), [](int i, int j){
			return t[i] < t[j];
		});
		for(int i = 1; i < n; i++){
			if(s[ord[i]] < t[ord[i-1]]) return 1;
		}
		return 0;
	}
}

Compilation message (stderr)

railroad.cpp:6:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0000000000000001e+18' to '2147483647' [-Woverflow]
    6 | const int INF = 1e18 + 100;
      |                 ~~~~~^~~~~

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