제출 #198462

#제출 시각아이디문제언어결과실행 시간메모리
198462QCFium휴가 (IOI14_holiday)C++14
47 / 100
476 ms7416 KiB
#include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } std::vector<int> a; int start, d; struct TopK { int k; std::multiset<int> upper; std::multiset<int> lower; int64_t upper_sum = 0; TopK (int k) : k(k) {} void low_to_up() { assert(lower.size()); auto greatest = std::prev(lower.end()); upper.insert(*greatest); upper_sum += *greatest; lower.erase(greatest); } void up_to_low() { assert(upper.size()); auto lowest = upper.begin(); upper_sum -= *lowest; lower.insert(*lowest); upper.erase(lowest); } void insert(int n) { if (!k) { lower.insert(n); return; } if ((int) upper.size() == k) { auto lowest = upper.begin(); if (*lowest < n) { lower.insert(*lowest); upper_sum -= *lowest; upper_sum += n; upper.erase(lowest); upper.insert(n); } else lower.insert(n); } else upper.insert(n), upper_sum += n; } void erase(int n) { if (upper.size() && *upper.begin() <= n) { upper_sum -= n; upper.erase(upper.find(n)); if (lower.size()) low_to_up(); } else lower.erase(lower.find(n)); } void set_k(int new_k) { for (; k < new_k; k++) { while (lower.size() && (int) upper.size() <= k) low_to_up(); } for (; k > new_k; k--) { while ((int) upper.size() >= k) up_to_low(); } k = new_k; } }; struct RangeSum { TopK topk; int l = 0; int r = 0; RangeSum () : topk(d) {} void set_lr(int new_l, int new_r) { new_r++; if (l == r) l = r = new_l; while (l > new_l) topk.insert(a[--l]); while (r < new_r) topk.insert(a[r++]); while (l < new_l) topk.erase(a[l++]); while (r > new_r) topk.erase(a[--r]); new_r--; int move; move = new_r - start; if (new_l < start) move += new_r - new_l; topk.set_k(std::max(0, d - move)); } int64_t sum() { return topk.upper_sum; } }; RangeSum sum; std::vector<int64_t> dp; // [], [] void monotone_minima(int rl, int rr, int ll, int lr) { int rm = rl + ((rr - rl) >> 1); int64_t max = -1; int maxindex = -1; for (int i = ll; i <= std::min(lr, rm); i++) { sum.set_lr(i, rm); int64_t cur = sum.sum(); if (max < cur) { max = cur; maxindex = i; } } assert(maxindex != -1); dp[rm] = max; if (rl < rm) monotone_minima(rl, rm - 1, ll, maxindex); if (rm < rr) monotone_minima(rm + 1, rr, maxindex, lr); } int64_t solve() { int n = a.size(); dp.assign(n, 0); monotone_minima(start, n - 1, 0, start); return *std::max_element(dp.begin(), dp.end()); } long long int findMaxAttraction(int n, int start_, int d_, int attraction[]) { a.resize(n); for (int i = 0; i < n; i++) a[i] = attraction[i]; start = start_; d = d_; int64_t res = solve(); start = n - 1 - start; std::reverse(a.begin(), a.end()); sum = RangeSum(); res = std::max(res, solve()); return res; } /* int main() { int n = ri(); int start = ri(); int d = ri(); int a[n]; for (auto &i : a) i = ri(); std::cout << findMaxAttraction(n, start, d, a) << std::endl; return 0; } //*/

컴파일 시 표준 에러 (stderr) 메시지

holiday.cpp: In function 'int ri()':
holiday.cpp:5:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...