Submission #7518

#	Time	Username	Problem	Language	Result	Execution time	Memory
7518		jalmal	배열 탈출 (GA8_array)	C++98	100 / 100	828 ms	39936 KiB

array

#include <stdio.h>

int N, arr[2230][2230], tab[2230][2230];

void upd(int x, int y)
{
    int m = 2147483647;
    if(x > 1)
    {
        if(arr[y][x] < arr[y][x-1])
        {
            if(tab[y][x-1] < m) m = tab[y][x-1];
        }
        else
        {
            if(tab[y][x-1] + arr[y][x] - arr[y][x-1] + 1 < m) m = tab[y][x-1] + arr[y][x] - arr[y][x-1] + 1;
        }
    }
    if(y > 1)
    {
        if(arr[y][x] < arr[y-1][x])
        {
            if(tab[y-1][x] < m) m = tab[y-1][x];
        }
        else
        {
            if(tab[y-1][x] + arr[y][x] - arr[y-1][x] + 1 < m) m = tab[y-1][x] + arr[y][x] - arr[y-1][x] + 1;
        }
    }
    tab[y][x] = m;
}

int main()
{
    //freopen("input.txt", "r",  stdin);
    int i, j;

    scanf("%d", &N);
    for(i = 1; i <= N; i ++) for(j = 1; j <= N; j ++) scanf("%d", &arr[i][j]);

    for(i = 2; i <= N; i ++)
    {
        int x, y;
        for(x = 1, y = i; x <= i; x ++, y --)
        {
            upd(x, y);
        }
    }

    for(i = 2; i <= N; i ++)
    {
        int x, y;
        for(x = i, y = N; x <= N; x ++, y --)
        {
            upd(x, y);
        }
    }

    printf("%d", tab[N][N]);

    return 0;
}

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