제출 #420231

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420231		dxz05	Boxes with souvenirs (IOI15_boxes)	C++14	20 / 100	1 ms	332 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int MAXN = 1111111;

void build(vector<int> &v, int K, vector<ll> &dp){
    ll cost = 0, prizes = K;
    for (int i = 0; i < v.size(); i++){
        if (prizes){
            prizes--;
            cost += v[i] - (i > 0 ? v[i - 1] : 0);
            dp[i] = cost;
        } else {
            prizes = K - 1;
            cost += v[i - 1] + v[i];
            dp[i] = cost;
        }
        dp[i] += v[i];
       // cout << dp[i] << ' ';
    }
}

long long delivery(int N, int K, int L, int p[]) {
    vector<int> v, lf, rg;
    for (int i = 0; i < N; i++){
        if (p[i] == 0) continue;
        lf.push_back(p[i]);
        rg.push_back(L - p[i]);
    }

    N = lf.size();
    if (N == 0) return 0ll;

    reverse(rg.begin(), rg.end());

    vector<ll> dp1(N), dp2(N);

    build(lf, K, dp1);
    build(rg, K, dp2);

    ll ans = min(dp1[N - 1], dp2[N - 1]);

    for (int i = 0; i < N - 1; i++){
        ans = min(ans, dp1[i] + dp2[N - i - 2]);

        if ((i + 1) % K != 0){
            int x = i + K - (i + 1) % K;

            ll cur = dp1[i] + L - 2 * lf[i];
            if (N - x - 2 >= 0) cur += dp2[N - x - 2];
            ans = min(ans, cur);

            cur = dp2[i] + L - 2 * rg[i];
            if (N - x - 2 >= 0) cur += dp1[N - x - 2];
            ans = min(ans, cur);
        }

    }

    return ans;
}

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

boxes.cpp: In function 'void build(std::vector<int>&, int, std::vector<long long int>&)':
boxes.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int i = 0; i < v.size(); i++){
      |                     ~~^~~~~~~~~~
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:35:16: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   35 |     N = lf.size();
      |         ~~~~~~~^~

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