oj.uz

Submission #40899

# Submission time Handle Problem Language Result Execution time Memory
40899 2018-02-09T20:42:10 Z MatheusLealV Difference (POI11_roz) C++14
60 / 100
 110 ms 32768 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 1 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 736 KB Output is correct
2 Correct 2 ms 740 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1020 KB Output is correct
2 Correct 1 ms 1020 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 2956 KB Output is correct
2 Correct 2 ms 2956 KB Output is correct
3 Correct 12 ms 2956 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 75 ms 32768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 32768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 32768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 89 ms 32768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -