Submission #785578

#	Time	Username	Problem	Language	Result	Execution time	Memory
785578		devariaota	Global Warming (CEOI18_glo)	C++17	28 / 100	2070 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];
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;
}

• 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