Submission #1068789

#TimeUsernameProblemLanguageResultExecution timeMemory
1068789PotatoTheWarriorFRTTGlobal Warming (CEOI18_glo)C++14
10 / 100
2077 ms3560 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll p1 = 27644437; ll p2 = 1000000007; int LIS(int n, ll a[]) { ll dp[n+1]; // dp[l] = smallest element at which a sequence of size l ends; int ans = 1; dp[1] = a[0]; for(int i=1;i<n;i++) { if(dp[ans] < a[i]) { ans++; dp[ans] = a[i]; }else if(a[i] < dp[1]) { dp[1] = a[i]; }else{ int r = ans; int l = 1; while(r - l > 1) { int m = (r+l)/2; if(a[i] < dp[m]) { r = m; }else if(a[i] >= dp[m]) { l = m; } } dp[r] = a[i]; } } return ans; } void solve() { int n, x; cin >> n >> x; ll a[n+1]; for(int i=0;i<n;i++) { cin >> a[i]; } if(x == 0) { cout << LIS(n, a) << endl; }else{ int ans = 0; for(int i=0;i<n;i++) { for(int j=i;j<n;j++) { for(int d=-x;d<=x;d++) { for(int k=i;k<=j;k++) { a[k]+=d; } ans = max(ans, LIS(n, a)); for(int k=i;k<=j;k++) { a[k]-=d; } } } } cout << ans << endl; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); // int t; cin >> t; // while(t--) solve(); char dksfjn; cin >> dksfjn; }
#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...