Submission #1264189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264189		vtnoo	Roller Coaster Railroad (IOI16_railroad)	C++20	0 / 100	26 ms	3400 KiB

railroad

#include <bits/stdc++.h>

using namespace std;

const int MAXN=16, INF=1e9;
pair<long long, int> dp[1<<MAXN];

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t){
    int n=s.size();
    /* for(int i=0;i<n;i++)cout<<s[i]<<" ";
    cout<<endl;
    for(int i=0;i<n;i++)cout<<t[i]<<" ";
    cout<<endl; */
    dp[0]={0,1}; //metros, velocidad
    for(int S=1;S<(1<<n);S++){
        dp[S]={1e18, 1e9};
        for(int i=n-1;i>=0;i--){
            if(((1<<i)&S)){
                int prevS=S^(1<<i);
                long long need=0;
                if(dp[prevS].second>s[i]){
                    need=dp[prevS].second-s[i];
                }
                /* cout<<"=================="<<endl;
                cout<<t[i]<<endl; */
                dp[S]=min(dp[S],{dp[prevS].first+need,t[i]});
                /* cout<<need<<endl;
                cout<<S<<endl;
                cout<<dp[S].first<<" "<<dp[S].second<<endl; */
            }
        }
    }
    //cout<<dp[(1<<n)-1].second<<endl;
    return dp[(1<<n)-1].first;
}

Compilation message (stderr)

railroad.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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