Submission #582798

#	Time	Username	Problem	Language	Result	Execution time	Memory
582798		MohamedFaresNebili	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	614 ms	293344 KiB

boxes

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using pi = pair<ll, pair<ll, ll>>;
        using ii = pair<int, int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        ll lf[10000001], rf[10000001];

        ll delivery(int N, int K, int L, int P[]) {
            ll res = 1e18;
            for(int l = 1; l <= N; l++) {
                if(l >= K) lf[l] += lf[l - K];
                ll A = P[l - 1] + min(L - P[l - 1], P[l - 1]);
                lf[l] += min(ll(L), A);
            }
            for(int l = N; l >= 1; l--) {
                int i = N - l + 1;
                if(i >= K) rf[l] += rf[l + K];
                ll A = L - P[l - 1] + min(L - P[l - 1], P[l - 1]);
                rf[l] += min(ll(L), A);
            }
            for(int l = 0; l <= N; l++)
                res = min(res, lf[l] + rf[l + 1]);
            return res;
        }

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