# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
338720 | FlashGamezzz | Savez (COCI15_savez) | C++17 | 148 ms | 65540 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <utility>
#include <vector>
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int n, p = 31, m = 1000000009;
vector< vector<long long> > ph, sh;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n;
long long pow = 1, h = 0;
vector<long long> temp;
for (int i = 0; i < n; i++){
string a; cin >> a;
pow = 1, h = 0; temp.clear();
for (int j = 0; j < a.length(); j++) {
h += (a[j]-'A'+1)*pow; h %= m;
temp.push_back(h); pow *= p; pow %= m;
}
ph.push_back(temp); h = 0; temp.clear();
for (int j = a.length()-1; j >= 0; j--) {
h *= p; h %= m; h += (a[j]-'A'+1); h %= m;
temp.push_back(h);
}
sh.push_back(temp);
}
unordered_map<long long, int> subsq;
int ans = 0;
for (int i = 0; i < n; i++){
int mv = 0;
for (int j = 0; j < ph[i].size(); j++){
if (ph[i][j] == sh[i][j]){
unordered_map<long long, int>::iterator it = subsq.find(ph[i][j]);
if (it != subsq.end()){
mv = max(mv, it->second);
}
}
}
subsq[ph[i][ph[i].size()-1]] = mv+1; ans = max(ans, mv+1);
}
cout << ans << endl;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |