Основное
 
 
Отправитель Задача Язык Вердикт Время Память Отослано Протест.  
215118514 Дорешивание:
Kuber
1467B - 15 C++14 (GCC 6-32) Превышено ограничение времени на тесте 2 1000 мс 4740 КБ 2023-07-23 05:47:40 2023-07-23 05:47:40
→ Исходный код
#include <bits/stdc++.h>
#include <cstdint>
using namespace std;
typedef long long ll;

typedef vector<ll> vi;
typedef pair<ll, ll> pi;

#define PB push_back
#define MP make_pair
#define FOR for(long long i = 0;i<n;i++)
#define SP << " " <<
#define F first
#define S second

#define MOD 1000000007
#define max_n 200005
#define lMOD 1e16

bool hov(int i, vector<ll> v){
	if(i == 0 or i == v.size() - 1) return false;
	if(v[i] > v[i-1] and v[i] > v[i+1]) return true;
	else if(v[i] < v[i-1] and v[i] < v[i+1]) return true;
	else return false;
}

ll calc(int i, vector<ll> v){
	ll n;
	v[i] = v[i-1];
	n = hov(i, v) + hov(i-1, v) + hov(i+1, v);
	return n;
}
void solve(){
	int n; cin >> n;
	vector<ll> a(n);
	vector<bool> s(n, false);
	ll ans = 0;
	for(int i = 0; i< n; i++)	{cin >> a[i];
		if(i!=0){s[i-1] = hov(i-1, a); ans += s[i-1];}

	}
	
	
	// for(int i = 1; i<n-1; i++){
	// 	if(a[i] > a[i-1] and a[i] > a[i+1]) s[i] = true;
	// 	else if(a[i] < a[i-1] and a[i] < a[i+1]) s[i] = true;
	// 	ans+= s[i];
	// }
	ll diff = 0;
	for(int i = 1 ;i < n-1; i++){
		ll old = s[i-1] + s[i] + s[i+1];
		ll nu = calc(i, a);
		diff = max(diff, old- nu);
	}
	cout << ans - diff << "\n";
}

int main() {
#ifndef ONLINE_JUDGE

	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);

#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	long long t;
	// t = 1;
	cin >> t;

	while (t--) {
	solve();
	}
	return 0;
}
?
Время: ? ms, память: ? КБ
Вердикт: ?
Ввод
?
Вывод участника
?
Ответ жюри
?
Комментарий чекера
?
Диагностика
?
Показать детали тестирования