Submission #789683

#	Time	Username	Problem	Language	Result	Execution time	Memory
789683		1ne	Roller Coaster Railroad (IOI16_railroad)	C++14	64 / 100	68 ms	11092 KiB

railroad

#include "railroad.h"
#include <cstdio>
#include <cassert>
#pragma once
#include <vector>
#include <bits/stdc++.h>
using namespace std;
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t){
	int n = (int)s.size();
	if (n > 16){
		vector<int>order(n);
		iota(order.begin(),order.end(),0);
		sort(order.begin(),order.end(),[&](int i,int j){
		   return t[i] < t[j];
		});
		vector<int>brr = s;
		sort(brr.begin(),brr.end());
		int cnt = 0;
		int pos = 0;
		int v = 0;
		for (int j = n - 1;j>=0;--j){
			while(!brr.empty() && brr.back() >= t[order[j]]){
				v = brr.back();
				brr.pop_back();
				++pos;
			}
			if (pos + cnt < n - j){
				cnt++;
			}
			else if (pos == 1 && s[order[j]] > t[order[j]]){
				cnt++;
			}
			else if (j + 1 + cnt < n && pos + cnt == n - j && v == s[order[j]] && t[order[j + 1 + cnt]] > v){
				cnt++;
			}	
		}
		if (cnt <= 1){
			return 0;
		}  
		return 1;
	}
	vector<vector<long long>>dp((1<<n),vector<long long>(n,1e18));
	for (int i = 0;i<n;++i){
		dp[(1<<i)][i] = 0;
	}
	long long v = 1e18;
	auto cost = [&](int i,int j){
		if (t[i] > s[j])return t[i] - s[j];
		return 0;
	};
	for (int i = 0;i<(1<<n);++i){
		for (int j = 0;j<n;++j){
			if (i & (1<<j)){
				for (int k = 0;k<n;++k){
					if ((i & (1<<k)) == 0){
						dp[i ^ (1<<k)][k] = min(dp[i][j] + cost(j,k),dp[i ^ (1<<k)][k]);
					}
				}
			}
		}
	}
	for (int i = 0;i<n;++i){
		v = min(v,dp[(1<<n) - 1][i]);
	}
	return v;
}

Compilation message (stderr)

railroad.cpp:4:9: warning: #pragma once in main file
    4 | #pragma once
      |         ^~~~

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