oj.uz

Submission #855207

# Submission time Handle Problem Language Result Execution time Memory
855207 2023-09-30T17:09:21 Z QuangBui Difference (POI11_roz) C++14
100 / 100
 717 ms 12224 KB 
// QuangBuiCP
#include "bits/stdc++.h"
using namespace std;

#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(),(a).end()

signed main() {
#ifndef LOCAL
	cin.tie(nullptr)->sync_with_stdio(false);
#endif // LOCAL

	int n;
	cin >> n;
	vector<vector<int>> pos(26);
	for (int i = 1; i <= n; ++i) {
		char c; cin >> c;
		pos[int(c - 'a')].push_back(i);
	}
	int ans = 0;
	for (int x = 0; x < 26; ++x) {
		for (int y = 0; y < 26; ++y) {
			if (x == y) {
				continue;
			}
			if (!SZ(pos[x]) || !SZ(pos[y])) {
				continue;
			}
			vector<int> a = {0};
			{
				int j = 0;
				for (int i : pos[x]) {
					while (j < SZ(pos[y]) && pos[y][j] < i) {
						a.push_back(-1);
						j++;
					}
					a.push_back(1);
				}
				while (j < SZ(pos[y])) {
					a.push_back(-1);
					j++;
				}
			}
#ifdef LOCAL
			cerr << x << ' ' << y << ": ";
			for (int it : a) {
				cerr << it << ' ';
			} cerr << '\n';
#endif // LOCAL
			int sz = SZ(a);
			int mn = n + 1, lst = 0;
			vector<int> pref(sz, 0);
			for (int i = 1; i < sz; ++i) {
				pref[i] = pref[i - 1] + a[i];
				if (i > 1 && a[i] != a[i - 1]) {
					for (int j = lst; j < i - 1; ++j) {
						mn = min(mn, pref[j]);
					}
					lst = i - 1;
				}
				ans = max(ans, pref[i] - mn);
			}
		}
	}
	cout << ans << '\n';

#ifdef LOCAL
	cerr << '\n' << clock() << "ms.";
#endif // LOCAL
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 1008 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 5 ms 348 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 6040 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 341 ms 4840 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 5896 KB Output is correct
2 Correct 440 ms 4552 KB Output is correct
3 Correct 154 ms 5732 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 6336 KB Output is correct
2 Correct 76 ms 11564 KB Output is correct
3 Correct 116 ms 6388 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 597 ms 5796 KB Output is correct
2 Correct 43 ms 12224 KB Output is correct
3 Correct 190 ms 6140 KB Output is correct