| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1300530 | mduchello | Financial Report (JOI21_financial) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
//=====================================================================================================================================
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pii pair<int, int>
#define BIT(i, mask) ((mask >> (i)) & 1)
#define DAOBIT(i, mask) ((mask ^ (1 << i)))
#define OFFBIT(i, mask) ((mask & ~(1 << (i))))
#define ONBIT(i, mask) ((mask | (1 << (i))))
#define nmax 1000007
//=====================================================================================================================================
const int N = 1e6 + 7;
const ll mod = 1e9 + 6;
const ll MOD = 1e9 + 7;
const ll inf = 1e18;
int n, d;
ll h[N];
//=====================================================================================================================================
void fre(){
freopen("RAMTHANGTAM.INP", "r", stdin);
freopen("RAMTHANGTAM.out", "w", stdout);
}
ll gcd(ll a, ll b){
return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b){
return (a / gcd(a, b)) * b;
}
namespace sub1{
int ans = 0;
void work(int i, ll mx, int last, int cnt){
if(i - last > d) return;
if(i == n + 1){
ans = max(ans, cnt);
return;
}
work(i + 1, max(mx, h[i]), i, cnt + (h[i] > mx));
if(i < n) work(i + 1, mx, last, cnt);
}
void solve(){
work(1, -1, n + 1, 0);
cout << ans << '\n';
}
}
namespace sub2{
const int N_sub2 = 400 + 7;
int dp[N_sub2][N_sub2];
vector<pli> b;
void roirac(){
sort(b.begin(), b.end());
h[b[0].second] = 1;
int counter = 1;
for (int i = 1; i < n; ++i)
if (b[i].first != b[i - 1].first)
h[b[i].second] = ++counter;
else
h[b[i].second] = counter;
}
void solve(){
int ans = 0;
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
dp[i][j] = -1 * N_sub2 * N_sub2;
}
}
dp[0][0] = 0;
for(int i = 1; i <= n; i++){
b.pb({h[i], i});
}
roirac();
for(int i = 1; i <= n; i++){
dp[i][h[i]] = 1;
for(int j = i - 1; j >= max(i - d, 0); j--){
for(int k = 1; k < h[i]; k++){
dp[i][h[i]] = max(dp[i][h[i]], dp[j][k] + 1);
ans = max(ans, dp[i][h[i]]);
}
for(int k = h[i]; k <= n; k++){
dp[i][k] = max(dp[i][k], dp[j][k]);
ans = max(ans, dp[i][k]);
}
}
}
cout << ans << '\n';
}
}
namespace sub3{
const int N_sub3 = 7000 + 7;
int dp[N_sub3];
int r[N_sub3];
vector<pli> b;
void roirac(){
sort(b.begin(), b.end());
h[b[0].second] = 1;
int counter = 1;
for (int i = 1; i < n; ++i)
if (b[i].first != b[i - 1].first)
h[b[i].second] = ++counter;
else
h[b[i].second] = counter;
}
void solve(){
int ans = 0;
for(int i = 1; i <= n; i++){
b.pb({h[i], i});
}
roirac();
for(int i = 1; i <= n; i++){
r[i] = n + 1;
for(int j = i + 1; j <= n; j++){
if(h[j] > h[i]){
r[i] = j;
break;
}
}
}
for(int i = 1; i <= n; i++){
dp[i] = 1;
for(int j = 1; j < i; j++){
if(a[i] > a[j]){
if(i - j <= d || r[i] >= i) dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
cout << ans << '\n';
}
}
namespace sub4{
void solve(){
int ans = 0;
stack<int> st;
for(int i = n; i >= 1; i--){
while(!st.empty() && st.top() <= h[i]) st.pop();
st.push(h[i]);
int len = st.size();
ans = max(ans, len);
}
cout << ans << '\n';
}
}
namespace sub5{
vector<ll> dp;
void solve(){
for(int i = 1; i <= n; i++){
int x = lower_bound(dp.begin(), dp.end(), h[i]) - dp.begin();
if(x == dp.size()) dp.push_back(h[i]);
else dp[x] = h[i];
}
cout << dp.size() << '\n';
}
}
//=====================================================================================================================================
int main(){
cin.tie(0)->sync_with_stdio(0);
// fre();
cin >> n >> d;
for(int i = 1; i <= n; i++){
cin >> h[i];
}
if(n <= 20){
sub1 :: solve();
return 0;
}
if(n <= 400){
sub2 :: solve();
return 0;
}
if(n <= 7000){
sub3 :: solve();
return 0;
}
if(d == 1){
sub4 :: solve();
return 0;
}
if(d == n){
sub5 :: solve();
return 0;
}
return 0;
}