Submission #420184

#	Time	Username	Problem	Language	Result	Execution time	Memory
420184		dxz05	Boxes with souvenirs (IOI15_boxes)	C++14	10 / 100	3 ms	4556 KiB

boxes

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

typedef long long ll;

using namespace std;

const int MAXN = 1111111;

int dp[MAXN];

ll solve(vector<int> lf, vector<int> rg, int K, int L){
    memset(dp, 0, sizeof(dp));

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

    cost = 0, prizes = K;
    for (int i = 0; i < lf.size(); i++){
        if (prizes){
            prizes--;
            cost += lf[i] - (i > 0 ? lf[i - 1] : 0);
        } else {
            prizes = K - 1;
            cost += lf[i] + lf[i - 1];
        }
    }

    ll ans = 1e18;

    int RG = rg.size();

    if (lf.empty()) ans = dp[RG - 1]; else
        ans = cost + lf.back() + dp[RG - 1];

    if (prizes > 0 && !lf.empty()){
        if (prizes >= rg.size()){
            ans = min(ans, cost + L - lf.back());
        } else {
            ans = min(ans, cost + L - lf.back() + dp[RG - prizes]);
        }
    }

    //cout << ans << endl;

    return ans;
}

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;
        v.push_back(p[i]);
        if (p[i] <= L / 2) lf.push_back(p[i]); else
            rg.push_back(L - p[i]);
    }
    N = v.size();

    if (N == 0) return 0ll;

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

    return min(solve(lf, rg, K, L), solve(rg, lf, K, L));
}

Compilation message (stderr)

boxes.cpp: In function 'll solve(std::vector<int>, std::vector<int>, int, int)':
boxes.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 0; i < rg.size(); i++){
      |                     ~~^~~~~~~~~~~
boxes.cpp:20:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   20 |             dp[i] = cost;
      |                     ^~~~
boxes.cpp:24:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   24 |             dp[i] = cost;
      |                     ^~~~
boxes.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < lf.size(); i++){
      |                     ~~^~~~~~~~~~~
boxes.cpp:43:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   43 |     int RG = rg.size();
      |              ~~~~~~~^~
boxes.cpp:49:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         if (prizes >= rg.size()){
      |             ~~~~~~~^~~~~~~~~~~~
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:69:15: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   69 |     N = v.size();
      |         ~~~~~~^~

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