fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define sti string
  4. #define bit(n,i) ((n>>i) &1)
  5. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. #define maxn 2000005
  7. #define fi first
  8. #define se second
  9. #define int long long
  10.  
  11.  
  12. using namespace std;
  13.  
  14. vector<int> dp;
  15. int n,A,B;
  16. int kmp[maxn];
  17. sti X,Y;
  18.  
  19.  
  20. void sub1(){
  21.    int cnt=0;
  22.    if(X != Y) cnt=max(A,B);
  23.    else cnt=A+B;
  24.    cout<<n*cnt;
  25. }
  26.  
  27. void sub2(){
  28.    int cntX=n-(int)X.size()+1;
  29.    int cntY=n-(int)Y.size()+1;
  30.    cout<<cntX*A+cntY*B;
  31. }
  32.  
  33. void sub3(){
  34.     dp.resize(n+1,0);
  35.    dp[0]=0;
  36.    for(int i=min(X.size(),Y.size());i<=n;i++){
  37.      if(i>=X.size()) dp[i]=max(dp[i-X.size()]+A,dp[i]);
  38.      if(i>=Y.size()) dp[i]=max(dp[i-Y.size()]+B,dp[i]);
  39.    }
  40.    cout<<dp[n];
  41. }
  42.  
  43. int getlap(string S, string T) {
  44.     int m = S.size();
  45.     int n = T.size();
  46.     string p = " " + S; // Pattern
  47.     string t = " " + T; // Text
  48.     vector<int> pi(m + 1, 0);
  49.  
  50.     // Bước 1: Xây dựng mảng tiền tố pi cho Pattern S
  51.     for (int i = 2, k = 0; i <= m; i++) {
  52.         while (k > 0 && p[i] != p[k + 1]) k = pi[k];
  53.         if (p[i] == p[k + 1]) k++;
  54.         pi[i] = k;
  55.     }
  56.  
  57.     // Bước 2: Khớp Pattern S vào Text T
  58.     int k = 0;
  59.     for (int i = 1; i <= n; i++) {
  60.         while (k > 0 && t[i] != p[k + 1]) k = pi[k];
  61.         if (t[i] == p[k + 1]) k++;
  62.  
  63.         // Nếu khớp hoàn toàn (k == m), ta cần lùi về để tìm overlap tiếp theo
  64.         // vì ta đang tìm hậu tố khớp tiền tố, không phải tìm xâu con đơn thuần.
  65.         if (k == m && i < n) k = pi[k];
  66.     }
  67.  
  68.     // Nếu là tự khớp (getlap(X, X)), k có thể bằng m (nguyên xâu).
  69.     // Ta chỉ lấy overlap thật sự nhỏ hơn độ dài xâu.
  70.     if (k == m) return pi[m];
  71.     return k;
  72. }
  73.  
  74. void sub5(){
  75.    int k=kmp[1]=0;
  76.    int m=X.size();
  77.    X=' '+X;
  78.    for(int i=2;i<=m;i++){
  79.        while(k>0 && X[i]!=X[k+1]) k=kmp[k];
  80.        kmp[i]=(X[i]==X[k+1] ? ++k : 0);
  81.    }
  82.    int lap=m-kmp[m];
  83.    int cnt=1+(n-m)/lap;
  84.    cout<<cnt*(A+B);
  85. }
  86.  
  87. void sub4() {
  88.     int L = X.size();
  89.  
  90.     // costXX: Đang có X, viết thêm bao nhiêu ký tự để lại có X
  91.     // getlap(X, X) tìm tiền tố X khớp hậu tố X
  92.     ll costXX = L - getlap(X, X);
  93.  
  94.     // costXY: Đang có X, viết thêm bao nhiêu ký tự để có Y
  95.     // Cần tìm tiền tố Y khớp hậu tố X -> dùng getlap(Y, X)
  96.     ll costXY = L - getlap(Y, X);
  97.  
  98.     // costYY: Đang có Y, viết thêm bao nhiêu ký tự để lại có Y
  99.     ll costYY = L - getlap(Y, Y);
  100.  
  101.     // costYX: Đang có Y, viết thêm bao nhiêu ký tự để có X
  102.     // Cần tìm tiền tố X khớp hậu tố Y -> dùng getlap(X, Y)
  103.     ll costYX = L - getlap(X, Y);
  104.  
  105.     // Khai báo DP: 2 hàng, n+1 cột
  106.     // Nếu n=10^7, vector<vector<ll>> tốn ~160MB.
  107.     // Nếu giới hạn 64MB, bạn cần dùng mảng 1 chiều hoặc kỹ thuật khác.
  108.     vector<ll> d0(n + 1, -1);
  109.     vector<ll> d1(n + 1, -1);
  110.  
  111.     if (L <= n) {
  112.         d0[L] = A;
  113.         d1[L] = B;
  114.     }
  115.  
  116.     ll ans = 0;
  117.     for (int i = L; i <= n; i++) {
  118.         // Trường hợp đang đứng ở cuối một xâu X
  119.         if (d0[i] != -1) {
  120.             ans = max(ans, d0[i]);
  121.             // Nối tiếp X: X -> X
  122.             if (i + costXX <= n)
  123.                 d0[i + costXX] = max(d0[i + costXX], d0[i] + A);
  124.             // Nối tiếp Y: X -> Y
  125.             if (i + costXY <= n)
  126.                 d1[i + costXY] = max(d1[i + costXY], d0[i] + B);
  127.         }
  128.         // Trường hợp đang đứng ở cuối một xâu Y
  129.         if (d1[i] != -1) {
  130.             ans = max(ans, d1[i]);
  131.             // Nối tiếp X: Y -> X
  132.             if (i + costYX <= n)
  133.                 d0[i + costYX] = max(d0[i + costYX], d1[i] + A);
  134.             // Nối tiếp Y: Y -> Y
  135.             if (i + costYY <= n)
  136.                 d1[i + costYY] = max(d1[i + costYY], d1[i] + B);
  137.         }
  138.     }
  139.     cout << ans;
  140. }
  141.  
  142. signed main()
  143. {
  144.     itachi
  145.     //freopen("STRING.inp","r",stdin);
  146.     //freopen("STRING.out","w",stdout);
  147.     cin>>n>>A>>B;
  148.     cin>>X>>Y;
  149.     bool subtask2=1;
  150.     bool subtask3=(X[0]=='a' && Y[0]=='c');
  151.     for(char c : X) if(c!='a') subtask2=0;
  152.     for(char c : Y) if(c!='a') subtask2=0;
  153.     for(int i=1;i<X.size();i++) if(X[i]!='b') subtask3=0;
  154.     for(int i=1;i<Y.size();i++) if(Y[i]!='d') subtask3=0;
  155.     if(X.size()==1 && Y.size()==1) sub1();
  156.     else if(subtask2) sub2();
  157.     else if(subtask3) sub3();
  158.     else if(X==Y) sub5();
  159.     else if(X.size()==Y.size()) sub4();
  160.     return 0;
  161. }
  162.  
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/b1H11i
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!