Submission #785200

#	Time	Username	Problem	Language	Result	Execution time	Memory
785200		devariaota	Global Warming (CEOI18_glo)	C++17	0 / 100	2068 ms	6484 KiB

glo

#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 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;
    }    

    cout << dp[1][0] << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    int t = 1;
    if(mutipletestcase) cin >> t; 
    while(t--) solve();
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25