fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define f first
  5. #define s second
  6. const ll mod = 123456789;
  7. using namespace std;
  8. string s,x;
  9. int f[3005][3005][2],las[3005][3005];
  10. void solve(){
  11.     cin >> s >> x;
  12.     int n = s.size(),m = x.size();
  13.     s = " " + s;
  14.     x = " " + x;
  15.     for(int i = n;i >= 1;i--){
  16.         for(int j = m;j >= 1;j--){
  17.             if(s[i] == x[j]){
  18.                 if(s[i] == '0'){
  19.                     f[i][j][1] = max(f[i+1][j+1][0],f[i+1][j+1][1])+1;
  20.                     f[i][j][0] = f[i+1][j+1][0];
  21.                     las[i][j] = las[i+1][j+1];
  22.                 }
  23.                 else{
  24.                     las[i][j] = s[i]-'0';
  25.                     f[i][j][0] = max(f[i+1][j+1][1],f[i+1][j+1][0])+1;
  26.                     f[i][j][1] = f[i+1][j+1][1];
  27.                 }
  28.             }
  29.             else{
  30.                 if(f[i+1][j][0] > f[i][j+1][0]){
  31.                     f[i][j][0] = f[i+1][j][0];
  32.                     las[i][j] = las[i+1][j];
  33.                 }
  34.                 else if(f[i+1][j][0] < f[i][j+1][0]){
  35.                     f[i][j][0] = f[i][j+1][0];
  36.                     las[i][j] = las[i][j+1];
  37.                 }
  38.                 else{
  39.                     f[i][j][0] = f[i+1][j][0];
  40.                     if(las[i+1][j] > las[i][j+1]){
  41.                         las[i][j] = las[i+1][j];
  42.                     }
  43.                     else las[i][j] = las[i][j+1];
  44.                 }
  45.                 f[i][j][1] = max(f[i+1][j][1],f[i][j+1][1]);
  46.             }
  47.         }
  48.     }
  49.     int i = 1,j = 1;
  50.     bool ok = 0;
  51.     while(i <= n && j <= m){
  52.         if(ok){
  53.             if(f[i][j][0] >= f[i][j][1]){
  54.                 if(f[i][j][0] == 0)break;
  55.                 int u = las[i][j];
  56.                 cout << u;
  57.                 while(s[i]-'0' != u)i++;
  58.                 while(x[j]-'0' != u)j++;
  59.             }
  60.             else{
  61.                 cout << '0';
  62.                 while(s[i] != '0')i++;
  63.                 while(x[j] != '0')j++;
  64.             }
  65.         }
  66.         else{
  67.             if(f[i][j][0] == 0)break;
  68.             int u = las[i][j];
  69.             cout << u;
  70.             ok = 1;
  71.             while(s[i]-'0' != u)i++;
  72.             while(x[j]-'0' != u)j++;
  73.         }
  74.         i++;
  75.         j++;
  76.     }
  77.     if(ok == 0)cout << 0;
  78. }
  79. int main()
  80. {
  81.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  82.     if(fopen("NUMBER.INP","r")){
  83.         freopen("NUMBER.INP","r",stdin);
  84.         freopen("NUMBER.OUT","w",stdout);
  85.     }
  86.     int ts = 1;//cin >> ts;
  87.     while(ts--)solve();
  88.     return 0;
  89. }
  90.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/P2PKYG
language:
C++14 (gcc 8.3)
created:
1 day 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!