oj.uz

Submission #1002326

# Submission time Handle Problem Language Result Execution time Memory
1002326 2024-06-19T12:32:44 Z Sang Difference (POI11_roz) C++14
80 / 100
 811 ms 13336 KB 
// Created by Sang lớp 9
// Какого черта ты переводишь?
#include <bits/stdc++.h>
using namespace std;
#define Sang 1
// #define int long long
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define FOR(i, a, b) for(__typeof(b) i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for(__typeof(a) i = a, _b = b; i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MASK(i) (1ll<<(i))
#define BIT(t, i) (((t)>>(i))&1)
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;
const int MOD = 1e9+7;
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;
 
template <class T> bool minimize(T &a, T b) { if (a > b) { a = b; return true; } return false;}
 
template <class T> bool maximize(T &a, T b) { if (a < b) { a = b; return true; } return false;}
 
//   ****   ****
//  *     *     *
//  *    K.B    *
//    *       *
//       * *  
 
int n;
vi pos[30];
 
int cal(int x, int y){
    vi b;
    if (x == y) return 0;
    if (pos[x].size() == 0 || pos[y].size() == 0) return 0;
    int i = 0, j = 0;
    while (i < pos[x].size() && j < pos[y].size()){
        if (pos[x][i] < pos[y][j]){
            b.pb(-1);
            i++;
        } else {
            b.pb(1);
            j++;
        }
    }
    while (j < pos[y].size()){
        b.pb(1);
        j++;
    }
    while (i < pos[x].size()){
        b.pb(-1);
        i++;
    }
    vi pref(b.size(), 0);
    pref[0] = b[0];
    int last0 = -1, last1 = -1;
    if (b[0] == -1) last0 = 0;
    else last1 = 0;
    int cur = 0, mi = INF, ans = 0;
    FOR (i, 1, (int)b.size()-1){
        if (b[i] == -1) last0 = i;
        else last1 = i;
        pref[i] = pref[i-1] + b[i];
        while (cur < min(last0, last1)){
            minimize(mi, pref[cur]);
          ++cur;
        }
        maximize(ans, pref[i]-mi);
    }
    return ans;
    
}
 
int32_t main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0); cout.tie(0);
    #ifndef Sang
        freopen("DIFFER.inp", "r", stdin);
        freopen("DIFFER.out", "w", stdout);
    #endif
    cin >> n;
    FOR (i, 1, n){
        char c; cin >> c;
        pos[c-'a'].pb(i);
    }
    int ans = 0;
    FOR (i, 'a', 'z'){
        FOR (j, 'a', 'z'){
            maximize(ans, cal(i-'a', j-'a'));
        }
    }
    cout << ans;
 
    return 0;
}

Compilation message

roz.cpp: In function 'int cal(int, int)':
roz.cpp:43:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     while (i < pos[x].size() && j < pos[y].size()){
      |            ~~^~~~~~~~~~~~~~~
roz.cpp:43:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     while (i < pos[x].size() && j < pos[y].size()){
      |                                 ~~^~~~~~~~~~~~~~~
roz.cpp:52:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     while (j < pos[y].size()){
      |            ~~^~~~~~~~~~~~~~~
roz.cpp:56:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     while (i < pos[x].size()){
      |            ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory 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
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
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 452 KB Output is correct

Subtask #3
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 344 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 1116 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 811 ms 6920 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 391 ms 5892 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 625 ms 6660 KB Output is correct
2 Correct 473 ms 5320 KB Output is correct
3 Correct 163 ms 6336 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 7124 KB Output is correct
2 Correct 77 ms 12056 KB Output is correct
3 Correct 112 ms 7572 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 632 ms 6540 KB Output is correct
2 Correct 45 ms 13336 KB Output is correct
3 Correct 193 ms 7152 KB Output is correct