제출 #238988

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

boxes

#include "boxes.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
using namespace std;

//#define RDEBUG 1
#ifdef RDEBUG
#define D(x) x
#else
#define D(x)
#endif
#define inf 0x7fffffff
#define MOD 1000000007

typedef long long ll;


ll add(ll a, ll b) {
    a += b;
    if(a >= MOD) {
        a -= MOD;
    }
    return a;
}
ll sub(ll a, ll b) {
    a -= b;
    if(a < 0) {
        a += MOD;
    }
    return a;
}

ll mul(ll a, ll b) {
    return (a * b)%MOD;
}

void add_self(ll& a, ll b) {
    a = add(a, b);
}
void sub_self(ll& a, ll b) {
    a = sub(a, b);
}
void mul_self(ll& a, ll b) {
    a = mul(a, b);
}


const ll MAXN = 10000010;

ll li[MAXN], ri[MAXN];

long long delivery(int N, int K, int L, int p[]) {
//    ios_base :: sync_with_stdio(false);
//    cin.tie(nullptr);
//    cin >> N >> K >> L;
//    for (ll i = 0; i<N; i++) {
//        cin >> p[i];
//    }
    for (ll i = 0; i<N; i++) {
        li[i+1] = p[i]-(i-K < 0 ? 0 : p[i-K])+li[max(i-K+1, 0ll)]+(i-K >= 0 ? 2*p[i-K] : 0);
    }
    ll curr = 0;
    for (ll i = N-1; i>=0; i--) {
        curr++;
        ri[curr] = (i+K > N-1 ? L : p[i+K])-p[i]+ri[max(curr-K, 0ll)]+2*(L-(i+K<N ? p[i+K] : L));
    }
    ll best = 1e13;
    for (ll i = 0; i<=N; i++) {
        ll numr = N-i;
        best = min(best, li[i]+ri[N-i]+(i != 0 ? p[i-1] : 0)+(i != N ? L-p[N-numr] : 0));
    }
    for (ll i = 0; i<=N-K; i++) {
        ll numr = N-i-K;
        best = min(best, li[i]+L+ri[N-i-K]+(i!=0 ? p[i-1] : 0)+(i != N-K ? L-p[N-numr] : 0));
    }
    return best;
}

//ll N, K, L, p[MAXN];
//
//int main() {
//    ios_base :: sync_with_stdio(false);
//    cin.tie(nullptr);
//    cin >> N >> K >> L;
//    for (ll i = 0; i<N; i++) {
//        cin >> p[i];
//    }
//    for (ll i = 0; i<N; i++) {
//        li[i+1] = p[i]-(i-K < 0 ? 0 : p[i-K])+li[max(i-K+1, 0ll)]+(i-K >= 0 ? 2*p[i-K] : 0);
//    }
//    ll curr = 0;
//    for (ll i = N-1; i>=0; i--) {
//        curr++;
//        ri[curr] = (i+K > N-1 ? L : p[i+K])-p[i]+ri[max(curr-K, 0ll)]+2*(L-(i+K<N ? p[i+K] : L));
//    }
//    ll best = 1e13;
//    for (ll i = 0; i<=N; i++) {
//        best = min(best, li[i]+ri[N-i]+(i != 0 ? p[i-1] : 0)+(i != N ? L-p[N-i-1] : 0));
//    }
//    for (ll i = 0; i<=N-K; i++) {
//        best = min(best, li[i]+L+ri[N-i-K]+(i!=0 ? p[i-1] : 0)+(i != N-K ? L-p[N-i-K-1] : 0));
//    }
//    cout << best << "\n";
//    return 0;
//}
//

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