Submission #396953

#TimeUsernameProblemLanguageResultExecution timeMemory
396953Andyvanh1Boxes with souvenirs (IOI15_boxes)C++14
50 / 100
2073 ms21596 KiB
#include <iostream> #include <algorithm> #include <vector> #include <set> #include <stack> #include <queue> #include <map> #include <math.h> using namespace std; #define pb push_back #define INF INT32_MAX #define vt vector typedef vt<int> vi; typedef pair<int,int> pii; typedef tuple<int,int,int> tiii; typedef long long ll; #define MOD 1000000007 ll delivery(int n, int k, int l, int arr[]){ if(k==1){ ll ans = 0; for(int i = 0; i < n; i++){ ans+=2*min(arr[i],l-arr[i]); } return ans; }else if(k==n){ if(arr[n-1]<=l/2){ return arr[n-1]*2; }else if(arr[0]>l/2){ return 2* (l-arr[0]); }else{ int Max1 = 0; int Max2 = 0; int i = 0; for(; i < n; i++){ if(arr[i]<=l/2){ Max1 = max(Max1, arr[i]); }else{ break; } } Max2 = arr[i]; return min(l,2*(Max1+l-Max2)); } }else{ vt<ll> dp(n+1); dp[0] = 0; for(int i = 1; i <= n; i++){ dp[i] =INT64_MAX; for(int j = i-1; j >= i-k&&j>=0; j--){ dp[i] = min(dp[i], dp[j] + min(min(2 * (l - arr[j]), 2 * arr[i - 1]), l)); } } return dp[n]; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...