Submission #467038

#	Time	Username	Problem	Language	Result	Execution time	Memory
467038		TeaTime	Bigger segments (IZhO19_segments)	C++17	0 / 100	1 ms	204 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;
    ll pos = 1;
    int j2 = pos;

    for (int i = 2; i <= n; i++) {
        dp[i] = { dp[i - 1].first, dp[i - 1].second + vec[i - 1] };
        
        if (pref[i] - pref[pos] >= dp[pos].second) {
            j2 = pos;
        }
        while ((j2 + 1) < i && dp[j2 + 1].second <= pref[i] - pref[j2 + 1]) j2++;

        dp[i] = { dp[j2].first + 1, pref[i] - pref[j2] };

        if (dp[i].first != dp[i - 1].first) pos = i;

        ans = max(ans, dp[i].first);
    }

    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: 0 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27