Submission #550429

#	Time	Username	Problem	Language	Result	Execution time	Memory
550429		elazarkoren	Boxes with souvenirs (IOI15_boxes)	C++17	0 / 100	2096 ms	304 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 1e6 + 5;
const ll infinity = 1e18;

ll dp[MAX_N];

ll Solve(vi &p, int l) {
    int n = p.size();
    ll ans = l;
    sort(all(p));
    for (int i = 0; i < n - 1; i++) {
        chkmin(ans, ll(2) * (p[i] + (l - p[i + 1])));
    }
    chkmin(ans, ll(2) * p[n - 1]);
    chkmin(ans, ll(2) * (l - p[0]));
    return ans;
}

long long delivery(int n, int k, int l, int p[]) {
    ll ans = infinity;
    sort(p, p + n);
    do {
        for (int i = 0; i < n; i++) {
            vi curr;
            dp[i] = infinity;
            for (int j = i; j; j--) {
                if (curr.size() > k) break;
                curr.push_back(p[j]);
                chkmin(dp[i], dp[j - 1] + Solve(curr, l));
            }
            curr.push_back(p[0]);
            if (curr.size() > k) continue;
            chkmin(dp[i], Solve(curr, l));
        }
        chkmin(ans, dp[n - 1]);
    } while (next_permutation(p,p + n));
    return ans;
}
//3 2 8
//1 2 5

Compilation message (stderr)

boxes.cpp: In function 'll Solve(vi&, int)':
boxes.cpp:21:19: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   21 |     int n = p.size();
      |             ~~~~~~^~
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:40:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |                 if (curr.size() > k) break;
      |                     ~~~~~~~~~~~~^~~
boxes.cpp:45:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |             if (curr.size() > k) continue;
      |                 ~~~~~~~~~~~~^~~

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