Submission #140095

#	Time	Username	Problem	Language	Result	Execution time	Memory
140095		SirCeness	Boxes with souvenirs (IOI15_boxes)	C++14	50 / 100	83 ms	20224 KiB

boxes

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

#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define orta ((l+r)>>1)
#define INF 1000000009
#define mod 1000000007
#define ppair(x); cerr << "(" << x.first << ", " << x.second << ")\n";
#define bas(x) #x << ": " << x << " "
#define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n";
#define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n";
using namespace std;
typedef long long ll;

ll n, k, s;
vector<int> arr;

ll tekcoz(vector<ll>& ar){
	if (ar.size() == 0) return 0;
	if (ar[0] > ar.back()) reverse(ar.begin(), ar.end());
	int i = (int)ar.size()-1;
	ll ans = 0;
	while (i >= 0){
		ans += ar[i] + ar[i];
		i -= k;
	}
	return ans;
}

ll solve(){
	vector<ll> sol, sag;
	for (int i = 0; i < n; i++) if (arr[i] < s - arr[i]) sol.pb(arr[i]); else sag.pb(s - arr[i]);
	return tekcoz(sol) + tekcoz(sag);
}

ll solve2(){
	int l = 0;
	int r = k-1;
	while (r < n && arr[l] < s-arr[r]) l++, r++;
	if (r >= n) return s*s;
	vector<ll> sol, sag;
	for (int i = 0; i < l; i++) sol.pb(arr[i]);
	for (int i = n-1; i > r; i--) sag.pb(s-arr[i]);
	//cout << bas(l) << bas(r) << endl;
	//prarrv(sol);
	//prarrv(sag);
	ll ans1 = tekcoz(sol) + tekcoz(sag) + s;
	sol.clear();
	sag.clear();
	l++; r++;
	if (r >= n) return ans1;
	for (int i = 0; i < l; i++) sol.pb(arr[i]);
	for (int i = n-1; i > r; i--) sag.pb(s-arr[i]);
	//cout << bas(l) << bas(r) << endl;
	//prarrv(sol);
	//prarrv(sag);
	ll ans2 = tekcoz(sol) + tekcoz(sag) + s;
	//cout << "return: " << min(ans1, ans2) << endl;
	return min(ans1, ans2);
}

ll delivery(int N, int K, int L, int p[]) {
	n = N;
	k = K;
	s = L;
	for (int i = 0; i < n; i++) arr.pb(p[i]);
	//sort(arr.begin(), arr.end());
	
	
	ll ans = 0;
	int artik = n%k;
	int l = 0;
	int r = n-1;
	ll bas, son;
	if (artik){	
		bas = arr[l+artik-1];
		son = s - arr[r-artik+1];
		if (bas < son){
			ans = bas*2;
			l += artik;
		} else {
			ans = son*2;
			r -= artik;
		}
	}
	
	while (l <= r){
		bas = arr[l+k-1];
		son = s-arr[r-k+1];
		//cout << bas(bas) << bas(son) << endl;
		if (2*bas > s && 2*son > s){
			ans += s;
			l += k;
			continue;
		}
		if (bas < son) ans += bas*2, l += k;
		else ans += son*2, r -= k;
	}
	
	//cout << solve() << endl;
	
    return min(ans, min(solve(), solve2()));
}

Compilation message (stderr)

boxes.cpp: In function 'll tekcoz(std::vector<long long int>&)':
boxes.cpp:28:5: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   i -= k;
   ~~^~~~
boxes.cpp: In function 'll solve2()':
boxes.cpp:41:11: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  int r = k-1;
          ~^~
boxes.cpp:46:16: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  for (int i = n-1; i > r; i--) sag.pb(s-arr[i]);
               ~^~
boxes.cpp:56:16: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  for (int i = n-1; i > r; i--) sag.pb(s-arr[i]);
               ~^~
boxes.cpp: In function 'll delivery(int, int, int, int*)':
boxes.cpp:74:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  int artik = n%k;
              ~^~
boxes.cpp:76:11: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  int r = n-1;
          ~^~
boxes.cpp:96:6: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
    l += k;
    ~~^~~~
boxes.cpp:99:34: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   if (bas < son) ans += bas*2, l += k;
                                ~~^~~~
boxes.cpp:100:24: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   else ans += son*2, r -= k;
                      ~~^~~~

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