제출 #707667

#제출 시각아이디문제언어결과실행 시간메모리
707667SamNguyen선물상자 (IOI15_boxes)C++14
100 / 100
769 ms259480 KiB
#include "boxes.h" #include <bits/stdc++.h> using namespace std; const long long INF = 1e18; template <class T1, class T2> inline bool minimise(T1 &x, T2 y) { if (x > y) { x = y; return true; } return false; } long long delivery(int N, int K, int L, int pos[]) { vector<int> lefts, rights; for (int i = 0; i < N; i++) { if (2 * pos[i] < L) lefts.push_back(pos[i]); else rights.push_back(L - pos[i]); } sort(lefts.begin(), lefts.end(), greater<int>()); sort(rights.begin(), rights.end(), greater<int>()); /* cerr << "K = " << K << endl; cerr << "lefts = "; for (int e : lefts) cerr << e << " "; cerr << endl; cerr << "rights = "; for (int e : rights) cerr << e << " "; cerr << endl; */ vector<long long> sum_lefts(lefts.size()), sum_rights(rights.size()); for (int i = int(lefts.size() - 1); i >= 0; i--) { sum_lefts[i] = lefts[i]; if (i + K < int(lefts.size())) sum_lefts[i] += sum_lefts[i + K]; } for (int i = int(rights.size() - 1); i >= 0; i--) { sum_rights[i] = rights[i]; if (i + K < int(rights.size())) sum_rights[i] += sum_rights[i + K]; } sum_lefts.push_back(0); sum_rights.push_back(0); /* cerr << "sum_lefts = "; for (int e : sum_lefts) cerr << e << " "; cerr << endl; cerr << "sum_rights = "; for (int e : sum_rights) cerr << e << " "; cerr << endl; */ long long ans = 2 * (sum_lefts.front() + sum_rights.front()); for (int i = 0; i <= K; i++) { long long cur = 1LL * L; //cerr << "i = " << i; //cerr << " => cur = " << cur; if (i < int(lefts.size())) cur += 2 * sum_lefts[i]; if (K - i < int(rights.size())) cur += 2 * sum_rights[K - i]; //cerr << " => cur = " << cur << endl; minimise(ans, cur); } cerr << "return ans = " << 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...