Submission #7888

#	Time	Username	Problem	Language	Result	Execution time	Memory
7888		xhae	배열 탈출 (GA8_array)	C++14	100 / 100	692 ms	39816 KiB

array

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int arr[2222][2222], n;
int dp[2222][2222];

int getAns(int y, int x)
{
	int &ret = dp[y][x];
    if(ret != -1) return ret;
    
    if(y == n - 1 and x == n - 1) ret = 0;
    else
    {
    	ret = (1 << 30);
        if(y < n - 1) ret = min(ret, getAns(y + 1, x) + max(0, arr[y + 1][x] + 1 - arr[y][x]));
        if(x < n - 1) ret = min(ret, getAns(y, x + 1) + max(0, arr[y][x + 1] + 1 - arr[y][x]));
    }
    
    return ret;
}   

int main(void)
{
	scanf("%d", &n);
    for(int i = 0; i < n; i++)
    	for(int j = 0; j < n; j++)
        	scanf("%d", arr[i] + j);
    
    memset(dp, -1, sizeof(dp));
    printf("%d\n", getAns(0, 0));
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 11 / 11
• Subtask 3: 32 / 32
• Subtask 4: 51 / 51