Submission #40899

#	Time	Username	Problem	Language	Result	Execution time	Memory
40899		MatheusLealV	Difference (POI11_roz)	C++14	60 / 100	110 ms	32768 KiB

roz

#include <bits/stdc++.h>
#define N 1000010
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, tot[30], resp, pref[N], suf[N], sum[N];

string s;

vector<pii> pos[30][2];

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n;

	cin>>s;

	for(int i = 0; i < s.size(); i++)
	{
		pos[ s[i] - 'a' ][0].push_back(pii(i, 1));

		pos[ s[i] - 'a' ][1].push_back(pii(i, -1));

		tot[ s[i] - 'a' ] ++;
	}

	for(int a = 0; a < 26; a++)
	{
		for(int b = 0; b < 26; b++)
		{
			if(a == b) continue;

			vector<pii> v(pos[a][0].size() + pos[b][1].size());

			int ans = 0, best = 0, q1 = 0, q2 = 0;

			merge(pos[a][0].begin(), pos[a][0].end(), pos[b][1].begin(), pos[b][1].end(), v.begin());

			for(int p = 0; p < v.size(); p ++) sum[p] = (p > 0 ? sum[p - 1] : 0) + v[p].s;

			for(int p = 0; p < v.size(); p ++)
			{
				if(!p) pref[p] = 0;

				else pref[p] = min(pref[p - 1], sum[p - 1]);
			}

			for(int p = v.size(); p >= 0; p--)
			{
				if(p == v.size() - 1) suf[p] = sum[p];

				else suf[p] = max(suf[p + 1], sum[p]);
			}

			for(int p = 0; p < v.size(); p++)

				if(v[p].s == -1) ans = max(ans, suf[p] - pref[p]);


			resp = max(ans, resp);
		}
	}

	cout<<resp<<"\n";
}

Compilation message (stderr)

roz.cpp: In function 'int main()':
roz.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++)
                   ^
roz.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int p = 0; p < v.size(); p ++) sum[p] = (p > 0 ? sum[p - 1] : 0) + v[p].s;
                     ^
roz.cpp:45:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int p = 0; p < v.size(); p ++)
                     ^
roz.cpp:54:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(p == v.size() - 1) suf[p] = sum[p];
          ^
roz.cpp:59:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int p = 0; p < v.size(); p++)
                     ^
roz.cpp:39:17: warning: unused variable 'best' [-Wunused-variable]
    int ans = 0, best = 0, q1 = 0, q2 = 0;
                 ^
roz.cpp:39:27: warning: unused variable 'q1' [-Wunused-variable]
    int ans = 0, best = 0, q1 = 0, q2 = 0;
                           ^
roz.cpp:39:35: warning: unused variable 'q2' [-Wunused-variable]
    int ans = 0, best = 0, q1 = 0, q2 = 0;
                                   ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10