oj.uz

Submission #885115

# Submission time Handle Problem Language Result Execution time Memory
885115 2023-12-09T03:01:03 Z catlover Difference (POI11_roz) C++14
100 / 100
 573 ms 13192 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fileio(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)
 
const int maxn = 1e6+5, inf = 1e9;
int n;
vector<int> idx[26];
string s;
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    fileio("diff");
    // freopen("debug.txt", "w", stderr);
 
    cin >> n >> s;
    s = "%" + s;
    for (int i = 1; i <= n; i++) {
        idx[s[i] - 'a'].push_back(i);
    }
 
    int res = 0;
    for (int x = 0; x < 26; x++) {
        for (int y = 0; y < 26; y++) {
            if (idx[x].empty() || idx[y].empty()) continue;
            if (x == y) continue;
 
            vector<int> a {0};
            int j = 0;
            for (int i: idx[x]) {
                while (j < idx[y].size() && idx[y][j] < i) {
                    a.push_back(-1);
                    j++;
                }
                a.push_back(1);
            }
            while (j < idx[y].size()) {
                a.push_back(-1);
                j++;
            }
 
            // kjjfdlkfjdf
            int ans = 0, mini = inf, last = 0;
            vector<int> pfs (a.size(), 0);
            for (int i = 1; i < a.size(); i++) {
                pfs[i] = pfs[i-1] + a[i];
                if (i > 1 && a[i] != a[i-1]) {
                    for (int j = last; j < i-1; j++) {
                        mini = min(mini, pfs[j]);
                    }
                    last = i-1;
                }
                ans = max(ans, pfs[i] - mini);
            }
            res = max(res, ans);
            // cerr << x << " " << y << "\n";
        }
    }
    cout << res;
}

Compilation message

roz.cpp: In function 'int32_t main()':
roz.cpp:32:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |                 while (j < idx[y].size() && idx[y][j] < i) {
      |                        ~~^~~~~~~~~~~~~~~
roz.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             while (j < idx[y].size()) {
      |                    ~~^~~~~~~~~~~~~~~
roz.cpp:46:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             for (int i = 1; i < a.size(); i++) {
      |                             ~~^~~~~~~~~~
roz.cpp:4:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define fileio(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
roz.cpp:14:5: note: in expansion of macro 'fileio'
   14 |     fileio("diff");
      |     ^~~~~~
roz.cpp:4:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define fileio(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
roz.cpp:14:5: note: in expansion of macro 'fileio'
   14 |     fileio("diff");
      |     ^~~~~~

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 360 KB Output is correct
4 Correct 0 ms 344 KB Output is correct

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 348 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 344 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 348 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 6 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 8228 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 279 ms 6360 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 7972 KB Output is correct
2 Correct 421 ms 6884 KB Output is correct
3 Correct 145 ms 7320 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 8224 KB Output is correct
2 Correct 63 ms 12104 KB Output is correct
3 Correct 113 ms 8308 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 7968 KB Output is correct
2 Correct 35 ms 13192 KB Output is correct
3 Correct 188 ms 7984 KB Output is correct