Submission #255598

#	Time	Username	Problem	Language	Result	Execution time	Memory
255598		karma	Bigger segments (IZhO19_segments)	C++14	100 / 100	129 ms	46296 KiB

segments

#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair
//#define int         int64_t

using namespace std;

const int N = int(5e5) + 7;
const int inf = 2e9 + 1;
typedef pair<ll, ll> pii;

ll s[N], ff;
int f[N], n;

struct TVector {
    vector<pii> f;
    void push(pii cur) {
        while(f.size() && f.back().fi >= cur.fi) f.pop_back();
        if(f.empty() || f.back().se < cur.se) f.pb(cur);
    }
    pii get(pii cur) {
        return *prev(lower_bound(f.begin(), f.end(), cur));
    }
} g, q[N];

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> s[i];
        s[i] += s[i - 1];
    }
    g.push(pii(0, 0)); q[0].push(pii(0, 0));
    for(int i = 1; i <= n; ++i) {
        f[i] = g.get(pii(s[i] + 1, 0)).se + 1;
        ff = -q[f[i] - 1].get(pii(s[i] + 1, 0)).se + s[i];
        g.push(pii(ff + s[i], f[i]));
        q[f[i]].push(pii(ff + s[i], s[i]));
        //cout << f[i] << ' ' << ff << '\n';
    }
    cout << f[n];
}

Compilation message (stderr)

segments.cpp: In function 'int32_t main()':
segments.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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