Submission #123494

#	Time	Username	Problem	Language	Result	Execution time	Memory
123494		baqargam	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	86 ms	10232 KiB

railroad

#include "bits/stdc++.h"
#include "railroad.h"

using namespace std;

long long j,l,dp[16][1000000],g[100],res=1000000000000000000;
vector<pair<int,int> >v;

long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = (int) s.size();
    for(int i=0;i<(1<<n);i++){
        int ct=__builtin_popcount(i);
        v.push_back({ct,i});
    }
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++)
            dp[j][i]=1000000000000000000;
    }
    for(int j=0;j<n;j++)
            dp[j][(1<<j)]=0;
    for(int id=0;id<v.size();id++){
        int a=v[id].second;
        for(j=a,l=0;j>0;j>>=1,l++)
            g[l]=j&1;
        for(int j=0;j<l;j++){
            if(g[j])
                for(int i=0;i<n;i++){
                    if(!g[i])
                        dp[i][a^(1<<i)]=min(dp[i][a^(1ll<<i)],
                                            dp[j][a]+max(0,t[j]-s[i]));
                                            //cout<<a<<"  "<<i<<" "<<j<<" "<<dp[j][a]<<" "<<t[j]<<" "<<s[i]<<endl;;
            }
        }
    }
    /*/
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            cout<<dp[j][i]<<" ";
        }
        cout<<"   "<<i<<endl;
    }
    /**/
    for(int i=0;i<n;i++){
        res=min(res,dp[i][(1<<n)-1]);
    }
    return res;
}

Compilation message (stderr)

railroad.cpp:42:5: warning: "/*" within comment [-Wcomment]
     /**/
      
railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int id=0;id<v.size();id++){
                  ~~^~~~~~~~~

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