Submission #1020657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020657		vjudge1	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	65 ms	10828 KiB

railroad

#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define popcnt __builtin_popcount

pii a[200100];
ll dp[100100][17];


bool cmp(int a, int b){
    return popcnt(a) < popcnt(b);
}

long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = s.size();
    vector<int> q;
    for(int i=1; i<(1 << n); i++){
        q.pb(i);
        for(int j=0; j<n; j++) dp[i][j] = 1e18;
    }
    sort(q.begin(), q.end(), cmp);
    for(int i=0; i<n; i++){
        dp[(1 << i)][i] = 0;
    }
    for(int k: q){
        vector<int> l, r;
        for(int i=0; i<n; i++){
            if((k & (1 << i))) l.pb(i);
            else r.pb(i);
        }
        for(int x: l){
            for(int y: r){
                dp[k + (1 << y)][y] = min(dp[k + (1 << y)][y], dp[k][x] + max(t[x] - s[y], 0));
            }
        }
    }
    ll ans = 1e18;
    for(int i=0; i<n; i++){
        ans = min(ans, dp[(1 << n) - 1][i]);
    }
    return ans;

        


    
}

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