제출 #258399

#제출 시각아이디문제언어결과실행 시간메모리
258399Kubin휴가 (IOI14_holiday)C++17
0 / 100
892 ms9088 KiB
#include <bits/stdc++.h> using namespace std; template<typename T> struct fenwick_tree { size_t n; vector<T> F; static constexpr size_t lsb(size_t x) { return x & -x; } fenwick_tree(size_t m) : n(m), F(n+1) {} T get_prefix(size_t p) const { T r = 0; while(p) r += F[p], p -= lsb(p); return r; } void delta(size_t p, T v) { p++; while(p <= n) F[p] += v, p += lsb(p); } size_t lower_bound(T v) { if(v == 0) return 0; size_t p = 0; T s = 0; for(size_t k = __lg(n) + 1; k --> 0; ) if(p + (1 << k) <= n and s + F[p + (1 << k)] < v) s += F[p += (1 << k)]; return p + 1; } }; struct max_sum_set { vector<int> A; vector<size_t> B; fenwick_tree<int> cnt; fenwick_tree<int64_t> sum; max_sum_set(vector<int> a) : A(a), B(A.size()), cnt(A.size()), sum(A.size()) { iota(B.begin(), B.end(), 0); sort(B.begin(), B.end(), [&](size_t lhs, size_t rhs) { return A[lhs] > A[rhs]; }); } void push(size_t i) { if(i >= A.size()) return; cnt.delta(B[i], +1); sum.delta(B[i], +A[i]); } void pop(size_t i) { if(i >= A.size()) return; cnt.delta(B[i], -1); sum.delta(B[i], -A[i]); } int64_t get(size_t k) { return sum.get_prefix(cnt.lower_bound(min(k, (size_t)cnt.get_prefix(A.size())))); } }; void divida_et_impera( size_t d1, size_t d2, size_t p1, size_t p2, vector<int64_t>& result, max_sum_set& V, const vector<int>& A, int mv) { if(d1 >= d2) return; size_t d = (d1 + d2) / 2, p = p1; int64_t& r = result[d]; for(size_t i = p1; i < p2 and mv*i <= d; i++) { auto v = V.get(d-mv*i); if(v > r) r = v, p = i; V.push(i); } for(size_t i = p1; i < p2 and mv*i <= d; i++) V.pop(i); divida_et_impera(d1, d, p1, p+1, result, V, A, mv); for(size_t i = p1; i < p; i++) V.push(i); divida_et_impera(d+1, d2, p, p2, result, V, A, mv); for(size_t i = p1; i < p; i++) V.pop(i); } vector<int64_t> best_values(vector<int> A, size_t d, int mv = 1) { vector<int64_t> result(d+1); max_sum_set V(A); divida_et_impera(0, d+1, 0, A.size()+1, result, V, A, mv); 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...