Submission #162539

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

railroad

#include <iostream>
#include <bits/stdc++.h>

using namespace std;
//dp[mask][j] = min(dp[mask without j][i]+max(arr[j].first-arr[i].second,0)
/*
4
1 4 5 6
7 3 8 6
*/
long long dp[500000][20];
long long plan_roller_coaster(vector<int> s, vector<int> t){
    int n = s.size();

    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            dp[i][j] = 1e17;
        }
    }
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            if(i-(1<<j) == 0){
                dp[i][j] = (long long)0;
                continue;
            }
            if(i&(1<<j)){
                for(int k=0;k<n;k++){
                    if(j==k){
                        continue;

                    }
                    if(i&(1<<k)){

                        dp[i][j] = min((long long)dp[i][j],dp[i^(1<<j)][k]+max((long long)t[k]-(long long)s[j],(long long)0));
                     //   cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j]<<endl;
                    }

                }
            }
        }
    }
    long long res = 1e17;
    for(int i=0;i<n;i++){

        res = min(res,dp[(1<<n)-1][i]);
    }
    return res;
}
/*
int main(){
    vector<int> v1;
    vector<int> v2;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        v1.push_back(x);
    }
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        v2.push_back(x);
    }
    cout<<plan_roller_coaster(v1,v2)<<endl;
}
*/

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