oj.uz

답안 #47335

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
47335 2018-05-01T05:26:36 Z mirbek01 회문 (APIO14_palindrome) C++17
0 / 100
 1000 ms 2108 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 2;

string s;
int n;
long long ans, h[N], has[N], pw[N], p[N], pr = 997, mod = 1e9 + 7;
map < pair <int, pair <int, int> > , int> mp;

int get(int l, int r){
      long long hs = h[r] - h[l - 1];
      hs *= pw[N - l];
      return hs;
}

int Get(int l, int r){
      long long hs = (has[r] - has[l - 1] + mod) % mod;
      hs = (hs * p[N - l]) % mod;
      return hs;
}

bool ispal(int l, int r){
      return get(l, r) == get(n - r + 1, n - l + 1) && Get(l, r) == Get(n - r + 1, n - l + 1);
}

int main(){
      pw[0] = pr;
      p[0] = pr;

      for(int i = 1; i < N; i ++){
            pw[i] = pw[i - 1] * pr;
            p[i] = (p[i - 1] * pr) % mod;
      }

      cin >> s;
      n = s.size();
      s = ' ' + s;

      for(int i = 1; i <= n; i ++){
            h[i] = h[i - 1] + s[i] * pw[i];
            has[i] = (has[i - 1] + s[i] * p[i]) % mod;
      }

      for(int i = 1; i <= n; i ++){
            for(int j = i; j <= n; j ++){
                  if(ispal(i, j)){
                        mp[{j - i + 1, {get(i, j), Get(i, j)}}] ++;
                  }
            }
      }

      for(auto i : mp){
            long long cur = i.first.first * i.second;
            ans = max(ans, cur);
      }

      cout << ans << endl;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Incorrect 2 ms 576 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1070 ms 1432 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 1720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 2108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -