제출 #714059

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

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;

#define num long long

vector<num> dp;

struct SegTree {
    vector<num> tree;

    int size, start, height;

    SegTree (int _size) {
        size = _size;
        height = ceil(log2(size));
        start  = 1 << height;

        tree.resize(start << 1);
    }

    void update (int index) {
        if (index == 0) return ;

        if (index < start) {
            int n0 = index << 1;
            int n1 = n0 + 1;

            tree[index] = min(tree[n0], tree[n1]);
        }
        update(index >> 1);
    }
    void modify (int index, num value) {
        tree[index + start] = value;
        update(index + start);
    }
    num query (int l, int r) {
        num res = 1e18;

        l += start;
        r += start;

        while (l < r) {
            if ((l & 1) == 1) res = min(res, tree[l]);
            if ((r & 1) == 0) res = min(res, tree[r]);

            l = (l + 1) >> 1;
            r = (r - 1) >> 1;
        }

        if (l == r) res = min(res, tree[l]);
        return res;
    }
};

num valuation (int L, int P) {
    return min(P, L - P);
}

long long delivery(int N, int K, int L, int p[]) {
    sort(p, p + N);

    SegTree opt(N + 1);
    
    dp.resize(N + 1, 0);
    dp[0] = 0;
    opt.modify(0, valuation(L, p[0]) - p[0] + dp[0]);
    dp[1] = valuation(L, p[0]) * 2;
    opt.modify(1, valuation(L, p[1]) - p[1] + dp[1]);

    for (int i = 2; i <= N; i ++) {
        int pos = p[i - 1];
        num mov = valuation(L, pos) + pos;
        num mmv = opt.query(max(0, i - K), i - 1);

        dp[i] = mmv + mov;
        opt.modify(i, valuation(L, p[i]) - p[i] + dp[i]);
    }

    //for (int i = 0; i <= N; i ++)
    //    cout << dp[i] << " ";
    //cout << endl;

    return dp[N];
}

컴파일 시 표준 에러 (stderr) 메시지

boxes.cpp: In constructor 'SegTree::SegTree(int)':
boxes.cpp:16:22: warning: conversion from 'double' to 'int' may change value [-Wfloat-conversion]
   16 |         height = ceil(log2(size));
      |                  ~~~~^~~~~~~~~~~~

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