Submission #1011715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011715		pawned	선물상자 (IOI15_boxes)	C++17	10 / 100	1 ms	432 KiB

boxes

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

ll delivery(int n, int kg, int lg, int p[]) {
	ll N = n; ll K = kg; ll L = lg;
	// length is L, have N teams, distribute K at a time
	ll cut = L / 2;
	vi leftv;	// [0, cut]
	vi rightv;	// [cut + 1, L - 1];
	sort(p, p + N);
	for (int i = 0; i < N; i++) {
		if (p[i] <= cut)
			leftv.pb(p[i]);
		else
			rightv.pb(L - p[i]);
	}
	sort(leftv.begin(), leftv.end());
	sort(rightv.begin(), rightv.end());
/*	cout<<"leftv: ";
	for (ll x : leftv)
		cout<<x<<" ";
	cout<<endl;
	cout<<"rightv: ";
	for (ll x : rightv)
		cout<<x<<" ";
	cout<<endl;*/
	int X = (int)(leftv.size());
	int Y = (int)(rightv.size());
	vi pfs1(X, 0);	// sum of all alternating by K
	vi pfs2(Y, 0);
	for (int i = 0; i < X; i++) {
		if (i < K)
			pfs1[i] = leftv[i];
		else
			pfs1[i] = pfs1[i - K] + leftv[i];
	}
	for (int i = 0; i < Y; i++) {
		if (i < K)
			pfs2[i] = rightv[i];
		else
			pfs2[i] = pfs2[i - K] + rightv[i];
	}
	ll mincost = 1e18;
	ll cost = 0;
	for (int i = X - 1; i >= 0; i -= K) {
		cost += leftv[i] * 2;
	}
	for (int i = Y - 1; i >= 0; i -= K) {
		cost += rightv[i] * 2;
	}
	mincost = cost;
	for (int i = 1; i < K; i++) {	// count remove in left
		if (X < i || Y < (K - i))
			continue;
		cost = L + 2 * (pfs1[X - i - 1] + pfs2[Y - (K - i) - 1]);
		mincost = min(mincost, cost);
	}
	return mincost;
}

Compilation message (stderr)

boxes.cpp: In function 'll delivery(int, int, int, int*)':
boxes.cpp:54:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   54 |  for (int i = X - 1; i >= 0; i -= K) {
      |                              ~~^~~~
boxes.cpp:57:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   57 |  for (int i = Y - 1; i >= 0; i -= K) {
      |                              ~~^~~~

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