이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <ctype.h>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin (),v.end()
using namespace std;
int n;
LL dp[(1<<16)+4][16+4],ans=mod*mod;
vector<int> s,t;
int Main()
{
for (int i = 0; i < (1 << n); i++)
for (int j = 0; j <= n; j++)
dp[i][j] = mod*mod;
for (int j = 0; j < n; j++)
dp[1 << j][j] = 0;
for (int mask = 1; mask < (1 << n); mask++)
for (int j = 0; j < n; j++)
if (((1 << j) & mask))
for (int i = 0; i < n; i++)
if (!((1 << i) & mask))
dp[mask | (1 << i)][i] = min(dp[mask | (1 << i)][i], max(t[j] - s[i], 0) + dp[mask][j]);
for (int j = 0; j < n; j++)
ans = min(ans, dp[(1 << n) - 1][j]);
return 0;
}
LL plan_roller_coaster(vector<int> S, vector<int> T)
{
n = S.size();
s = S;
t = T;
Main();
return ans;
}
#ifdef death
int main()
{
int N;
vector<int> S,T;
cin >> N;
for (int i = 0; i < N; i++)
{
S.PB(0);
cin >> S.back();
T.PB(0);
cin >> T.back();
}
cout << plan_roller_coaster(S,T) << endl;
return 0;
}
#endif
/*
*/
# | 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... |