Submission #763384

#	Time	Username	Problem	Language	Result	Execution time	Memory
763384		cheat_when_I_was_young	Financial Report (JOI21_financial)	C++17	19 / 100	43 ms	3664 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;
vector<pair<int,int>> tmp;
int value() {
    if (!tmp.size()) return 0;
    if (tmp.back().second != n) return 0;
    int ma = -1, ans = 0;
    for (int i = 0; i < tmp.size(); ++i) {
        if (i && tmp[i].second - tmp[i-1].second > d) return 0;
        if (tmp[i].first > ma) ++ans;
        ma = max(ma, tmp[i].first);
    }
    return ans;
}
void backtrack(int x) {
    if (x == n+1) {
        res = max(res, value());
        return;
    }
    backtrack(x+1);
    tmp.push_back({a[x], x});
    backtrack(x+1);
    tmp.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();
	}
}

Compilation message (stderr)

Main.cpp: In function 'int value()':
Main.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0; i < tmp.size(); ++i) {
      |                     ~~^~~~~~~~~~~~

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