ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1029. Министерство

WA test #6
Послано idemura 7 июл 2013 06:25
My code: What's wrong???

#include <algorithm>
#include <vector>
#include <utility>
#include <stdio.h>

#define ARRAY_SIZEOF(a) (sizeof(a) / sizeof(a[0]))
#define INF 0x7fffffff

using namespace std;

typedef long long int lli;

int M, N;
int C[100][500];
int T[101][500];
int m1[500];
int m2[500];
int path[500*500];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
#endif
    int i, j, k;

    scanf("%d%d", &M, &N);
    for (i = 0; i < M; i++) {
        for (j = 0; j < N; j++) {
            scanf("%d", &C[i][j]);
            C[i][j]++;
            T[i+1][j] = INF;
        }
    }

    for (i = 1; i <= M; i++) {
        m1[0] = T[i-1][0] + C[i-1][0];
        for (j = 1; j < N; j++) {
            m1[j] = min(m1[j-1], T[i-1][j]) + C[i-1][j];
        }
        m2[N-1] = T[i-1][N-1] + C[i-1][N-1];
        for (j = N-1; j-- > 0; ) {
            m2[j] = min(m2[j+1], T[i-1][j]) + C[i-1][j];
        }
        for (j = 0; j < N; j++) {
            T[i][j] = min(m1[j], m2[j]);
        }
    }

    int jmin = 0;
    for (j = 1; j < N; j++) {
        if (T[M][j] < T[M][jmin]) {
            jmin = j;
        }
    }
    i = M;
    j = jmin;
    k = 0;
    do {
        path[k++] = j + 1;
        int m = T[i-1][j];
        jmin = j;
        if (j-1 >= 0 && T[i][j-1] < m) {
            jmin = j-1;
            m = T[i][jmin];
        }
        if (j+1 <  N && T[i][j+1] < m) {
            jmin = j+1;
            m = T[i][jmin];
        }
        if (m == T[i-1][j])
            i--;
        else
            j = jmin;
    } while (i);

    for (i = 0; i < k; i++) {
        printf("%d ", path[k-1-i]);
    }
    printf("\n");

    return 0;
}