Submission #467030

#	Time	Username	Problem	Language	Result	Execution time	Memory
467030		TeaTime	Bigger segments (IZhO19_segments)	C++17	37 / 100	1575 ms	3220 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;
     
    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;
        for (int i = 2; i <= n; i++) {
            pair<ll, ll> bst = { -1, -1 };
            for (int j = 0; j < i; j++) {
                if (pref[i] - pref[j] >= dp[j].second) {
                    bst = max(bst, { dp[j].first + 1, -(pref[i] - pref[j]) });
                }
            }
            bst.second = -bst.second;
            dp[i] = bst;
            ans = max(ans, dp[i].first);
          if (dp[i].first < dp[i - 1].first) return 1;
        }
     
        cout << ans;
     
        return 0;
    }

Compilation message (stderr)

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

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