Submission #685133

#	Time	Username	Problem	Language	Result	Execution time	Memory
685133		APROHACK	Boxes with souvenirs (IOI15_boxes)	C++14	20 / 100	1 ms	340 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
ll n, k, l;
vector<int>teams;
ll distanciaABase(ll number){
    return min(number, l-number);
}
bool isLeft(int number){
    return number <= l/2;
}

ll dp[10000001][2];
ll calculateDp(){
    ll acum = 0, restantes = k, ant = 0;
    for(int i = 0 ;i < n ; i ++){
        restantes--;
        acum += (teams[i] - ant);
        dp[i][0] = acum + distanciaABase(teams[i]);
        ant = teams[i];
        if(!restantes){
            restantes = k;
            ant = 0;
            acum += distanciaABase(teams[i]);
        }

        //cout << i << " -> " << dp[i][0] << endl;
    }

    acum = 0, restantes = k, ant = l;
    for(int i = n-1 ;i >= 0 ; i --){
        restantes--;
        acum += (ant - teams[i]);
        dp[i][1] = acum + distanciaABase(teams[i]);
        ant = teams[i];
        if(!restantes){
            restantes = k;
            ant = l;
            acum += distanciaABase(teams[i]);
        }

        //cout << i << " -> " << dp[i][1] << endl;
    }

    ll best = dp[0][1];
    for(int i = 0 ;i  < n-1 ; i ++){
        best = min(best, dp[i][0] + dp[i+1][1]);
    }
    return min(best, dp[n-1][0]);

}

long long delivery(int N, int K, int L, int p[]) {
    n = N, k = K, l = L;
    for(int i = 0 ; i < n ; i ++){
        teams.pb(p[i]);
    }
    sort(teams.begin(), teams.end());
    return calculateDp();
}

Compilation message (stderr)

boxes.cpp: In function 'long long int calculateDp()':
boxes.cpp:35:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   35 |     for(int i = n-1 ;i >= 0 ; i --){
      |                 ~^~

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