Submission #531852

#TimeUsernameProblemLanguageResultExecution timeMemory
531852abc864197532Bigger segments (IZhO19_segments)C++17
100 / 100
90 ms12996 KiB
#include <bits/stdc++.h> using namespace std; #define lli long long int #define mp make_pair #define pb push_back #define eb emplace_back #define pii pair <int, int> #define X first #define Y second #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() void abc() {cout << endl;} template <typename T, typename ...U> void abc(T a, U ...b) { cout << a << ' ', abc(b...); } template <typename T> void printv(T l, T r) { for (; l != r; ++l) cout << *l << " \n"[l + 1 == r]; } template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) { return o >> a.X >> a.Y; } template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) { return o << '(' << a.X << ", " << a.Y << ')'; } template <typename T> ostream& operator << (ostream& o, vector<T> a) { bool is = false; if (a.empty()) return o << "{}"; for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;} return o << '}'; } template <typename T> struct vv : vector <vector <T>> { vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {} vv() {} }; template <typename T> struct vvv : vector <vv <T>> { vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {} vvv() {} }; #ifdef Doludu #define test(args...) abc("[" + string(#args) + "]", args) #define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout); #else #define test(args...) void(0) #define owo ios::sync_with_stdio(false); cin.tie(0) #endif const int mod = 1e9 + 7, N = 1001, logN = 20, K = 111, C = 7; int main () { owo; int n; cin >> n; vector <lli> pre(n + 1); vector <int> dp(n + 1, 0), p(n + 1, 0); for (int i = 0, x; i < n; ++i) { cin >> x; pre[i + 1] = pre[i] + x; } for (int i = 1; i <= n; ++i) { p[i] = max(p[i], p[i - 1]); dp[i] = dp[p[i]] + 1; int x = lower_bound(all(pre), pre[i] * 2 - pre[p[i]]) - pre.begin(); p[x] = max(p[x], i); } cout << dp[n] << '\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...
#Verdict Execution timeMemoryGrader output
Fetching results...