oj.uz

답안 #855206

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
855206 2023-09-30T17:08:32 Z trucmai Difference (POI11_roz) C++17
100 / 100
 856 ms 26140 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{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

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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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

# 결과 실행 시간 메모리 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

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 1828 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 5 ms 604 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 854 ms 15364 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 411 ms 11812 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 856 ms 15240 KB Output is correct
2 Correct 446 ms 12516 KB Output is correct
3 Correct 205 ms 11392 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 854 ms 14852 KB Output is correct
2 Correct 75 ms 24780 KB Output is correct
3 Correct 141 ms 13788 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 849 ms 15044 KB Output is correct
2 Correct 42 ms 26140 KB Output is correct
3 Correct 246 ms 12888 KB Output is correct