oj.uz

Submission #140139

# Submission time Handle Problem Language Result Execution time Memory
140139 2019-08-02T07:37:08 Z asifthegreat Difference (POI11_roz) C++14
50 / 100
 1000 ms 8508 KB 
#include <bits/stdc++.h>
#define pii pair<int,int>

#ifdef LOCAL
bool local = true;
#else
bool local = false;
#endif
using namespace std;


const int N = 1000005;
char s[N];

vector<int>occ[27];


int find_max(int n,const vector<int> &v){
	vector<int>pref(n+1);
	vector<int>pref_min(n+1);
	//for(int i = 1; i <= n;i++)cout << v[i] << " ";cout << endl;
	for(int i = 1; i <= n;i++){
		pref[i]=pref[i-1]+v[i];
		pref_min[i] = min(pref_min[i-1],pref[i]);
	}
	//for(int i = 1; i <= n;i++)cout << pref_min[i] << " ";cout << endl;//
	int last = -1,ans = 0;
	for(int i = 1; i <= n;i++){
		if(v[i] == -1)last = i;
		else if(last != -1){
			ans = max(ans,pref[i]-pref_min[last-1]);
		}
	}
	return ans;
}


int calc(const vector<int>&a, const vector<int>&b){
	if(a.empty() || b.empty())return 0;
	int size1 = a.size(),size2 = b.size();
	// for(auto i: a)cout << i << " ";cout << endl;
	// for(auto i: b)cout << i << " ";cout << endl;
 
	vector<int>v(size1+size2+5);
	int i = 0,j = 0,k = 1;
	while(1){
		if(k == size1+size2+1)break;
		if(i == size1){
			v[k++] = +1;j++;//continue; 
		}
		else if(j == size2){
			v[k++] = -1;i++;
			//continue;
		}
		else{
			if(a[i] < b[j]){
				v[k++] = -1;
				i++;
			}
			else{
				v[k++] = +1;
				j++;
			}
		}
		
		//cout << i << " " << j << " " << k << endl;
	}
	int n = size1+size2;
	//cout << n << endl;
	//for(int i =1; i <= n;i++)cout << v[i] << " ";cout << endl;
	/// v is an array with 1, -1 starting index = 1
	int ans = find_max(n,v);
	return ans;
}


int main(int argc, char const *argv[])
{
	int n;
	scanf("%d",&n);
	scanf("%s",s);
	for(int i = 0; i < n; i++){
		occ[(int)(s[i]-'a')].push_back(i);
	}
	int ans = 0;

	//ans = calc(occ[7],occ[5]);



	 for(int i = 0; i < 26;i++){
	 	for(int j = 0; j < 26;j++){
	// 		if(calc(occ[i],occ[j]) == 2){
	 //			cout << (char)('a'+i) <<" " << (char)('a'+j) << " " << i << " " << j <<  endl;
	// 		}
	 		if(i != j)ans = max(ans,calc(occ[i],occ[j]));
	 	}
	 }
	printf("%d\n", ans);

	return 0;
}

Compilation message

roz.cpp: In function 'int main(int, const char**)':
roz.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
roz.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s);
  ~~~~~^~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 256 KB Output isn't correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 1100 KB Output is correct
2 Correct 2 ms 400 KB Output is correct
3 Correct 9 ms 556 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 7988 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 8184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 8508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 7912 KB Time limit exceeded
2 Halted 0 ms 0 KB -