Submission #855206

#	Time	Username	Problem	Language	Result	Execution time	Memory
855206		trucmai	Difference (POI11_roz)	C++17	100 / 100	856 ms	26140 KiB

roz

//i_love_aisukiuwu
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(a) (a).begin(), (a).end()
#define vi vector<ll>
#define pi pair<ll,ll>
#define fi first
#define se second
#define gcd __gcd
#define mset(a,v) memset(a, v, sizeof(a))
#define endl '\n'

const int N = 1e6 + 6,LOG = 27,MOD = 1e9 + 7;
const ll INF = 1e18;

void process();

signed main(){
    cin.tie(0); cout.tie(0); 
    ios_base::sync_with_stdio(false);
    process(); 
    cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
ll n; string s;
vector<ll>pos[30];
void process(){ 
    //O..O(k)
    cin>>n>>s; s = " " + s;
    for(ll i = 1;i <= n;++i)
        pos[s[i] - 'a'].emplace_back(i);
    ll res = 0;
    for(ll x = 0;x < 26;++x){
        for(ll y = 0;y < 26;++y){
            if(x == y || pos[x].empty() || pos[y].empty()) continue; 
            //transforming string to 0 - 1 sequnece
            ll _ptr = 0;
            vector<ll>v{0}; 
            for(ll &idx : pos[x]){
                while(_ptr < pos[y].size() && pos[y][_ptr] < idx){
                    ++_ptr; 
                    v.push_back(-1);
                }
                v.push_back(1); 
            }
            while(_ptr < pos[y].size()){
                ++_ptr; 
                v.push_back(-1);
            }
            //calculating the maximum
            ll tmp = 0,last = 0,min_idx = INF;
            vector<ll>pf(v.size(),0);
            for(ll i = 1;i < v.size();++i){
                pf[i] = pf[i-1] + v[i]; 
                if(i > 1 && v[i] != v[i-1]){
                    for(ll j = last;j < i - 1;++j) min_idx = min(min_idx,pf[j]);
                    last = i - 1;
                }
                tmp = max(tmp,pf[i] - min_idx);
            }
            res = max(res,tmp);
        }
    }
    cout<<res<<endl;
}

Compilation message (stderr)

roz.cpp: In function 'void process()':
roz.cpp:41:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |                 while(_ptr < pos[y].size() && pos[y][_ptr] < idx){
      |                       ~~~~~^~~~~~~~~~~~~~~
roz.cpp:47:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             while(_ptr < pos[y].size()){
      |                   ~~~~~^~~~~~~~~~~~~~~
roz.cpp:54:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for(ll i = 1;i < v.size();++i){
      |                          ~~^~~~~~~~~~

• 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: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10