Submission #442046

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
442046	2021-07-06T21:06:16 Z	cabbagecabbagecabbage	Difference (POI11_roz)	C++14	100 / 100	106 ms	6312 KB

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
template<typename T> void in(T& x){ cin >> x; }
template<typename T, typename... Args> void in(T& x, Args&...args){ cin >> x, in(args...); }
template<typename T> void out(const T& x){ cout << x << "\n"; }
template<typename T, typename... Args> void out(const T& x, const Args&...args){ cout << x << " ", out(args...); }
// #define int 				long long
#define f(a) 				for (int i = 0; i < a; ++i)
#define ff(a) 				for (int j = 0; j < a; ++j)
#define f2(a, b) 			for (int i = a; i < b; ++i)
#define ff2(a, b) 			for (int j = a; j < b; ++j)
#define fil(arr, val) fill((remove_array<decltype(arr)>::type*)&arr, (remove_array<decltype(arr)>::type*)((char*)&arr + sizeof(arr)), val)
template<typename T> struct remove_array {typedef T type;};
template<typename T, size_t sz> struct remove_array<T[sz]> { typedef typename remove_array<T>::type type;};
#define mem(a, b)			memset(a, b, sizeof(a))
#define min(a, b) 			((a) < (b) ? (a) : (b))
#define max(a, b) 			((a) > (b) ? (a) : (b))
#define inf 				0x3f3f3f3f
#define llinf 				0x3f3f3f3f3f3f3f3f
#define eb 					emplace_back
typedef long long 			ll;
typedef vector<int> 		vi;
typedef pair<int, int> 		pii;

/*
maximize (cur[i] - pre[i]) - (cur[j] - pre[j])
= maximize (cur[i] - cur[j]) - minimize (pre[i] - pre[j])

keep track of 
cur[i][j] value of freq(i) - freq(j) in the current prefix
pre[i][j] smallest value of freq(i) - freq(j) in the previous prefixes
cnt[i][j] freq(j) when pre[i][j] was taken
pre2[i][j] second smallest value of freq(i) - freq(j) in the previous prefixes, with freq(j) > cnt[i][j]
*/

const int nax = 1e6 + 5, mod = 1e9 + 7, alpha = 26;
int n, cur[alpha][alpha], pre[alpha][alpha], cnt[alpha][alpha], pre2[alpha][alpha], num[nax], freq[alpha];
string s;


int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	in(n,s);
	mem(pre2,inf);
	f(n){
		num[i] = s[i] - 'a';
	}
	int ans = 0;
	f(n){
		//update freq
		++freq[num[i]];
		ff(26){
			//update cur
			++cur[num[i]][j];
			--cur[j][num[i]];
			if (freq[j] - cnt[num[i]][j]) ans = max(ans, cur[num[i]][j] - pre[num[i]][j]);
			else ans = max(ans, cur[num[i]][j] - pre2[num[i]][j]);

			if (freq[num[i]] - cnt[j][num[i]]) ans = max(ans, cur[j][num[i]] - pre[j][num[i]]);
			else ans = max(ans, cur[j][num[i]] - pre2[j][num[i]]);
			
			//only cur[j][num[i]] decreased; update pre?
			if (pre[j][num[i]] > cur[j][num[i]]){
				//depending on whether frequency decreased or stayed the same
				if (cnt[j][num[i]] == freq[num[i]]){
					pre[j][num[i]] = cur[j][num[i]];
				}
				else{ //cnt[j][num[i]] < freq[num[i]]
					//update both pre and pre2
					pre2[j][num[i]] = pre[j][num[i]];
					pre[j][num[i]] = cur[j][num[i]];
					cnt[j][num[i]] = freq[num[i]];
				}
			}
			//update pre2?
			else if (pre2[j][num[i]] > cur[j][num[i]]){
				//pre2 cant have same frequency as pre (has to be more)
				if (freq[num[i]] > cnt[j][num[i]]){
					pre2[j][num[i]] = cur[j][num[i]];
				}
			}
		}
	}
	out(ans);
	return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	320 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	1040 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	3 ms	456 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	102 ms	6248 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	78 ms	5224 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	101 ms	6304 KB	Output is correct
2	Correct	84 ms	5096 KB	Output is correct
3	Correct	84 ms	5480 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	105 ms	6248 KB	Output is correct
2	Correct	106 ms	6312 KB	Output is correct
3	Correct	101 ms	6248 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	101 ms	6248 KB	Output is correct
2	Correct	100 ms	6288 KB	Output is correct
3	Correct	101 ms	6248 KB	Output is correct

Submission #442046

Compilation message