제출 #785578

#제출 시각아이디문제언어결과실행 시간메모리
785578devariaotaGlobal Warming (CEOI18_glo)C++17
28 / 100
2070 ms262144 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl "\n"
#define pii pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define pque priority_queue
#define pqueg priority_queue<ll,vector<ll>,greater<ll>>
#define que queue<ll>
#define FOR(m,i,n) for(int i=(m); i<=(n); i++)
#define FORM(m,i,n) for(int i=(m); i>=(n); i--)
int n,x,ans,temp;
int a[200200];
map<int,int> memo[200200][4];
map<int,int> memo1[200200];
int dp(int idx, int stat, int prev) {
  if(idx == n + 1) return 0;
  if(memo[idx][stat][prev] == 0) {
    memo[idx][stat][prev] = dp(idx+1,stat,prev);
      if(stat == 0) {
          if(prev < a[idx]) { // ambil ga nambah
            memo[idx][stat][prev] = max(memo[idx][stat][prev],
            dp(idx+1,0,a[idx]) + 1);
          }
          if(prev < a[idx]+temp) { // ambil nambah
            memo[idx][stat][prev] = max(memo[idx][stat][prev],
            dp(idx+1,1,a[idx]+temp) + 1);
          }
      }
      else if(stat == 1) {
          if(prev < a[idx] + temp) { // ambil dan masih nambah
              memo[idx][stat][prev] = max(memo[idx][stat][prev],
            dp(idx+1,1,a[idx]+temp) + 1);
          }
          if(prev < a[idx]) { // ambil dah ga nambah
            memo[idx][stat][prev] = max(memo[idx][stat][prev],
            dp(idx+1,2,a[idx]) + 1);
          }  
      }
      else {
          if(prev < a[idx]) { // ambil dah ga nambah
            memo[idx][stat][prev] = max(memo[idx][stat][prev],
            dp(idx+1,2,a[idx]) + 1);
          }
      }
    } 
    return memo[idx][stat][prev];
}
int dp1(int idx, int prev) {
    if(idx == n+1) return 0;
    if(memo1[idx][prev] == 0) {
      memo1[idx][prev] = dp1(idx+1,prev);
      if(prev < a[idx]) {
        memo1[idx][prev] = max(memo1[idx][prev],dp1(idx+1,a[idx])+1);
      }
    }
    return memo1[idx][prev];
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> x;
    FOR(1,i,n) {
      cin >> a[i];
    }
    if(x == 0) {
      cout << dp1(1,-1e8) << endl;
      return 0;
    }
    FOR(1,i,x*2+1) {
      temp = i - (x+1);
      ans = max(ans,dp(1,0,-1e8));
   }
    cout << ans << endl;
}
#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...