# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
953938 | 2024-03-27T00:06:55 Z | AlphaMale06 | Global Warming (CEOI18_glo) | C++17 | 19 ms | 6236 KB |
#include <bits/stdc++.h> using namespace std; #define pb push_back #define int long long #define F first #define S second const int N = 2e5+3; int dp[N], ndp[N]; pair<int, int> mdp[N]; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, d; cin >> n >> d; int a[n]; for(int i=0; i< n; i++)cin >> a[i]; dp[0] = 2e9+1; int mx=0; for(int i = n-1; i>=0; i--){ if(a[i]<dp[mx]){ mx++; dp[mx]=a[i]; continue; } int l = 1, r = mx; while(l<=r){ int s = l+r>>1; if(dp[s]>=a[i])l=s+1; else r=s-1; } dp[l]=min(dp[l], a[i]); mdp[i] = {mx, dp[mx]}; } int ans=mx; if(d==0){ cout << ans << '\n'; return 0; } for(int i = 1; i<=n; i++)ndp[i]=1e9+i; ndp[0]=-1e9; int mxx=0; for(int i=0; i < n; i++){ int l = 0, r = n; if(a[i]-d>ndp[mxx]){ mxx++; ndp[mxx]=a[i]-d; } else{ while(l<=r){ int s = l+r>>1; if(ndp[s]>=a[i]-d)r=s-1; else l=s+1; } ndp[l]=min(ndp[l], a[i]-d); } l = 0, r = n; while(l<=r){ int s = l+r>>1; if(ndp[s]<mdp[i+1].S)l=s+1; else r=s-1; } ans=max(ans, mdp[i+1].F+r); } cout << ans << '\n'; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Incorrect | 1 ms | 2396 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Incorrect | 1 ms | 2396 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Incorrect | 1 ms | 2396 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 19 ms | 6236 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 8 ms | 4956 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 19 ms | 5468 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Incorrect | 1 ms | 2396 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |