MSIS-SET.cpp

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <ctime>

#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>

#define PI 3.141592653589

#define int long long
#define ll long long
#define ull unsigned long long
#define II pair<int, int>
#define III pair<int, pair<int, int>>
#define DI pair<double, int>
#define fs first
#define sc second
#define mp(a, b) make_pair(a, b)

const long long LINF = 9223372036854775807;
const int INF = 2147483647;

using namespace std;

struct Node {
    int sum = 0;
    vector<int> v;

    Node() {}
    Node(int x) {
        this->sum = x;
        this->v.push_back(x);
    }
    Node(Node n, int x) {
        this->sum = n.sum + x;
        this->v.resize(n.v.size());
        for(int i = 0; i < n.v.size(); i++) {
            this->v[i] = n.v[i];
        }
        this->v.push_back(x);
    }
};

bool operator < (const Node& a, const Node& b) {
    if(a.sum < b.sum) return true;
    if(a.sum == b.sum) {
        if(a.v.size() == 0) return true;
        if(b.v.size() == 0) return false;
        return a.v.back() <= b.v.back();
    }
    return false;
}

bool cmpSum(const Node& a, const Node& b) {
    if(a.sum < b.sum) return true;
    if(a.sum == b.sum && a.v.back() <= b.v.back()) return true;
    return false;
}

bool cmpLE(const Node& a, const Node& b) {
    if(a.v.size() == 0) return true;
    if(b.v.size() == 0) return false;
    if(a.v.back() <= b.v.back()) return true;
    return false;
}

void genTest(int n) {
    freopen("MSIS3.INP", "w", stdout);
    cout << n << endl;
    for(int i = 1; i <= n; i++) cout << i << " ";
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    // genTest(10000);
    // return 0;

    freopen("MSIS3.INP", "r", stdin);
    freopen("MSIS3.OUT", "w", stdout);

    int n, inp;
    cin >> n >> inp;

    set<Node> S;
    S.insert(Node());
    S.insert(Node(inp));

    vector<set<Node>::iterator> toErase;
    for (int i = 0; i < n-1; i++) {
        cin >> inp;
        set<Node>::iterator s_less =
            --upper_bound(S.begin(), S.end(), Node(inp), cmpLE);
        Node ns = Node(*s_less, inp);
        set<Node>::iterator s_more =
            lower_bound(S.begin(), S.end(), ns, cmpSum);

        ++s_less;
        while(s_less != s_more) toErase.push_back(s_less++);
        for(int j = 0; j < toErase.size(); j++) S.erase(toErase[j]);
        toErase.clear();
        S.insert(ns);
    }

    // for(auto& au : S) {
    //     cout << au.sum << endl;
    //     for(int i = 0; i < au.v.size(); i++) {
    //         cout << au.v[i] << " ";
    //     }
    //     cout << endl << endl;
    // }
    cout << (--S.end())->sum << endl;

    return 0;
}