제출 #1307269

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307269		kevins	Global Warming (CEOI18_glo)	C++20	15 / 100	2095 ms	3540 KiB

glo

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <iostream>
using namespace std;
#define ll long long


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n, d;
	cin >> n >> d;

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

	ll dp[n];

	if (d == 0){
		for (ll i = 0; i < n; ++i) dp[i] = 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]);
		}
		cout << runningMax << "\n";
		return 0;
	}


	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";
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25