fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fi first
  4. #define se second
  5. #define all(x) (x).begin(), (x).end()
  6. #define MASK(i) (1LL << (i))
  7. #define BIT(i, n) (((n) >> (i)) & 1)
  8.  
  9. typedef long long ll;
  10. typedef pair<int, int> pii;
  11.  
  12. template <class X, class Y> bool mini(X& x, const Y& y) {
  13.     if(x > y){ x = y; return 1; }
  14.     return 0;
  15. }
  16.  
  17. template <class X, class Y> bool maxi(X& x, const Y& y) {
  18.     if(x < y){ x = y; return 1; }
  19.     return 0;
  20. }
  21.  
  22. const int N = 2e3 + 5;
  23.  
  24. string s;
  25. int n;
  26. bitset<N> pal[N];
  27. ll ans = 0;
  28.  
  29. void prepare()
  30. {
  31.     for(int i = 1; i <= n; ++i){
  32.         int l = i, r = i;
  33.         while(l >= 1 && r <= n && s[l] == s[r])
  34.             pal[l--][r++] = 1;
  35.  
  36.         l = i, r = i + 1;
  37.         while(l >= 1 && r <= n && s[l] == s[r])
  38.             pal[l--][r++] = 1;
  39.     }
  40. }
  41.  
  42. namespace sub2
  43. {
  44.     bool check()
  45.     {
  46.         return n <= 100;
  47.     }
  48.     void run()
  49.     {
  50.         for(int i1 = 1; i1 <= n; ++i1) for(int j1 = i1; j1 <= n; ++j1) if(pal[i1][j1]){
  51.             for(int i2 = j1 + 1; i2 <= n; ++i2) for(int j2 = i2; j2 <= n; ++j2) if(pal[i2][j2]){
  52.                 ++ans;
  53.             }
  54.         }
  55.  
  56.         cout << ans;
  57.     }
  58. }
  59.  
  60. namespace sub4
  61. {
  62.     int cnten[N], cntst[N];
  63.     void prepareSub4()
  64.     {
  65.         for(int i = 1; i <= n; ++i){
  66.             for(int len = 1; len <= i; ++len){
  67.                 cnten[i] += pal[i - len + 1][i];
  68.             }
  69.         }
  70.  
  71.         for(int i = n; i; --i){
  72.             for(int len = 1; i + len - 1 <= n; ++len){
  73.                 cntst[i] += pal[i][i + len - 1];
  74.             }
  75.         }
  76.     }
  77.     void run()
  78.     {
  79.         prepareSub4();
  80.         for(int j1 = 1; j1 <= n; ++j1){
  81.             for(int i2 = j1 + 1; i2 <= n; ++i2){
  82.                 ans += 1LL * cnten[j1] * cntst[i2];
  83.             }
  84.         }
  85.  
  86.         cout << ans;
  87.     }
  88. }
  89.  
  90. int main()
  91. {
  92.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  93.     #define file "PALINPAIRS"
  94.     if(fopen(file".inp", "r")){
  95.         freopen(file".inp", "r", stdin);
  96.         freopen(file".out", "w", stdout);
  97.     }
  98.  
  99.     cin >> s;
  100.     n = s.size(), s = '#' + s;
  101.  
  102.     prepare();
  103.  
  104. //    sub2::run(); cerr << "\n";
  105. //    sub4::run();
  106.  
  107.     if(sub2::check()) sub2::run();
  108.     else sub4::run();
  109.  
  110.     return 0;
  111. }
  112.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/VSZxk6
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!