제출 #793108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
793108		PixelCat	선물상자 (IOI15_boxes)	C++14	50 / 100	37 ms	8264 KiB

boxes

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include "boxes.h"

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 1000;
const int INF = 1'000'000'000'000'000'000;

int a[MAXN + 10];
int c[MAXN + 10];

int cost(int l, int r) {
    return a[r] - a[l] + c[l] + c[r];
}

long long delivery(int32_t N, int32_t K, int32_t L, int32_t pos[]) {
    For(i, 1, N) {
        a[i] = pos[i - 1];
        c[i] = min(a[i], L - a[i]);
    }
    int dp = 0;
    deque<pii> dq;  // {index, value}
    For(i, 1, N) {
        if(sz(dq) && dq.front().F <= i - K) dq.pop_front();
        int val = dp + c[i] - a[i];
        while(sz(dq) && dq.back().S > val) dq.pop_back();
        dq.eb(i, val);
        dp = a[i] + c[i] + dq.front().S;
        // For(j, 1, K) if(i >= j) {
        //     dp[i] = min(dp[i], dp[i - j] + cost(i - j + 1, i));
        // }
    }
    return dp;
}

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