# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
250955 | 2020-07-19T16:37:13 Z | kingfran1907 | Savez (COCI15_savez) | C++14 | 109 ms | 17912 KB |
#include <bits/stdc++.h> using namespace std; typedef long long llint; const int maxn = 2e6+10; const llint base = 31337; const llint mod = 1e9+9; int n; map< llint, int > dp; llint pot[maxn]; vector< llint > v; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; pot[0] = 1; for (int i = 1; i < maxn; i++) pot[i] = pot[i - 1] * base, pot[i] %= mod; int sol = 0; while (n--) { string a; cin >> a; v.clear(); v.push_back(0); for (int i = 0; i < a.size(); i++) { llint tren = v.back() * base; tren %= mod; tren += a[i], tren %= mod; v.push_back(tren); } int tren = 0; for (int i = 1; i < v.size(); i++) { //printf("debug: %d/%d\n", i, v.size()); //printf("has: %lld == %lld\n", v[i], (v.back() - ((v[v.size() - 1 - i] * pot[i]) % mod) + mod) % mod); if (v[i] == (v.back() - ((v[v.size() - 1 - i] * pot[i]) % mod) + mod) % mod) tren = max(tren, dp[v[i]]); } tren++; sol = max(sol, tren); int &ac = dp[v.back()]; ac = max(ac, tren); } printf("%d", sol); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 16000 KB | Output is correct |
2 | Correct | 18 ms | 16000 KB | Output is correct |
3 | Correct | 22 ms | 16000 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 16000 KB | Output is correct |
2 | Correct | 17 ms | 16000 KB | Output is correct |
3 | Correct | 22 ms | 16128 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 109 ms | 17144 KB | Output is correct |
2 | Correct | 102 ms | 17144 KB | Output is correct |
3 | Correct | 107 ms | 17144 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 16128 KB | Output is correct |
2 | Correct | 50 ms | 17272 KB | Output is correct |
3 | Correct | 69 ms | 17272 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 17016 KB | Output is correct |
2 | Correct | 45 ms | 17016 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 43 ms | 17016 KB | Output is correct |
2 | Correct | 47 ms | 17036 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 45 ms | 17016 KB | Output is correct |
2 | Correct | 49 ms | 17016 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 17016 KB | Output is correct |
2 | Correct | 58 ms | 17016 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 58 ms | 17164 KB | Output is correct |
2 | Correct | 56 ms | 17144 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 69 ms | 17400 KB | Output is correct |
2 | Correct | 66 ms | 17320 KB | Output is correct |
3 | Correct | 109 ms | 17912 KB | Output is correct |