1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll dp[101][101][2][2][201];
const ll INF = 2137213722;
//dp[a][b][ktory wybrales][koniec ktorego ciagu][ograniczenie] -> dlugosc twojego ciagu
//0 - ciag rosnacy
//1 - ciag malejacy
int wy[600001];
void policz(vector<int> A, vector<int> B){
	
	int n = A.size();
	int m = B.size();
	A.push_back(0);
	B.push_back(0);
	reverse(A.begin(),A.end());
	reverse(B.begin(),B.end());
	/*cout<<"POLICZ dla sufiksow: \n";
	for (int x : A) cout<<x<<" ";
	cout<<"\n";
	for (int x : B) cout<<x<<" ";
	cout<<"\n";*/
	int i;
	for (i = 0; i <= n; i++){
		for (int j = 0; j <= m; j++){
			for (int k = 0; k <= n+m; k++){
				dp[i][j][0][0][k] = dp[i][j][0][1][k] = dp[i][j][1][0][k] = dp[i][j][1][1][k] = INF;
			}	
		}
	}
	for (int k = 0; k <= n+m; k++) dp[0][0][0][0][k] = dp[0][0][0][1][k] = 0;
	for (i = 0; i <= n; i++){
		for (int j = 0; j <= m; j++){
			for (int k = 0; k <= n+m; k++){
				for (int pop = 0; pop < 2; pop++){
					for (int akt = 0; akt < 2; akt++){
						if (akt == 0 && i == n) continue;
						if (akt == 1 && j == m) continue;
						//
						int nasz;
						if (pop == 0){
							nasz = A[i];
						}else{
							nasz = B[j];
						}	
						int a = 0;
						int b = 0;
						int ich;
						if (akt == 0){
							ich = A[i+1];
							a++;
						}else{
							ich = B[j+1];
							b++;
						}
						//
						int ktory = 1;
						if (nasz < ich) ktory = 0;
						if (dp[i][j][pop][ktory][k] < k){
						//	cout<<i<<" "<<j<<" "<<k<<" # "<<dp[i][j][pop][ktory][k]<<"\n";
						//	cout<<"Poprawia!\n";
							dp[i+a][j+b][akt][ktory][k] = min(dp[i+a][j+b][akt][ktory][k],dp[i][j][pop][ktory][k]+1);
							dp[i+a][j+b][akt][ktory^1][k] = 1;
						}
					}
				}
			}
		}
	}
	for (i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			for (int k = 0; k <= n+m; k++){
				//cout<<i<<" "<<j<<" "<<k<<" # "<<dp[i][j][0][0][k]<<"\n";
				if (dp[i][j][0][0][k] != INF || dp[i][j][1][0][k] != INF){
				//	cout<<i<<" "<<j<<" # "<<k<<"\n";
					wy[k]++;
					break;
				}
			}
		}
	}
//	exit(0);
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll i;
	int n,m;
	cin>>n>>m;
	int A[n+1];
	int B[m+1];
	for (i = 1; i <= n; i++) cin>>A[i];
	for (i = 1; i <= m; i++) cin>>B[i];
	vector<int> Avec;
	for (i = n; i >= 1; i--){
		Avec.push_back(A[i]);
		vector<int> Bvec;
		for (int j = m; j >= 1; j--){
			Bvec.push_back(B[j]);
			policz(Avec,Bvec);
		}
	}
	for (i = 1; i <= n+m; i++) cout<<wy[i]<<" ";
	cout<<"\n";
	return 0;
}