Submission #507141

#	Time	Username	Problem	Language	Result	Execution time	Memory
507141		dannyboy20031204	Money (IZhO17_money)	C++17	100 / 100	1084 ms	55232 KiB

money

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
void db() {cout << endl;}
template <typename T, typename ...U> void db(T a, U ...b) {cout << a << ' ', db(b...);}
#ifdef Cloud
#define file freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define file ios::sync_with_stdio(false); cin.tie(0)
#endif
#define pii pair<int, int>
const int inf = 1e9, N = 120, _N = 501, mod = 998244353;
pair<int, int> p[_N][N]{};
pii get(pii u){
    return p[u.fi][u.se] = p[u.fi][u.se] == u ? u : get(p[u.fi][u.se]);
}
void merge(pii a, pii b){
    b = get(b);
    p[a.fi][a.se] = b;
}
int main(){
    
    file;
    /*
    int n;
    cin >> n;
    int a[n], tot = 0;
    for (int &i : a) cin >> i, tot += i;
    if (tot % 2) return cout << 0 << '\n', 0;
    int cnt[N]{};
    bool dp[N]{}, can[_N][N]{};
    for (int i = 0; i < N; i++) p[n][i] = {n, i};
    for (int i = n - 1; i >= 0; i--){
        for (int j = 0; j < N; j++) p[i][j] = p[i + 1][j];
        for (int j = a[i]; j < N; j++) merge(p[i][j], p[i + 1][j - a[i]]);
    }
    dp[0] = 1;
    //db(p[3][8]);
    for (int i = 0; i < n; i++){
        bool can[N]{};
        for (int j = 0; j < N; j++) if (dp[j]) {
            auto u = get(i + 1, j);
            can[u.fi][u.se] = 1;
        }
        for (int j = 0; j < N; j++) {
            auto u = get(i + 1, j);
            if (can[u.fi][u.se] and j * 2 >= tot - a[i]){
                db(i, j, j * 2 - tot + a[i]);
                cnt[j * 2 - tot + a[i]]++;
            }
        }
        for (int j = N - 1; j >= a[i]; j--) dp[j] |= dp[j - a[i]];
    }
    if (!dp[tot / 2]) return cout << 0 << '\n', 0;
    vector<int> ans;
    for (int i = 1; i < N; i++) if (cnt[i] == n) ans.push_back(i);
    cout << ans.size() << '\n';
    for (int i : ans) cout << i << ' ';
    */
    int n;
    cin >> n;
    int a[n], ans = 0;
    for (int &i : a) cin >> i;
    set<int> s;
    for (int i = 0; i < n; i++){
        ans++;
        auto it = s.upper_bound(a[i]);
        int x = it == s.end() ? inf : *it;
        s.insert(a[i]);
        //db(i, x);
        while (i + 1 < n and a[i + 1] >= a[i] and a[i + 1] <= x)
            i++, s.insert(a[i]);
    }
    cout << ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55