Submission #1257756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257756		s1zzl3	Financial Report (JOI21_financial)	C++17	0 / 100	38 ms	6216 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct FenwickMax {
    int n;
    vector<int> bit;
    FenwickMax(int _n=0){init(_n);}
    void init(int _n){
        n=_n;
        bit.assign(n+1, 0);
    }
    void update(int i, int val){
        for(; i<=n; i += i&-i) bit[i] = max(bit[i], val);
    }
    int query(int i){
        int res = 0;
        for(; i>0; i -= i&-i) res = max(res, bit[i]);
        return res;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N, D;
    cin >> N >> D;
    vector<long long> A(N+1);
    for(int i=1;i<=N;i++) cin >> A[i];
    vector<long long> vals;
    vals.reserve(N);
    for(int i=1;i<=N;i++) vals.push_back(A[i]);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    auto getIndex = [&](long long x){
        return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) + 1; 
    };
    FenwickMax bit((int)vals.size());
    vector<int> dp(N+1, 0);
    for(int i=1;i<=N;i++){
        int idx = getIndex(A[i]);
        int best = 0;
        if(idx-1 >= 1) best = bit.query(idx-1);
        dp[i] = best + 1;
        bit.update(idx, dp[i]);
    }
    cout << dp[N] << '\n';
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35