제출 #785567

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
785567		devariaota	Global Warming (CEOI18_glo)	C++17	28 / 100	2079 ms	262144 KiB

glo

#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];
map<int,bool> vis[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(!vis[idx][prev]) {
    vis[idx][prev] = true;
    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,-1e9) << endl;
    return 0;
  }
  else {
    FOR(1,i,x*2+1) {
      temp = i - (x+1);
      ans = max(ans,dp(1,0,-1e9));
    }
    cout << ans << endl;
  }
}

/*
8 0
7 3 5 12 2 7 3 4
*/

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