#include "railroad.h"
#include<iostream>
#include<algorithm>
using namespace std;
long long DP[20][100000];
int n;
long long graph[20][20];
long long f(int x){
if(x>0)return x;
return 0;
}
long long min(int x, int y){
if(x<y)return x;
return y;
}
bool BIT(int n, int k){
if((n >> (k )) & 1)return true;
return false;
}
long long trabalha(int start, int mask){
if(DP[start][mask]!=-1)return DP[start][mask];
//cout<<start<<" "<<mask<<endl;
DP[start][mask]=200000000000;
for(int i=0;i<n;i++){
if(BIT(mask,i) & i!=start){
DP[start][mask]=min(DP[start][mask],trabalha(i,mask^(1<<(start)))+graph[i][start]);
}
}
if(DP[start][mask]==200000000000)DP[start][mask]=0;
return DP[start][mask];
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
n=s.size();
/*if(n<=16){
for(int i=0;i<n;i++){//cout<<t[i]<<" "<<s[i]<<endl;
for(int j=0;j<n;j++){
graph[i][j]=f(t[i]-s[j]);//ir de i para j
//cout<<graph[i][j]<<" ";
}//cout<<endl;
}
long long ans=200000000000;
for(int i=0;i<n;i++){
for(int j=0;j<(1<<n);j++)DP[i][j]=-1;
}
for(int i=0;i<n;i++){
ans=min(ans,trabalha(i,(1<<n)-1));
}
return ans;
}*/
pair<int,int> arr[n];
for(int i=0;i<n;i++){
arr[i].first=s[i];
arr[i].second=t[i];
}
sort(arr,arr+n);
int maximo[n];
for(int i=0;i<n;i++){
int hi,lo;
lo=-1;
hi=n;
while(hi-lo>1){
int mid=(hi+lo)/2;
if(arr[i].second<=arr[mid].first)hi=mid;
else lo=mid;
}
maximo[i]=hi;
//cout<<hi<<endl;
}
int sum[n];
for(int i=0;i<n;i++){
sum[i]=0;
}
for(int i=0;i<n;i++){
if(maximo[i]<n)sum[maximo[i]]++;
}
for(int i=1;i<n;i++){
sum[i]+=sum[i-1];
}
//for(int i=0;i<n;i++)cout<<sum[i]<<endl;
bool b[n];
for(int i=0;i<n;i++){
b[i]=true;
}
int next[n];
for(int i=0;i<n;i++){
int minimo=0;
for(int j=0;j<n;j++){
if(b[j] && sum[minimo]-minimo>sum[j]-j)minimo=j;
}
if(i>0 && minimo<maximo[next[i-1]])return 0;
if(sum[minimo]<minimo)return 1;
if(sum[minimo]>minimo)return 0;
b[minimo]=false;
for(int j=maximo[minimo];j<n;j++){
sum[j]--;
}
next[i]=minimo;
}
return 0;
}
Compilation message
railroad.cpp: In function 'long long int trabalha(int, int)':
railroad.cpp:25:21: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
if(BIT(mask,i) & i!=start){
~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
n = 2 |
| 2 |
Correct |
2 ms |
356 KB |
n = 2 |
| 3 |
Correct |
2 ms |
432 KB |
n = 2 |
| 4 |
Correct |
2 ms |
508 KB |
n = 2 |
| 5 |
Correct |
3 ms |
508 KB |
n = 2 |
| 6 |
Incorrect |
2 ms |
524 KB |
answer is not correct: 1 instead of 523688153 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
n = 2 |
| 2 |
Correct |
2 ms |
356 KB |
n = 2 |
| 3 |
Correct |
2 ms |
432 KB |
n = 2 |
| 4 |
Correct |
2 ms |
508 KB |
n = 2 |
| 5 |
Correct |
3 ms |
508 KB |
n = 2 |
| 6 |
Incorrect |
2 ms |
524 KB |
answer is not correct: 1 instead of 523688153 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
131 ms |
7112 KB |
n = 199999 |
| 2 |
Correct |
142 ms |
7112 KB |
n = 199991 |
| 3 |
Correct |
147 ms |
7112 KB |
n = 199993 |
| 4 |
Correct |
98 ms |
7112 KB |
n = 152076 |
| 5 |
Correct |
66 ms |
7112 KB |
n = 93249 |
| 6 |
Correct |
102 ms |
7112 KB |
n = 199910 |
| 7 |
Correct |
112 ms |
7112 KB |
n = 199999 |
| 8 |
Correct |
112 ms |
7112 KB |
n = 199997 |
| 9 |
Correct |
123 ms |
7112 KB |
n = 171294 |
| 10 |
Incorrect |
107 ms |
7112 KB |
answer is not correct: 1 instead of 0 |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
n = 2 |
| 2 |
Correct |
2 ms |
356 KB |
n = 2 |
| 3 |
Correct |
2 ms |
432 KB |
n = 2 |
| 4 |
Correct |
2 ms |
508 KB |
n = 2 |
| 5 |
Correct |
3 ms |
508 KB |
n = 2 |
| 6 |
Incorrect |
2 ms |
524 KB |
answer is not correct: 1 instead of 523688153 |
| 7 |
Halted |
0 ms |
0 KB |
- |
