Submission #785207

#TimeUsernameProblemLanguageResultExecution timeMemory
785207christinelynnGlobal Warming (CEOI18_glo)C++17
28 / 100
2086 ms6488 KiB
#include <bits/stdc++.h>
using namespace std;

# define int long long
# define fir first
# define sec second
# define pb push_back
# define endl "\n"

const int cnst = 2e5+5;
bool mutipletestcase = 0;
//bool debug = false;

void solve() {
    int n, x; cin >> n >> x;

    int num[n+5];

    for(int i = 1; i<=n; i++) cin >> num[i];

    // if(x == 0) {
    //     int vis[n+5];
    //     memset(vis, 0, sizeof(vis));
    //     int ans = 0;
    // }
    // else if(x == 1e9) {}

    int ans = 0;
    int dp[n+5][3];
    memset(dp, 0, sizeof(dp)); dp[n][1] = dp[n][0] = 1;

    for(int i = n-1; i>=1; i--) {
        for(int k = i+1; k<=n; k++) {
            if(num[k] > num[i]) {
                dp[i][0] = max(dp[i][0], dp[k][0]);
                dp[i][1] = max(dp[i][1], dp[k][1]);
            }
            else if(num[i]-num[k] < x) {
                dp[i][0] = max(dp[i][0], dp[k][1]);
            }
        }

        dp[i][0] += 1, dp[i][1] += 1;
        ans = max(ans, dp[i][0]);
    }    

    // for(int i = 1; i<=n; i++) cerr << dp[i][0] << " " << dp[i][1] << endl; cerr << endl;

    cout << ans << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    int t = 1;
    if(mutipletestcase) cin >> t; 
    while(t--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...