Submission #785238

#TimeUsernameProblemLanguageResultExecution timeMemory
785238devariaotaGlobal Warming (CEOI18_glo)C++17
0 / 100
2087 ms248608 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--) 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; } FOR(1,i,x*2+1) { temp = i - (x+1); ans = max(ans,dp(1,0,-1e12)); } 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...