Codechef - Colored Array

colorDP.cpp

//http://www.codechef.com/problems/COLARR/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

#define MAXN 1005

using namespace std;

int t, k, n, m;
int A[MAXN], B[MAXN][MAXN], C[MAXN][MAXN], haruhi[MAXN];
int memo[MAXN][MAXN];

int dp(int idx, int k) {
    if(k < 0) return -(1<<30);
    if(memo[idx][k] != -1) return memo[idx][k];
    if(idx == n) {
            if(k > 0) return haruhi[idx];
            else return B[idx][A[idx]];
    }
    return memo[idx][k] = max(dp(idx+1,k)+B[idx][A[idx]], dp(idx+1,k-1) + haruhi[idx]);
}

int main() {
    scanf("%d", &t);
while(t--) {
    memset(memo,(-1),sizeof(memo));
    scanf("%d %d %d", &n, &m, &k);
    for(int i = 1; i <= n; i++) scanf("%d", &A[i]);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &B[i][j]);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &C[i][j]);
    for(int i = 1; i <= n; i++)
        haruhi[i] = -(1<<30);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            haruhi[i] = max(haruhi[i], B[i][j] - C[i][j]);
    printf("%d\n", dp(1,k));
}
    return 0;
}