제출 #409129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
409129		pliam	선물상자 (IOI15_boxes)	C++14	100 / 100	577 ms	134264 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 10000005
typedef long long ll;

ll pos[MAXN];
deque<pair<int,ll>> min_q;
int n,k;
ll l;
ll ans;

ll min_(){
    return min_q.front().second;
}

void insert_q(pair<int,ll> p){
    while(!min_q.empty()&&p.second<min_q.back().second) min_q.pop_back();
    min_q.push_back(p);
}

void erase_q(int x){
    if(!min_q.empty()&&min_q.front().first==x) min_q.pop_front();
}

ll dist(ll x){
    return min(x,l-x);
}

ll c(int i){
    return dist(pos[i])+pos[i];
}

ll d(int i){
    return dist(pos[i+1])-pos[i+1];
}

long long delivery(int N, int K, int L, int positions[]) {
    n=N;
    k=K;
    l=L;
    if(N==1){
        return 2*dist(positions[0]);
    }
    for(int i=1;i<=n;i++){
        pos[i]=positions[i-1];
    }
    insert_q({0,d(0)});//base case
    for(int i=1;i<=n;i++){
        erase_q(i-k-1);
        ans=min_()+c(i);
        if(i!=n) insert_q({i,min_()+c(i)+d(i)});
    }
    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30