Submission #763381

#	Time	Username	Problem	Language	Result	Execution time	Memory
763381		vjudge1	Financial Report (JOI21_financial)	C++17	5 / 100	46 ms	3656 KiB

Main

// #cheat_when_I_was_young
// #cheatkhitacontre #khionhatoicheat
// #thaycuckythatvong
#include "bits/stdc++.h"
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
const int NM = 3e5 + 5;
int n, d, a[NM], res;
vector<int> lis, tmp = {0}, in = {0};
int value() {
    int m = tmp.size() - 1;
    int ma[m+1];
    ma[0] = 0;
    for (int i = 2; i <= m; ++i) if (in[i] - in[i-1] > d) return 0;
    for (int i = 1; i <= m; ++i) ma[i] = max(ma[i-1], tmp[i]);
    int ans = 0;
    for (int i = 1; i <= m; ++i) if (tmp[i] > ma[i-1]) ++ans;
    return ans;
}
void backtrack(int x) {
    if (x == n) {
        tmp.push_back(a[n]);
        in.push_back(n);
        res = max(res, value());
        tmp.pop_back();
        in.pop_back();
        return;
    }
    backtrack(x+1);
    tmp.push_back(a[x]);
    in.push_back(x);
    backtrack(x+1);
    tmp.pop_back();
    in.pop_back();
}
signed main() {
	IOS;
	cin >> n >> d;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	if (n <= 20) {
        backtrack(1);
        cout << res;
        return 0;
	}
	if (d == n) {
        for (int i = 1; i <= n; ++i) {
            if (!lis.size() || lis.back() < a[i]) lis.push_back(a[i]);
            else *lower_bound(lis.begin(), lis.end(), a[i]) = a[i];
        }
        cout << lis.size();
	}
}

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