제출 #604270

#제출 시각아이디문제언어결과실행 시간메모리
604270cheissmart선물상자 (IOI15_boxes)C++14
10 / 100
1 ms468 KiB
#include "boxes.h" #include <bits/stdc++.h> #define F first #define S second #define V vector #define PB push_back #define EB emplace_back #define MP make_pair #define SZ(v) int((v).size()) #define ALL(v) (v).begin(), (v).end() using namespace std; typedef long long ll; typedef pair<int, int> pi; typedef V<int> vi; const int INF = 1e9 + 7; const ll oo = 1e18; ll delivery(int n, int k, int l, int p[]) { vi a; for(int i = 0; i < n; i++) if(p[i]) a.PB(p[i]); n = SZ(a); vi x, y; for(int i = 0; i < n; i++) { if(a[i] < l - a[i]) { x.PB(a[i]); } else if(l - a[i] < a[i]) { y.PB(l - a[i]); } } auto go = [&] (vi tt) { sort(ALL(tt)); V<ll> dp(SZ(tt) + 1); for(int i = 0; i < SZ(tt); i++) { dp[i + 1] = dp[max(0, i + 1 - k)] + tt[i] * 2; } V<ll> diff; for(int i = 0; i < SZ(tt); i++) diff.PB(dp[i + 1] - dp[i]); assert(is_sorted(ALL(diff))); return diff; }; V<ll> dx = go(x), dy = go(y), aux(SZ(dx) + SZ(dy)); merge(ALL(dx), ALL(dy), aux.begin()); ll ans = 1LL * (n + k - 1) / k * l, sum = 0; for(int i = 0; i < SZ(aux); i++) { sum += aux[i]; ans = min(ans, sum + 1LL * (n - i - 1 + k - 1) / k * l); } cerr << ans << endl; return ans; }
#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...