Submission #782601

#	Time	Username	Problem	Language	Result	Execution time	Memory
782601		ymm	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	727 ms	196412 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
using namespace std;

vector<ll> al, dpl, ar, dpr;

long long delivery(int N, int K, int L, int p[]) {
	Loop (i,0,N) {
		if (p[i] > L-p[i])
			ar.push_back(L-p[i]);
		else
			al.push_back(p[i]);
	}
	sort(al.begin(), al.end());
	sort(ar.begin(), ar.end());
	Loop (dard,0,2) {
		auto &a = dard? ar: al;
		auto &dp = dard? dpr: dpl;
		dp.resize(a.size()+1);
		dp[0] = 0;
		Loop (i,0,a.size())
			dp[i+1] = i < K? 2*a[i]: 2*a[i] + dp[i+1-K];
	}
	ll ans = dpl.back() + dpr.back();
	Loop (i,0,K) {
		int x = (int)al.size()-i;
		int y = (int)ar.size()-K+i;
		if (x < 0 || y < 0)
			continue;
		ans = min(ans, dpl[x] + dpr[y] + L);
	}
	return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
boxes.cpp:23:3: note: in expansion of macro 'Loop'
   23 |   Loop (i,0,a.size())
      |   ^~~~
boxes.cpp:28:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   28 |   int x = (int)al.size()-i;
      |           ~~~~~~~~~~~~~~^~
boxes.cpp:29:27: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   29 |   int y = (int)ar.size()-K+i;
      |           ~~~~~~~~~~~~~~~~^~

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