Submission #64937

#	Time	Username	Problem	Language	Result	Execution time	Memory
64937		mirbek01	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	513 ms	196160 KiB

boxes

#include "boxes.h"

# include <bits/stdc++.h>

using namespace std;

long long d1[10000005], d2[10000005];

long long delivery(int N, int K, int L, int p[]) {
      long long ans = 1e18;

      for(int i = 0; i < N; i ++){
            if(i < K){
                  d1[i] = p[i] + min(L - p[i], p[i]);
            } else {
                  d1[i] = (p[i] + min(L - p[i], p[i])) + d1[i - K];
            }
      }

      for(int i = N - 1, cn = 0; i >= 0; i --, cn ++){
            if(cn < K){
                  d2[i] = (L - p[i]) + min(L - p[i], p[i]);
            } else {
                  d2[i] = ((L - p[i]) + min(L - p[i], p[i])) + d2[i + K];
            }
      }

      for(int i = 0; i < N; i ++){
            ans = min(ans, d1[i] + d2[i + 1]);
      }

      long long res = 0;
      for(int j = 0; j < N; j += K){
            res += (L - p[j]) + min(p[j], L - p[j]);
      }
      ans = min(ans, res);

      return ans;
}

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