| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 895372 | MilosMilutinovic | AAQQZ (JOI15_aaqqz) | C++14 | 102 ms | 36072 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int BruteForce(vector<int> a) {
int n = (int) a.size();
int res = 0;
int L, R;
for (int l = 0; l < n; l++) {
for (int r = l; r < n; r++) {
vector<int> seq;
for (int i = l; i <= r; i++) {
seq.push_back(a[i]);
}
sort(seq.begin(), seq.end());
vector<int> new_a = a;
for (int j = l; j <= r; j++) {
new_a[j] = seq[j - l];
}
vector<vector<bool>> f(n, vector<bool>(n));
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (i == j) {
f[i][j] = true;
continue;
}
if (new_a[i] == new_a[j]) {
if (i + 1 == j) {
f[i][j] = true;
} else {
f[i][j] = f[i + 1][j - 1];
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (f[i][j]) {
res = max(res, j - i + 1);
if (res == j - i + 1) {
L = l;
R = r;
}
}
}
}
}
}
cout << "-- " << L << " " << R << '\n';
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, c;
cin >> n >> c;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
--a[i];
}
while (true) {
int ans = 0;
{
vector<int> cnt(c);
for (int i = 0; i < n; i++) {
cnt[a[i]] += 1;
}
ans = max(ans, *max_element(cnt.begin(), cnt.end()));
}
for (int rot = 0; rot < 2; rot++) {
vector<vector<int>> dp(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = n - 1; j >= i; j--) {
if (i == j) {
dp[i][j] = 1 + (i > 0 && j + 1 < n ? dp[i - 1][j + 1] : 0);
} else {
if (a[i] != a[j]) {
dp[i][j] = 0;
continue;
}
dp[i][j] = 1 + (i > 0 && j + 1 < n ? dp[i - 1][j + 1] : 0);
}
}
}
auto Extend = [&](int L, int R, bool f) {
ans = max(ans, R - L + 1);
if (!f) {
int ptr = R;
vector<int> cnt(c);
for (int i = L - 1; i >= 0; i--) {
if (i < L - 1 && a[i] < a[i + 1]) {
break;
}
bool ok = true;
while (ptr + 1 < n && cnt[a[i]] == 0) {
ptr += 1;
if (a[ptr] < a[i]) {
ok = false;
}
cnt[a[ptr]] += 1;
}
if (!cnt[a[i]] || !ok) {
break;
}
cnt[a[i]] -= 1;
for (int j = (i == L - 1 ? 0 : a[i + 1]); j < a[i]; j++) {
if (cnt[j] > 0) {
ok = false;
break;
}
}
if (!ok) {
break;
}
int foo = 0;
if (L - i == ptr - R && i > 0 && ptr + 1 < n) {
foo = dp[i - 1][ptr + 1] * 2;
}
ans = max(ans, R - L + 1 + (L - i) * 2 + foo);
}
} else {
int mn = c;
for (int i = L + 1; i < n; i++) {
if (a[i] < a[L]) {
mn = a[i];
break;
}
}
if (mn == c) {
return;
}
int ptr = R;
vector<int> cnt(c);
int cnt_mn = 0;
for (int i = L; i >= 0; i--) {
if (i < L && a[i] < a[i + 1]) {
break;
}
bool ok = true;
while (ptr + 1 < n && cnt[a[i]] == 0) {
ptr += 1;
if (a[ptr] < mn) {
break;
}
if (a[ptr] != mn) {
if (a[ptr] < a[i]) {
ok = false;
break;
}
cnt[a[ptr]] += 1;
} else {
cnt_mn += 1;
}
}
if (!cnt[a[i]] || !ok) {
break;
}
cnt[a[i]] -= 1;
for (int j = (i == L ? 0 : a[i + 1]); j < a[i]; j++) {
if (cnt[j] > 0) {
ok = false;
break;
}
}
if (!ok) {
break;
}
while (true) {
int foo = 0;
if (L - i + 1 == ptr - R - cnt_mn && i > 0 && ptr + 1 < n) {
foo = dp[i - 1][ptr + 1] * 2;
}
ans = max(ans, (L - i + 1) * 2 + cnt_mn + foo);
if (ptr + 1 < n && a[ptr + 1] == mn) {
cnt_mn += 1;
ptr += 1;
} else {
break;
}
}
}
vector<int> cntL(c), cntR(c);
ptr = R;
cnt_mn = 0;
for (int i = L; i >= 0; i--) {
if (i < L && a[i + 1] > a[i]) {
break;
}
cntL[a[i]] += 1;
bool ok = true;
while (ptr + 1 < n) {
if (a[ptr + 1] < mn) {
break;
} else if (a[ptr + 1] == mn) {
cnt_mn += 1;
} else {
if (a[ptr + 1] < a[i]) {
break;
}
cntR[a[ptr + 1]] += 1;
}
ptr += 1;
}
if (cntL[a[i]] > cntR[a[i]] || !ok) {
break;
}
if (!ok) {
break;
}
for (int j = (i == L ? 0 : a[i + 1]); j < a[i]; j++) {
while (ptr > R && cntR[j] > cntL[j]) {
if (a[ptr] == mn) {
cnt_mn -= 1;
ptr -= 1;
continue;
}
cntR[a[ptr]] -= 1;
if (cntL[a[ptr]] > cntR[a[ptr]]) {
ok = false;
break;
}
ptr -= 1;
}
if (cntR[j] > cntL[j]) {
ok = false;
break;
}
}
if (!ok) {
break;
}
ans = max(ans, (L - i + 1) * 2 + cnt_mn);
}
}
};
for (int i = 0; i < n; i++) {
Extend(i - dp[i][i] + 1, i + dp[i][i] - 1, false);
Extend(i, i, false);
if (i + 1 < n && a[i] == a[i + 1]) {
Extend(i - dp[i][i + 1] + 1, i + dp[i][i + 1], false);
}
}
for (int i = 0; i < n; i++) {
Extend(i, i, true);
}
for (int i = 0; i < n; i++) {
a[i] = c - a[i] - 1;
}
reverse(a.begin(), a.end());
}
cout << ans << '\n';
break;
}
return 0;
}
/*
10 6
5 5 4 0 1 1 0 5 3 4
7 4
2 3 2 2 3 3 1
*/
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||