제출 #258361

#제출 시각아이디문제언어결과실행 시간메모리
258361Kubin휴가 (IOI14_holiday)C++17
7 / 100
5086 ms6904 KiB
#include <bits/stdc++.h> using namespace std; template<typename T, typename Cmp = less<T>> struct max_sum_set { Cmp cmp; vector<T> values; void insert(const T& x) { values.push_back(x); } T get(size_t k) { nth_element(values.begin(), values.begin() + k, values.end(), cmp); return accumulate(values.begin(), values.begin() + k, T(0)); } }; vector<int64_t> best_values(const vector<int>& A, size_t d, int mv = 1) { max_sum_set<int64_t, greater<int64_t>> val; vector<int64_t> result((mv+1)*A.size() + 1); for(size_t p = 1; p <= A.size(); p++) { val.insert(A[p - 1]); for(size_t q = 1; q <= p; q++) { result[mv*p + q] = max(result[mv*p + q], val.get(q)); } } result.resize(d + 1); for(size_t i = 1; i <= d; i++) result[i] = max(result[i], result[i-1]); return result; } int64_t solve_right(const vector<int>& A, size_t s, size_t d) { auto R = best_values(vector<int>(A.begin() + s, A.end()), d), L = best_values(vector<int>(A.rbegin() + (A.size()-s), A.rend()), d, 2); int64_t result = 0; for(size_t r = 0; r <= d; r++) result = max(result, R[r] + L[d-r]); return result; } long long int findMaxAttraction(int n, int start, int d, int a[]) { vector<int> A(a, a + n); int64_t result = solve_right(A, start, d+1); reverse(A.begin(), A.end()); result = max(result, solve_right(A, n-1 - start, d+1)); return result; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...