Submission #441861

#	Time	Username	Problem	Language	Result	Execution time	Memory
441861		NintsiChkhaidze	선물상자 (IOI15_boxes)	C++14	100 / 100	508 ms	196980 KiB

boxes

#include "boxes.h"
#include <iostream>
#define ll long long
using namespace std;
const int N = 10000005;
ll dp[4][N];
ll delivery(int n, int k, int l, int p[]) {
  //dp[1][i] = pirveli i cali avige cw mimartulebit
  //dp[2][i] = bolodan is chatvlit avige ccw mimartulebit

   for (int i = 0; i < n; i++){
     if (i < k) dp[1][i] = p[i]*2;
     else dp[1][i] = dp[1][i - k] + min(p[i]*2,l);
   }
    
   for (int i = n - 1; i >= 0; i--){
     if (i + k - 1 > n - 1) dp[2][i] = (l - p[i])*2;
     else dp[2][i] = dp[2][i + k] + min(l,(l - p[i])*2); 
   }

   ll ans = 1e18;
   for (int i = 0; i < n; i++){
     ans = min(ans,dp[1][i] + dp[2][i + 1]);
   }
   ans = min(ans,dp[1][n - 1]);
   ans = min(ans,dp[2][0]);
   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