5577 | 2023-08-01 15:26:50 | 111 | Mágikus intervallum | cpp14 | Hibás válasz 25/100 | 89ms | 32792 KiB |
#include <bits/extc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
void prev_greater(vector<int>& r, const vector<int>& a) {
stack<int> s;
for (int i = 0; i < a.size(); i++) {
while (!s.empty() && a[s.top()] <= a[i]) {
s.pop();
}
r[i] = s.empty() ? -1 : s.top();
s.push(i);
}
}
void next_greater(vector<int>& r, const vector<int>& a) {
stack<int> s;
for (int i = a.size() - 1; i >= 0; i--) {
while (!s.empty() && a[s.top()] <= a[i]) {
s.pop();
}
r[i] = s.empty() ? a.size() : s.top();
s.push(i);
}
}
signed main() {
#ifdef CB
ifstream fin("be2.txt");
cin.rdbuf(fin.rdbuf());
ofstream fout("ki.txt");
#endif
int N;
cin >> N;
vector<int> v(N);
for (int i = 0; i < N; i++) {
cin >> v[i];
}
vector<int> p(N), n(N);
prev_greater(p, v);
next_greater(n, v);
int ans = 0;
int ms, me;
for (int i = 0; i < N; i++) {
int s = i, e = i;
int m = v[i];
while (true) {
bool bs = s - 1 > p[i] && m + v[s - 1] <= v[i] * 2;
bool be = e + 1 < n[i] && m + v[e + 1] <= v[i] * 2;
if (bs && be) {
if (v[s - 1] <= v[e + 1]) {
s--;
m += v[s];
}
else {
e++;
m += v[e];
}
}
else if (bs) {
s--;
m += v[s];
}
else if (be) {
e++;
m += v[e];
}
else {
break;
}
}
if (ans < e - s + 1) {
ans = e - s + 1;
ms = s;
me = e;
}
}
cout << ms + 1 << " " << me + 1 << endl;
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 1812 KiB | ||||
2 | Elfogadva | 71ms | 9332 KiB | ||||
subtask2 | 0/5 | ||||||
3 | Elfogadva | 3ms | 3540 KiB | ||||
4 | Elfogadva | 3ms | 3776 KiB | ||||
5 | Elfogadva | 3ms | 3972 KiB | ||||
6 | Elfogadva | 3ms | 4180 KiB | ||||
7 | Hibás válasz | 3ms | 4300 KiB | ||||
8 | Elfogadva | 3ms | 4272 KiB | ||||
subtask3 | 0/10 | ||||||
9 | Elfogadva | 3ms | 4548 KiB | ||||
10 | Hibás válasz | 3ms | 4656 KiB | ||||
11 | Elfogadva | 3ms | 4768 KiB | ||||
12 | Hibás válasz | 3ms | 4872 KiB | ||||
13 | Elfogadva | 3ms | 5160 KiB | ||||
14 | Elfogadva | 3ms | 5240 KiB | ||||
subtask4 | 10/10 | ||||||
15 | Elfogadva | 3ms | 5256 KiB | ||||
16 | Elfogadva | 3ms | 5352 KiB | ||||
17 | Elfogadva | 3ms | 5596 KiB | ||||
18 | Elfogadva | 8ms | 6540 KiB | ||||
19 | Elfogadva | 74ms | 14184 KiB | ||||
20 | Elfogadva | 43ms | 14788 KiB | ||||
21 | Elfogadva | 43ms | 15548 KiB | ||||
subtask5 | 15/15 | ||||||
22 | Elfogadva | 2ms | 8532 KiB | ||||
23 | Elfogadva | 43ms | 15624 KiB | ||||
24 | Elfogadva | 59ms | 18620 KiB | ||||
subtask6 | 0/60 | ||||||
25 | Elfogadva | 71ms | 17644 KiB | ||||
26 | Elfogadva | 81ms | 19820 KiB | ||||
27 | Hibás válasz | 81ms | 21268 KiB | ||||
28 | Hibás válasz | 76ms | 21708 KiB | ||||
29 | Hibás válasz | 81ms | 23040 KiB | ||||
30 | Hibás válasz | 78ms | 24372 KiB | ||||
31 | Hibás válasz | 87ms | 26864 KiB | ||||
32 | Hibás válasz | 89ms | 28412 KiB | ||||
33 | Elfogadva | 50ms | 28908 KiB | ||||
34 | Elfogadva | 50ms | 29840 KiB | ||||
35 | Hibás válasz | 50ms | 30508 KiB | ||||
36 | Elfogadva | 75ms | 31912 KiB | ||||
37 | Elfogadva | 37ms | 32176 KiB | ||||
38 | Elfogadva | 43ms | 32792 KiB | ||||
39 | Elfogadva | 3ms | 25812 KiB |