Submission #555501

#TimeUsernameProblemLanguageResultExecution timeMemory
555501tht2005Copy and Paste 3 (JOI22_copypaste3)C++17
1 / 100
3071 ms22872 KiB
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; void ckmin(LL& a, LL b) { if(a > b) { a = b; } } const int N = 2503; const int B = 311; const LL INF = 0x3f3f3f3f3f3f3f3f; int n, a, b, c, g[N][N]; char s[N]; LL res, f[N][N], dp[N]; ULL h[N], pw[N]; ULL get(int l, int r) { return h[r] - h[l] * pw[r - l]; } int main() { scanf("%d %s %d %d %d", &n, s, &a, &b, &c); h[0] = 0; pw[0] = 1; for(int i = 0; i < n; ++i) { h[i + 1] = h[i] * B + s[i]; pw[i + 1] = pw[i] * B; } for(int i = n; i--; ) { for(int j = i + 1; j <= n; ++j) { g[i][j] = (j + j - i <= n && get(i, j) == get(j, j + j - i)) ? g[j][j + j - i] + 1 : 1; } } for(int i = 0; i < n; ++i) { f[i][i + 1] = a + b; } for(int L = 2; L <= n; ++L) { for(int i = 0, j = L; j <= n; ++i, ++j) { f[i][j] = (LL)a * L; for(int l = i; l < j; ++l) { for(int r = l + 1; r <= j; ++r) { int cnt = min(g[l][r], (j - l) / (r - l)); int r2 = l + (r - l) * cnt; f[i][j] = min(f[i][j], f[l][r] + (LL)a * (l - i) + min((LL)c * cnt, (LL)a * (r2 - l)) + (LL)a * (j - r2)); } } f[i][j] += b; } } res = (LL)a * n; for(int i = 0; i < n; ++i) { for(int j = i + 1; j <= n; ++j) { dp[0] = 0; for(int k = 1; k <= n; ++k) { dp[k] = INF; } for(int k = 0; k < n; ++k) { ckmin(dp[k + 1], dp[k] + a); if(k + j - i <= n && get(i, j) == get(k, k + j - i)) { ckmin(dp[k + j - i], dp[k] + c); } } res = min(res, f[i][j] + dp[n]); } } printf("%lld", res); return 0; }

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d %s %d %d %d", &n, s, &a, &b, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...