Submission #772925

#TimeUsernameProblemLanguageResultExecution timeMemory
772925phoebeHoliday (IOI14_holiday)C++17
30 / 100
84 ms5764 KiB
#include <bits/stdc++.h> #include "holiday.h" using namespace std; #define ll long long #define pii pair<int, int> #define F first #define S second #define FOR(i, n) for (int i = 0; i < n; i++) const int INF = 1e9 + 7; const int maxn = 1e5 + 10; int n, s, d, a[maxn]; int calc_dist(int l, int r){ if (l >= s) return r - s; if (r <= s) return s - l; return r - l + min(r - s, s - l); } ll solve(){ // cout << "kore wa beginning" << endl; // cout << n << ' ' << ' ' << s << ' ' << d << endl; set<pii> include, removed; ll best = 0, include_sum = 0; for (int i = 0; i < s; i++){ removed.insert({a[i], i}); } int l = 0; for (int r = s; r < min(s + d, n); r++){ // cout << l << ' ' << r << endl; removed.insert({a[r], r}); while (calc_dist(l, r) > d){ if (include.count({a[l], l})){ include.erase({a[l], l}); include_sum -= a[l]; } else removed.erase({a[l], l}); l++; } // rebalance while (include.size() > 0 && removed.size() > 0 && include.begin()->F < removed.rbegin()->F){ pii x = *include.begin(), y = *removed.rbegin(); include_sum -= x.F; include.erase(x); removed.erase(y); include_sum += y.F; include.insert(y); removed.insert(x); } // adding elements if we can int can_include = d - calc_dist(l, r); while (include.size() < can_include && removed.size() > 0){ pii x = *removed.rbegin(); removed.erase(x); include_sum += x.F; include.insert(x); } // removing elements if we must while (include.size() > can_include){ pii x = *include.begin(); include.erase(x); include_sum -= x.F; removed.insert(x); } while (l <= r){ int can_include = d - calc_dist(l, r); int can_include_prime = d - calc_dist(l + 1, r); ll delta = 0; if (include.count({a[l], l})){ delta -= a[l]; can_include_prime++; } else{ removed.erase({a[l], l}); } auto it = removed.rbegin(); vector<pii> to_remove; FOR(_, min((int)removed.size(), can_include_prime - can_include)){ to_remove.push_back(*it); delta += it->F; it++; } if (delta < 0){ if (include.count({a[l], l}) == 0){ removed.insert({a[l], l}); } break; } if (include.count({a[l], l})){ include.erase({a[l], l}); } for (auto x : to_remove){ removed.erase(x); include.insert(x); } include_sum += delta; l++; } best = max(best, include_sum); } return best; } ll findMaxAttraction(int N, int start, int D, int attraction[]){ n = N, s = start, d = D; for (int i = 0; i < n; i++) a[i] = attraction[i]; ll re = solve(); reverse(a, a + n); s = n - 1 - start; re = max(re, solve()); return re; }

Compilation message (stderr)

holiday.cpp: In function 'long long int solve()':
holiday.cpp:51:31: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |         while (include.size() < can_include && removed.size() > 0){
      |                ~~~~~~~~~~~~~~~^~~~~~~~~~~~~
holiday.cpp:56:31: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |         while (include.size() > can_include){
      |                ~~~~~~~~~~~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...