Submission #1060888

#TimeUsernameProblemLanguageResultExecution timeMemory
1060888sleepntsheepCopy and Paste 3 (JOI22_copypaste3)C++17
25 / 100
890 ms158424 KiB
#pragma GCC optimize("O3,unroll-loops") #include <iostream> #include <map> #include <cstring> #include <vector> #include <algorithm> using namespace std; using ll = long long; template <typename T> using ve = vector<T>; const int N = 1001; const ll B = 137, M = 1000000007; int n; ll dp[N][N], a, b, c; char s[N]; ll hs[N], bp[N], ibp[N]; ll bpow(ll a, ll b) { if (!b) return 1; ll r { bpow(a, b / 2) }; if (b & 1) return r * r % M * a % M; return r * r % M; } void do_hash() { bp[0] = ibp[0] = 1; for (int i = 1; i <= n; ++i) bp[i] = bp[i - 1] * B % M, ibp[i] = bpow(bp[i], M - 2); for (int i = 1; i <= n; ++i) hs[i] = bp[i] * s[i] % M, hs[i] = (hs[i] + hs[i - 1]) % M; } ll get_hash(int l, int r) { return ibp[l] * (hs[r] - hs[l - 1] + M) % M; } map<ll, ve<int>> oo, op[N]; void init() { do_hash(); memset(dp, 63, sizeof dp); for (int i = 1; i <= n; ++i) { dp[i][i] = a; for (int j = i; j <= n; ++j) oo[get_hash(i, j)].push_back(i); } for (int i = 1; i <= n; ++i) { for (int j = i; j <= n; ++j) { ll x = get_hash(i, j); auto &v = oo[x]; auto it = lower_bound(v.begin(), v.end(), i); while (it != v.end()) { op[i][x].push_back(*it); it = lower_bound(v.begin(), v.end(), *it + j - i + 1); } } } } int main() { scanf("%d%s%lld%lld%lld", &n, s + 1, &a, &b, &c); init(); for (int l = 1; l <= n; ++l) { for (int i = 1, j = l; j <= n; ++i, ++j) { if (i < j) dp[i][j] = min(dp[i][j], dp[i + 1][j] + a); if (j > i) dp[i][j] = min(dp[i][j], dp[i][j - 1] + a); auto x = get_hash(i, j); auto &oc = op[i][x]; auto it = lower_bound(oc.begin(), oc.end(), i); int cnt = 1; for (; it != oc.end(); ++it, ++cnt) { int jj = *it + l - 1; dp[i][jj] = min(dp[i][jj], dp[i][j] + b + cnt * c + (jj - i + 1 - cnt * l) * a); } } } printf("%lld", dp[1][n]); }

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     scanf("%d%s%lld%lld%lld", &n, s + 1, &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...