Submission #1171968

#TimeUsernameProblemLanguageResultExecution timeMemory
1171968JahonaliXHacker (BOI15_hac)C++20
100 / 100
229 ms39496 KiB
#include <bits/extc++.h> using namespace std; #define int long long #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define mod 1000000007 #define INF LONG_LONG_MAX #define cmin(a, b) a = min(a, b) #define cmax(a, b) a = max(a, b) template<typename T> using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>; template<typename T> using matrix = vector<vector<T>>; namespace io { template<typename T, typename F> istream &operator>>(istream &cin, pair<T, F> &p) { cin >> p.first >> p.second; return cin; } template<typename T, typename F> ostream &operator<<(ostream &cout, pair<T, F> &p) { cout << p.first << ' ' << p.second << '\n'; return cout; } template<typename T> istream &operator>>(istream &cin, vector<T> &a) { for (T &i: a) cin >> i; return cin; } template<typename T> ostream &operator<<(ostream &cout, vector<T> &a) { for (T i: a) cout << i << ' '; return cout; } template<typename T> istream &operator>>(istream &cin, deque<T> &a) { for (T &i: a) cin >> i; return cin; } template<typename T> ostream &operator<<(ostream &cout, deque<T> &a) { for (T i: a) cout << i << ' '; return cout; } } using namespace io; void solution() { int k = 1, m = 0; //cin >> k; while (k--) { int n, s = 0, l; cin >> n, l = (n + 1) / 2; vector<int> a(n), pref(n * 2), dp(n * 2), d(n * 2); cin >> a; for (int i = 0; i < n; ++i) pref[i] = pref[i + n] = a[i]; partial_sum(all(pref), pref.begin()); dp[l - 1] = pref[l - 1]; for (int i = l; i < n * 2; ++i) dp[i] = pref[i] - pref[i - l]; multiset<int> ms; for (int i = l - 1; i < l * 2 - 2; ++i) ms.insert(dp[i]); for (int i = l * 2 - 2; i < n * 2; ++i) { ms.insert(dp[i]); d[i] = *ms.begin(); ms.erase(ms.find(dp[i - l + 1])); } for (int i = 0; i < n * 2; ++i) cmax(s, d[i]); cmax(m, s); } cout << m; } signed main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr), cerr.tie(nullptr); int t = 1; // cin >> t; while (t--) { solution(); cout << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...