oj.uz

Submission #701070

# Submission time Handle Problem Language Result Execution time Memory
701070 2023-02-20T02:24:25 Z hgmhc Difference (POI11_roz) C++17
100 / 100
 608 ms 4172 KB 
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define dbg(x) cerr << #x << ": " << x << '\n'
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

// 관찰 1. 사실 구간 내의 임의의 두 문자를 잡고 빈도수 차이를 구하는 것들을 모든 문자에 대해서 적용해서 나오는 최댓값으로 고려해도 된다.
// 그렇다면 26*26 경우에 대해서 전체 구간에 대해 문제를 풀면 된다.
// (a,b)로 잡았다면 a: +1, b:-1로 해서 최대 구간합을 구하면 된다.
const int N = 1e6+3;
int n, ans, b[N];
char a[N];

int main() {
    scanf("%d", &n);
    scanf("%s", a+1);
    rep(c,'a','z') rep(d,c+1,'z') {
        int m = -1;
        rep(i,1,n) {
            if (a[i] == c) {
                b[++m] = +1;
                for (; i < n and a[i+1] != d; ++i) if (a[i+1] == c) b[m]++;
            }
            else if (a[i] == d) {
                b[++m] = -1;
                for (; i < n and a[i+1] != c; ++i) if (a[i+1] == d) b[m]--;
            }
        }
        int s = -1e9, t = -1e9;
        if (m > 0) Mup(ans,max(b[0]-1,-b[0]-1));
        rep(i,1,m) {
            s = max(s+b[i],b[i-1]+b[i]);
            t = max(t-b[i],-b[i-1]-b[i]);
            ans = max({ans,b[i]-1,-b[i]-1,s,t});
        }
    }
    printf("%d", ans);
}

Compilation message

roz.cpp: In function 'int main()':
roz.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
roz.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%s", a+1);
      |     ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 500 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 7 ms 320 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 608 ms 2452 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 439 ms 2104 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 2396 KB Output is correct
2 Correct 450 ms 2000 KB Output is correct
3 Correct 281 ms 1976 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 2404 KB Output is correct
2 Correct 466 ms 3560 KB Output is correct
3 Correct 283 ms 2240 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 2396 KB Output is correct
2 Correct 438 ms 4172 KB Output is correct
3 Correct 312 ms 2260 KB Output is correct