Submission #920129

#TimeUsernameProblemLanguageResultExecution timeMemory
920129TINSavez (COCI15_savez)C++17
0 / 120
17 ms1884 KiB
#include <bits/stdc++.h> using namespace std; #define FNAME "test" #define sz(s) (int) (s).size() typedef long long ll; const int base = 311; const ll M = 1e9 + 3; const int N = 505; const int len = 2e5 + 5; int n; string s[N]; ll p[len], hashS[N][len]; ll dp[N]; ll ans = 0; void Task() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout << fixed << setprecision(9); if (fopen(FNAME".inp","r")) { freopen(FNAME".inp","r",stdin); freopen(FNAME".out","w",stdout); } } void prepare() { p[0] = 1; for (int i = 1; i <= 2000000; i++) p[i] = (p[i - 1] * base) % M; } void update(int i, string s) { int lenS = sz(s); s = " " + s; hashS[i][0] = 0; for (int j = 1; j <= lenS; j++) hashS[i][j] = (hashS[i][j - 1] * base + s[j] + 1) % M; } ll getHash(int i, int l, int r) { return (hashS[i][r] - hashS[i][l - 1] * p[r - l + 1] + M * M) % M; } void Solve() { //Your Code prepare(); cin >> n; dp[0] = 0; for (int i = 1; i <= n; i++) { cin >> s[i]; update(i, s[i]); } for (int i = n; i >= 1; i--) { int best = 0; ll hashI = getHash(i, 1, sz(s[i])); ll hashHead, hashTail; for (int j = i + 1; j <= n; j++) { if (sz(s[j]) < sz(s[i])) continue; hashHead = getHash(j, 1, sz(s[i])); hashTail = getHash(j, sz(s[j]) - sz(s[i]) + 1, sz(s[j])); if (hashHead == hashI && hashI == hashTail) { if (dp[j] > dp[best]) { best = j; } } } dp[i] = dp[best] + 1; ans = max(ans, dp[i]); } cout << ans << '\n'; } int main() { Task(); Solve(); cerr << "\nTime run: " << 1000*clock()/CLOCKS_PER_SEC << "ms"; return 37^37; }

Compilation message (stderr)

savez.cpp: In function 'void Task()':
savez.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   freopen(FNAME".inp","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
savez.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   freopen(FNAME".out","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
savez.cpp: In function 'void prepare()':
savez.cpp:34:52: warning: iteration 200005 invokes undefined behavior [-Waggressive-loop-optimizations]
   34 |  for (int i = 1; i <= 2000000; i++) p[i] = (p[i - 1] * base) % M;
      |                                             ~~~~~~~^
savez.cpp:34:20: note: within this loop
   34 |  for (int i = 1; i <= 2000000; i++) p[i] = (p[i - 1] * base) % M;
      |                  ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...