#include <bits/stdc++.h>
using namespace std;
vector< vector<int> > mat;
const int INF = 1e6;
int nwa(string a, string b , int i , int j){
if(mat[i][j] != -INF)
return mat[i][j];
else{
int val1;
if(i > 0 && j > 0 && a[i - 1] == b[j - 1])
val1 = nwa(a , b, i - 1, j - 1) + 1;
else
val1 = nwa(a , b, i - 1, j - 1) - 1;
int val2 = nwa(a , b, i - 1, j) - 2;
int val3 = nwa(a , b, i, j - 1) - 2;
return mat[i][j] = max({val1 , val2 , val3});
}
}
signed main() {
cin.tie(NULL);
ios_base::sync_with_stdio(NULL);
string a = "AAAC";
string b = "AGC";
int m = a.size();
int n = b.size();
mat.assign(m + 1, vector<int>(n + 1, -INF));
int cnt = 0;
for(int i = 0 ; i <= n; i++) mat[0][i] = cnt, cnt -= 2;
cnt = 0;
for(int i = 0 ; i <= m; i++) mat[i][0] = cnt, cnt -= 2;
int ans = nwa(a , b, m , n);
for(auto v : mat){
for(int i : v)
cout << i << "\t\t";
cout << endl;
}
cout << "RES:\n";
cout << ans << endl;
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gbWF0Owpjb25zdCBpbnQgSU5GID0gMWU2OwppbnQgbndhKHN0cmluZyBhLCBzdHJpbmcgYiAsIGludCBpICwgaW50IGopewoJaWYobWF0W2ldW2pdICE9IC1JTkYpIAoJCXJldHVybiBtYXRbaV1bal07CgllbHNlewoJCWludCB2YWwxOwoJCWlmKGkgPiAwICYmIGogPiAwICYmIGFbaSAtIDFdID09IGJbaiAtIDFdKQoJCQl2YWwxID0gbndhKGEgLCBiLCBpIC0gMSwgaiAtIDEpICsgMTsgCgkJZWxzZQoJCQl2YWwxID0gbndhKGEgLCBiLCBpIC0gMSwgaiAtIDEpIC0gMTsKCQlpbnQgdmFsMiA9IG53YShhICwgYiwgaSAtIDEsIGopIC0gMjsKCQlpbnQgdmFsMyA9IG53YShhICwgYiwgaSwgaiAtIDEpIC0gMjsKCQlyZXR1cm4gbWF0W2ldW2pdID0gbWF4KHt2YWwxICwgdmFsMiAsIHZhbDN9KTsKCX0KfQoKCnNpZ25lZCBtYWluKCkgewoJY2luLnRpZShOVUxMKTsKCWlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oTlVMTCk7CglzdHJpbmcgYSA9ICJBQUFDIjsKCXN0cmluZyBiID0gIkFHQyI7CglpbnQgbSA9IGEuc2l6ZSgpOwoJaW50IG4gPSBiLnNpemUoKTsKCW1hdC5hc3NpZ24obSArIDEsIHZlY3RvcjxpbnQ+KG4gKyAxLCAtSU5GKSk7CglpbnQgY250ID0gMDsKCWZvcihpbnQgaSA9IDAgOyBpIDw9IG47IGkrKykgbWF0WzBdW2ldID0gY250LCBjbnQgLT0gMjsgCgljbnQgPSAwOwoJZm9yKGludCBpID0gMCA7IGkgPD0gbTsgaSsrKSBtYXRbaV1bMF0gPSBjbnQsIGNudCAtPSAyOwoJaW50IGFucyA9IG53YShhICwgYiwgIG0gLCBuKTsKCWZvcihhdXRvIHYgOiBtYXQpewoJCWZvcihpbnQgaSA6IHYpCgkJCWNvdXQgPDwgaSA8PCAiXHRcdCI7CgkJY291dCA8PCBlbmRsOwoJfQoJY291dCA8PCAiUkVTOlxuIjsKCWNvdXQgPDwgYW5zIDw8IGVuZGw7CglyZXR1cm4gMDsKfQ==