Submission #701070

#	Time	Username	Problem	Language	Result	Execution time	Memory
701070		hgmhc	Difference (POI11_roz)	C++17	100 / 100	608 ms	4172 KiB

roz

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10