Submission #781377

#	Time	Username	Problem	Language	Result	Execution time	Memory
781377		joelgun14	Global Warming (CEOI18_glo)	C++17	0 / 100	335 ms	4160 KiB

glo

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, x;
    cin >> n >> x;
    int t[n + 1];
    for(int i = 1; i <= n; ++i) {
        cin >> t[i];
    }
    // find prefix lis/suffix lis, nanti cari yg max di mana
    // suffix lis -> lds dr belakang
    // prefix lis -> lis dr depan
    int pref[n + 1], suff[n + 2];
    pref[0] = 0, suff[n + 1] = 0;
    set<int> s;
    for(int i = 1; i <= n; ++i) {
        if(s.lower_bound(t[i]) != s.end()) {
            s.erase(s.lower_bound(t[i]));
            s.insert(t[i]);
        }
        else {
            s.insert(t[i]);
        }
        if(*--s.end() == 1e9)
            pref[i] = s.size() - 1;
        else
            pref[i] = s.size();
    }
    for(int i = 1; i <= n; ++i) {
        t[i] = -t[i];
    }
    for(int i = n; i >= 1; --i) {
        if(s.lower_bound(t[i]) != s.end()) {
            s.erase(s.lower_bound(t[i]));
            s.insert(t[i]);
        }
        else    
            s.insert(t[i]);
        suff[i] = s.size();
    }
    int out = 0;
    for(int i = 1; i <= n; ++i)
        out = max(out, pref[i] + suff[i + 1]), cout << pref[i] << " " << suff[i + 1] << endl;
    cout << out << endl;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25