제출 #412692

#제출 시각아이디문제언어결과실행 시간메모리
412692losmi247선물상자 (IOI15_boxes)C++14
100 / 100
619 ms333012 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e7+2; int n,k,l; int pos[N]; ll kje1(){ ll sol = 0; for(int i = 0; i < n; i++){ ll dod = 2*min(pos[i],(int)l-pos[i]); sol += dod; } return sol; } ll kjen(){ int sol = l; sol = min(sol,2*(l-pos[0])); for(int i = 0; i < n-1; i++){ int sta = 2*pos[i]+2*(l-pos[i+1]); sol = min(sol,sta); } sol = min(sol,2*pos[n-1]); return sol; } ll inace(){ ll sol1 = 0; int a = l/2, b = (l+1)/2; for(int i = 0; i < n; i += k){ int kraj = min(i+k-1,n-1); /// sad gledas range pos-ova od i do kraj if(pos[kraj] <= a) sol1 += (ll)2*pos[kraj]; else if(pos[i] >= b) sol1 += (ll)2*(l-pos[i]); else sol1 += l; } ll sol2 = 0; a = l/2, b = (l+1)/2; for(int i = n-1; i >= 0; i -= k){ int poc = max(0,i-k+1); /// sad gledas range pos-ova od poc do i if(pos[i] <= a) sol2 += (ll)2*pos[i]; else if(pos[poc] >= b) sol2 += (ll)2*(l-pos[poc]); else sol2 += l; } return min(sol1,sol2); } ll dp1[N],dp2[N]; ll nesto(){ int a = l/2,b = (l+1)/2; for(int i = 0; i < n; i++){ //if(pos[i] > a) break; dp1[i] = 1e18; int sta = min(k,i+1); dp1[i] = min(dp1[i],2*pos[i]+dp1[i-sta]); /*for(int j = 1; j <= k && j <= i+1; j++){ dp1[i] = min(dp1[i],2*pos[i]+dp1[i-j]); }*/ } for(int i = n-1; i >= 0; i--){ //if(pos[i] < b) break; dp2[i] = 1e18; int sta = min(k,n-i); dp2[i] = min(dp2[i],2*(l-pos[i])+dp2[i+sta]); /*for(int j = 1; j <= k && j <= n-i; j++){ dp2[i] = min(dp2[i],2*(l-pos[i])+dp2[i+j]); }*/ } ll sol1 = dp2[0]; for(int i = 0; i < n; i++) sol1 = min(sol1,dp1[i]+dp2[i+1]); ll sol2 = 1e18; for(int i = 0; i < n; i++){ int kraj = min(n-1,i+k-1); if(pos[i] <= a && pos[kraj] >= b){ ll sta = l; if(i > 0) sta += dp1[i-1]; if(kraj < n-1) sta += dp2[kraj+1]; sol2 = min(sta,sol2); } } return min(sol1,sol2); } ll delivery(int br1,int br2,int br3,int *positions){ n = br1; k = br2; l = br3; for(int i = 0; i < n; i++) pos[i] = positions[i]; int sta = 0; while(sta < n && pos[sta] == 0) sta++; if(sta == n) return 0; for(int i = 0; i < n-sta; i++) pos[i] = pos[i+sta]; n -= sta; if(k == 1) return kje1(); if(k >= n) return kjen(); return nesto(); }
#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...