Submission #1307266

#TimeUsernameProblemLanguageResultExecution timeMemory
1307266kevinsGlobal Warming (CEOI18_glo)C++20
15 / 100
2095 ms3500 KiB
#include <iostream>
using namespace std;
#define ll long long


int main(){
	ll n, d;
	cin >> n >> d;

	ll t[n];
	for (ll i = 0; i < n; ++i){
		cin >> t[i];
	}

	ll dp[n];
	ll maximumLIS = 0;
	for (ll left = 0; left < n; ++left){
		for (ll right = left; right < n; ++right){
			for (ll x = -d; x <= d; ++x){
				for (ll i = 0; i < n; ++i) dp[i] = 1;

				for (ll i = left; i <= right; ++i) t[i] += x;

				//compute lis
				dp[0] = 1;
				ll runningMax = 0;
				for (ll i = 0; i < n; ++i){
					ll cur = t[i];
					for (ll j = 0; j < i; ++j){
						if (t[j] < t[i]){
							dp[i] = max(dp[j]+1, dp[i]);
						}
					}
					runningMax = max(runningMax, dp[i]);
				}

				maximumLIS = max(maximumLIS, runningMax);

				for (ll i = left; i <= right; ++i) t[i] -= x;
			}
		}
	}

	cout << maximumLIS << "\n";
}
#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...