Submission #7473

#	Time	Username	Problem	Language	Result	Execution time	Memory
7473		gs14004	배열 탈출 (GA8_array)	C++98	100 / 100	596 ms	49916 KiB

array

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int a[2500][2500],n;
int dp[2500][2500];

int main(){
    memset(a,0x3f,sizeof(a));
    scanf("%d",&n);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int j=2; j<=n; j++){
        dp[1][j] = dp[1][j-1] + max(a[1][j]-a[1][j-1]+1,0);
    }
    for(int i=2; i<=n; i++){
        dp[i][1] = dp[i-1][1] + max(a[i][1]-a[i-1][1]+1,0);
        for(int j=2; j<=n; j++){
            dp[i][j] = min(dp[i-1][j] + max(a[i][j] - a[i-1][j]+1,0),dp[i][j-1] + max(a[i][j] - a[i][j-1]+1,0));
        }
    }
    printf("%d",dp[n][n]);
}

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