#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 = "ACTGATTCA";
string b = "ACGCATCA";
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+ID4gbWF0Owpjb25zdCBpbnQgSU5GID0gMWU2OwppbnQgbndhKHN0cmluZyBhLCBzdHJpbmcgYiAsIGludCBpICwgaW50IGopewoJaWYobWF0W2ldW2pdICE9IC1JTkYpIAoJCXJldHVybiBtYXRbaV1bal07CgllbHNlewoJCWludCB2YWwxOwoJCWlmKGkgPiAwICYmIGogPiAwICYmIGFbaSAtIDFdID09IGJbaiAtIDFdKQoJCQl2YWwxID0gbndhKGEgLCBiLCBpIC0gMSwgaiAtIDEpICsgMTsgCgkJZWxzZQoJCQl2YWwxID0gbndhKGEgLCBiLCBpIC0gMSwgaiAtIDEpIC0gMTsKCQlpbnQgdmFsMiA9IG53YShhICwgYiwgaSAtIDEsIGopIC0gMjsKCQlpbnQgdmFsMyA9IG53YShhICwgYiwgaSwgaiAtIDEpIC0gMjsKCQlyZXR1cm4gbWF0W2ldW2pdID0gbWF4KHt2YWwxICwgdmFsMiAsIHZhbDN9KTsKCX0KfQoKCnNpZ25lZCBtYWluKCkgewoJY2luLnRpZShOVUxMKTsKCWlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oTlVMTCk7CglzdHJpbmcgYSA9ICJBQ1RHQVRUQ0EiOwoJc3RyaW5nIGIgPSAiQUNHQ0FUQ0EiOwoJaW50IG0gPSBhLnNpemUoKTsKCWludCBuID0gYi5zaXplKCk7CgltYXQuYXNzaWduKG0gKyAxLCB2ZWN0b3I8aW50PihuICsgMSwgLUlORikpOwoJaW50IGNudCA9IDA7Cglmb3IoaW50IGkgPSAwIDsgaSA8PSBuOyBpKyspIG1hdFswXVtpXSA9IGNudCwgY250IC09IDI7IAoJY250ID0gMDsKCWZvcihpbnQgaSA9IDAgOyBpIDw9IG07IGkrKykgbWF0W2ldWzBdID0gY250LCBjbnQgLT0gMjsKCWludCBhbnMgPSBud2EoYSAsIGIsICBtICwgbik7Cglmb3IoYXV0byB2IDogbWF0KXsKCQlmb3IoaW50IGkgOiB2KQoJCQljb3V0IDw8IGkgPDwgIlx0XHQiOwoJCWNvdXQgPDwgZW5kbDsKCX0KCWNvdXQgPDwgIlJFUzpcbiI7Cgljb3V0IDw8IGFucyA8PCBlbmRsOwoJcmV0dXJuIDA7Cn0=