제출 #578560

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
578560		jasmin	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	92 ms	13884 KiB

railroad

#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
#define int long long

const int inf=1e18;

int find_dp(int mask, int x, vector<vector<int> >& dp, vector<int32_t>& s, vector<int32_t>& t, int n){
    /*for(int i=0; i<n; i++){
        cout << (mask>>i)%2;
    }
    cout << " " << x << " =>" << dp[mask][x] << "\n" << flush;*/
    if(dp[mask][x]!=inf) return dp[mask][x];

    for(int i=0; i<n; i++){
        if(i==x || (mask>>i)%2!=1) continue;
        dp[mask][x]=min(dp[mask][x], find_dp(mask-(1<<x), i, dp, s, t, n)+max(0, t[x]-s[i]));
    }
    return dp[mask][x];
}

int plan_roller_coaster(vector<int32_t> s, vector<int32_t> t){
    int n=s.size();
    int pow2=(1<<n);

    vector<vector<int> > dp(pow2, vector<int> (n, inf));
    for(int i=0; i<n; i++){
        dp[(1<<i)][i]=0;
    }
    int ans=inf;
    for(int i=0; i<n; i++){
        ans=min(ans, find_dp(pow2-1, i, dp, s, t, n));
    }
    return ans;
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int32_t> s(n);
    vector<int32_t> t(n);
    for(int i=0; i<n; i++){
        cin >> s[i];
    }
    for(int i=0; i<n; i++){
        cin >> t[i];
    }
    cout << plan_roller_coaster(s, t) << "\n";
}*/

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