이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
long long memo[20][100000];
int n;
int arr1[20],arr2[20];
long long dp(int prev,int bm){
if (bm == (1<<n)-1) return 0;
if (memo[prev][bm] != -1) return memo[prev][bm];
memo[prev][bm] = 1e18;
for (int i = 0; i < n; i++){
if (bm & (1<<i)) continue;
int cost = max(0,arr2[prev]-arr1[i]);
memo[prev][bm] = min(memo[prev][bm],dp(i,bm+(1<<i))+cost);
}
return memo[prev][bm];
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
n = (int) s.size();
if (n > 20){
vector<ii> up,down;
for (int i = 0; i < n; i++){
if (s[i] <= t[i]) up.push_back(ii(s[i],t[i]));
else down.push_back(ii(s[i],t[i]));
}
sort(up.begin(),up.end());
sort(down.begin(),down.end());
int p1 = 0,p2 = 0;
int pos = 0;
long long ans = 0;
while (p1 != up.size() && p2 != down.size()){
if (p1 == up.size()){
int s = down[p2].first, t = down[p2].second;
ans += max(pos-s,0);
pos = t;
p2++;
}
else if (p2 == up.size()){
int s = up[p1].first, t = up[p2].second;
ans += max(pos-s,0);
pos = t;
p1++;
}
else{
int s1 = down[p2].first, t1 = down[p2].second;
int s2 = up[p1].first, t2 = up[p2].second;
if (t2 > s1){
ans += max(pos-s1,0);
pos = t1;
p2++;
}
else{
ans += max(pos-s2,0);
pos = t2;
p1++;
}
}
}
return ans;
}
for (int i = 0; i < n; i++){
arr1[i] = s[i];
arr2[i] = t[i];
}
for (int i = 0; i < 20; i++)for (int j = 0; j < 100000; j++) memo[i][j] = -1;
long long ans = 1e18;
for (int i = 0; i < n; i++) ans = min(ans,dp(i,1<<i));
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (p1 != up.size() && p2 != down.size()){
~~~^~~~~~~~~~~~
railroad.cpp:32:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (p1 != up.size() && p2 != down.size()){
~~~^~~~~~~~~~~~~~
railroad.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (p1 == up.size()){
~~~^~~~~~~~~~~~
railroad.cpp:39:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
else if (p2 == up.size()){
~~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |