Submission #785490

#	Time	Username	Problem	Language	Result	Execution time	Memory
785490		devariaota	Global Warming (CEOI18_glo)	C++17	28 / 100	2072 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--)
ll n,x,ans,temp;
ll a[200200];
map<ll,ll> memo[200200][4];
map<ll,ll> memo1[200200];
ll dp(ll idx, ll stat, ll 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];
}
ll dp1(ll idx, ll 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,-1e12) << endl;
    return 0;
  }
  else {
    FOR(1,i,x*2+1) {
      temp = i - (x+1);
      ans = max(ans,dp(1,0,-1e12));
    }
    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