oj.uz

Submission #269734

# Submission time Handle Problem Language Result Execution time Memory
269734 2020-08-17T09:25:31 Z mayhoubsaleh Savez (COCI15_savez) C++14
120 / 120
 134 ms 33644 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define left 2*i+1
#define righ 2*i+2
#define mid (l+r)/2
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);


using namespace std;
const ll maxn=1e5+100;
const ll inf=1e9+10;
const ll mod=1e9+7;
const ll base=27;

ll n;vector<string>s;
unordered_map<ll,ll>dp;
ll ans;
int main()
{
    IOS
    cin>>n;
    s.resize(n);
    for(ll i=0;i<n;i++)cin>>s[i];

    for(ll i=0;i<n;i++){
        ll curans=1;
        ll pre=0,suf=0,b=1;
        for(ll l=0,r=s[i].size()-1;l<s[i].size();l++,r--){
            pre=pre*base%mod;
            pre=(pre+(s[i][l]-'A'+1))%mod;
            suf=(suf+(s[i][r]-'A'+1)*b%mod)%mod;
            b=b*base%mod;
            if(pre==suf){
                curans=max(curans,dp[pre]+1);
            }
        }
        dp[pre]=max(dp[pre],curans);
        ans=max(ans,curans);
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message

savez.cpp: In function 'int main()':
savez.cpp:29:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(ll l=0,r=s[i].size()-1;l<s[i].size();l++,r--){
      |                                    ~^~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2432 KB Output is correct
2 Correct 41 ms 2456 KB Output is correct
3 Correct 34 ms 2560 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 25 ms 2424 KB Output is correct
3 Correct 30 ms 2560 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2816 KB Output is correct
2 Correct 30 ms 2688 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3200 KB Output is correct
2 Correct 25 ms 3176 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4096 KB Output is correct
2 Correct 30 ms 4136 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4736 KB Output is correct
2 Correct 32 ms 4864 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 9088 KB Output is correct
2 Correct 53 ms 9088 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 14308 KB Output is correct
2 Correct 74 ms 14328 KB Output is correct
3 Correct 134 ms 33644 KB Output is correct