Submission #693944

#	Time	Username	Problem	Language	Result	Execution time	Memory
693944		T0p_	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	593 ms	293628 KiB

boxes

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

const int N = 10000000;

long long cw[N+5], ccw[N+5];

long long cost(int a, int b, int L)
{
    if (a > b) swap(a, b);
    return min(b-a, L-b+a);
}

long long delivery(int N, int K, int L, int p[])
{
    for (int i=0 ; i<K ; i++) cw[i] = p[i];
    for (int i=K ; i<N ; i++) cw[i] = cw[i-K] + p[i] + p[i-K]; 
 
    for (int i=0 ; i<K ; i++) ccw[N-i-1] = L - p[N-i-1];
    for (int i=K ; i<N ; i++) ccw[N-i-1] = ccw[N-i+K-1] + L - p[N-i+K-1] + L - p[N-i-1];
 
    long long ans = 1e18;
    for (int i=0 ; i<=N ; i++)
    {
        if (i == 0) ans = min(ans, ccw[0] + cost(p[0], 0, L));
        else if (i == N) ans = min(ans, cw[N-1] + cost(p[N-1], 0, L));
        else ans = min(ans, cw[i-1] + cost(p[i-1], 0, L) + ccw[i] + cost(p[i], 0, L));
    }

    return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:15:24: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   15 | long long delivery(int N, int K, int L, int p[])
      |                    ~~~~^
boxes.cpp:5:11: note: shadowed declaration is here
    5 | const int N = 10000000;
      |           ^

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