oj.uz

Submission #855204

# Submission time Handle Problem Language Result Execution time Memory
855204 2023-09-30T17:07:07 Z trucmai Difference (POI11_roz) C++17
80 / 100
 843 ms 25376 KB 
//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; 
            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 = 0;
            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

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

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 604 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 1612 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 823 ms 15212 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 395 ms 11496 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 841 ms 15440 KB Output is correct
2 Correct 437 ms 12744 KB Output is correct
3 Correct 197 ms 11428 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 843 ms 14832 KB Output is correct
2 Correct 74 ms 25376 KB Output is correct
3 Correct 139 ms 13604 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 827 ms 15428 KB Output is correct
2 Correct 41 ms 25116 KB Output is correct
3 Correct 244 ms 12732 KB Output is correct