제출 #100028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
100028		ShaneOng	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	97 ms	27356 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define INF 10000000000000009ll
using namespace std;
typedef long long ll;
int n;
ll memo[17][(1<<16)+10];
vector<int> a,b;
ll dp(int i, int bitmask){
    if(bitmask==(1<<n)-1){
        //printf("test\n");
        return memo[i][bitmask]=0ll;
    }
    if(memo[i][bitmask]!=-1ll){
        return memo[i][bitmask];
    }
    //printf("%d %d\n",i,bitmask);
    memo[i][bitmask]=INF;
    for(int x=0;x<n;x++){
        if(!((1<<x)&bitmask)){
            memo[i][bitmask]=min(memo[i][bitmask],dp(x,bitmask|(1<<x))+max(0ll,(ll)b[i]-a[x]));

        }
    }
    return memo[i][bitmask];
}
long long plan_roller_coaster(vector<int> s, vector<int> t) {
    n = (int) s.size();
    //printf("%d\n",n);
    a=s,b=t;
    for(int x=0;x<n;x++){
        for(int y=0;y<=(1<<n);y++)
            memo[x][y]=-1ll;
    }

    return dp(0,1);
}

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