Submission #140139

#	Time	Username	Problem	Language	Result	Execution time	Memory
140139		asifthegreat	Difference (POI11_roz)	C++14	50 / 100	1086 ms	8508 KiB

roz

#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 (stderr)

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
• 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