Submission #467029

#	Time	Username	Problem	Language	Result	Execution time	Memory
467029		TeaTime	Bigger segments (IZhO19_segments)	C++17	13 / 100	1 ms	332 KiB

segments

//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <cmath>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

const ll SZ = 1e6 + 100, INF = 1e9, AM = 2, K = 26, LG = 20;

pair<ll, ll> dp[SZ];
ll n;
vector<ll> vec;

signed main() {
    fastInp;

    cin >> n;
    vec.resize(n);
    vector<ll> pref(1);
    for (auto& c : vec) {
        cin >> c;
        pref.push_back(pref.back() + c);
    }

    ll i2 = 0;
    dp[1] = { 1, vec[0] };
    ll ans = 1;
    vector<ll> bstj;
    bstj.push_back(1);
    bstj.push_back(0);
    for (int i = 2; i <= n; i++) {
        pair<ll, ll> bst = { -1, -1 };
        for (auto j : bstj) {
            int j2 = j;
            for (int lg = LG - 1; lg >= 0; lg--) {
                if (j2 + (1ll << lg) < i && pref[i] - pref[j2 + (1ll << lg)] >= dp[j2 + (1ll << lg)].second) j2 = j2 + (1ll << lg);
            }
            if (pref[i] - pref[j2] >= dp[j2].second) {
                bst = max(bst, { dp[j2].first + 1, -(pref[i] - pref[j2]) });
            }
        }
        bst.second = -bst.second;
        dp[i] = bst;
        if (ans < dp[i].first) {
            bstj.insert(bstj.begin(), i);
        }
        ans = max(ans, dp[i].first);
        while (dp[bstj.back()].first < ans - 3) bstj.pop_back();

        for (auto& c : bstj) {
            if (dp[bstj.back()].first == bst.first) {
                if (dp[bstj.back()].second > bst.second) c = i;
            }
        }
    }

    cout << ans;

    return 0;
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:37:8: warning: unused variable 'i2' [-Wunused-variable]
   37 |     ll i2 = 0;
      |        ^~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27