Submission #738484

#	Time	Username	Problem	Language	Result	Execution time	Memory
738484		Abrar_Al_Samit	Palindromes (APIO14_palindrome)	C++17	47 / 100	987 ms	82604 KiB

palindrome

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define mod 1000000007
    #define v 2
    ll h[10005];
    bool ispalindrome[10005][10005];
    ll mod_inverse[10005];
    char str[10005];
    ll modpow(ll x,ll n)
    {
    	ll res=1;
    	while(n)
    	{
    		if(n&1) res = res*x%mod;
    		x = x*x%mod;
    		n >>= 1;
    	}
    	return res;
    }
    ll calc(int l,int r)
    {
    	if(l==1) return h[r];
    	ll d = (h[r]-h[l-1]+mod)%mod;
    	return d*mod_inverse[l]%mod;
    }
    int main()
    {
    	scanf("%s",str);
    	int n=strlen(str);
    	for(int i=n;i>=1;i--) str[i] = str[i-1];
    	for(int i=1;i<=n;i++) ispalindrome[i][i]=true;
    	for(int i=1;i<n;i++) ispalindrome[i][i+1] = str[i]==str[i+1];
    	for(int len=3;len<=n;len++)
    	{
    		for(int i=1;i+len-1<=n;i++)
    		{
    			ispalindrome[i][i+len-1] = ispalindrome[i+1][i+len-2] & (str[i] == str[i+len-1]);
    		}
    	}
    	ll cur = 1LL;
    	for(int i=1;i<=10005;i++)
    	{
    		mod_inverse[i] = modpow(cur,mod-2); cur=cur*v%mod;
    	}
    	cur = 1LL;
    	for(int i=1;i<=n;i++)
    	{
    		h[i] = (h[i-1]+cur*(str[i]-'a')%mod)%mod;
    		cur = cur*v%mod;
    	}
    	int res=0;
    	for(int i=1;i<=n;i++)
    	{
    		map<ll,int>ch; int maxvalue=0;
    		for(int j=1;j+i-1<=n;j++)
    		{
    			if(ispalindrome[j][j+i-1]) maxvalue = max(maxvalue,++ch[calc(j,j+i-1)]);
    		}
    		res = max(res,maxvalue*i);
    	}
    	printf("%d%c",res,10);

        cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    }

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:29:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |      scanf("%s",str);
      |      ~~~~~^~~~~~~~~~
palindrome.cpp:44:22: warning: iteration 10004 invokes undefined behavior [-Waggressive-loop-optimizations]
   44 |       mod_inverse[i] = modpow(cur,mod-2); cur=cur*v%mod;
      |       ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
palindrome.cpp:42:19: note: within this loop
   42 |      for(int i=1;i<=10005;i++)
      |                  ~^~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27