제출 #134740

#제출 시각아이디문제언어결과실행 시간메모리
134740ckodserRoller Coaster Railroad (IOI16_railroad)C++14
34 / 100
139 ms12936 KiB
#include "railroad.h" #include<bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair #define pii pair<ll,ll> #define F first #define S second #define ld long double using namespace :: std; const ll maxn=16; const ll inf=1e17+900; ll ger[maxn][maxn]; ll dp[1<<maxn][maxn]; ll solve17(vector<int> s,vector<int> t){ ll n=s.size(); for(ll i=0;i<n;i++){ for(ll j=0;j<n;j++){ ger[i][j]=max(0,t[i]-s[j]); } } for(ll i=1;i<(1<<n);i++){ for(ll j=0;j<n;j++){ if(i!=(1<<j)){ if((i>>j)&1){ dp[i][j]=inf; for(ll k=0;k<n;k++){ if(((i>>k)&1) && k!=j){ dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+ger[j][k]); } } } } } } ll ans=inf; for(ll i=0;i<n;i++){ ans=min(ans,dp[(1<<n)-1][i]); } return ans; } long long plan_roller_coaster(vector<int> s,vector<int> t) { if(s.size()<=16){ return solve17(s,t); } t.pb(1); s.pb(inf); int n = (int) s.size(); vector<pii> vec; for(ll i=0;i<n;i++){ ll v=s[i]; vec.pb(mp(v,(i+1))); } for(ll i=0;i<n;i++){ ll v=t[i]; vec.pb(mp(v,-(i+1))); } sort(vec.begin(),vec.end()); reverse(vec.begin(),vec.end()); vector<ll> invecs,invect; invecs.resize(n);invect.resize(n); for(ll i=0;i<vec.size();i++){ pii e=vec[i]; ll v=e.F; ll w=e.S; ll x=abs(w)-1; if(w<0){ invect[x]=i; }else{ invecs[x]=i; } } ll sum=0; ll mnn=inf; for(ll i=0;i<vec.size();i++){ pii e=vec[i]; ll v=e.F; ll w=e.S; ll x=abs(w)-1; if(w<0){ mnn=min(mnn,invecs[x]); sum--; }else{ sum++; } if(sum<0)return 1; if(sum==0){ if(mnn<=i && i){ return 1; } } } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:55:13: warning: overflow in implicit constant conversion [-Woverflow]
     s.pb(inf);
             ^
railroad.cpp:72:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=0;i<vec.size();i++){
                ~^~~~~~~~~~~
railroad.cpp:74:5: warning: unused variable 'v' [-Wunused-variable]
  ll v=e.F;
     ^
railroad.cpp:86:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=0;i<vec.size();i++){
                ~^~~~~~~~~~~
railroad.cpp:88:5: warning: unused variable 'v' [-Wunused-variable]
  ll v=e.F;
     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...