Submission #855203

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
855203	2023-09-30T17:06:32 Z	trucmai	Difference (POI11_roz)	C++17	70 / 100	835 ms	26816 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 = -INF;
    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	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	1 ms	500 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	464 KB	Output is correct
2	Incorrect	0 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	66 ms	1716 KB	Output is correct
2	Incorrect	0 ms	348 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	822 ms	15944 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	411 ms	12304 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	835 ms	15820 KB	Output is correct
2	Correct	423 ms	13372 KB	Output is correct
3	Correct	198 ms	12364 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	818 ms	15588 KB	Output is correct
2	Correct	79 ms	26816 KB	Output is correct
3	Correct	139 ms	14360 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	831 ms	15688 KB	Output is correct
2	Correct	37 ms	26388 KB	Output is correct
3	Correct	238 ms	13484 KB	Output is correct