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

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

Please somebody give mesome test I got WA3! Thank you
Послано Husan 31 июл 2008 11:14
This is my prog

#include<iostream>
using namespace std;


int a[102][502]={{0}},path[102][502]={{0}};
int n,m;

void matr(int i)
{
    int j;
    int p1[500]={0},p2[500]={0};
    int pre1[500],pre2[500];

       p1[0]=p2[n+1]=10000;

    // left to right
    for(j=1;j<=n;j++)
        if(p1[j-1]+a[i][j]>a[i][j]+a[i-1][j]){p1[j]=a[i][j]+a[i-1][j];pre1[j]=j;}
        else{p1[j]=p1[j-1]+a[i][j];pre1[j]=j-1;}

        //right to left
    for(j=n;j>=1;j--)
        if(p2[j+1]+a[i][j]>a[i][j]+a[i-1][j]){p2[j]=a[i][j]+a[i-1][j];pre2[j]=j;}
        else {p2[j]=p2[j+1]+a[i][j];pre2[j]=j+1;}

        //sravnenie
    for(j=1;j<=n;j++)
    {
        if(p1[j]>p2[j]){a[i][j]=p2[j];path[i][j]=pre2[j];}else{a[i][j]=p1[j];path[i][j]=pre1[j];}
        p1[j]=p2[j]=0;
    }
}

int main()
{
    int i,j,min=10000,mini;


    cin>>m>>n;

    for(i=1;i<=m;i++)
    {
        a[i][0]=a[i][n+1]=10000;
        for(j=1;j<=n;j++)cin>>a[i][j];
    }

    for(i=2;i<=m;i++)matr(i);


    for(i=1;i<=n;i++)
        if(min>a[m][i]){min=a[m][i];mini=i;};

    int k1=m,k2=mini,kol=1,ans[500];

    if(m==1)cout<<mini;else{
    ans[kol]=k2;
    do
    {
        kol++;
        ans[kol]=path[k1][k2];
        if(path[k1][k2]==k2)k1--;else k2=path[k1][k2];
    }while(path[k1][k2]!=0);


    for(i=kol;i>=1;i--)cout<<ans[i]<<" ";}
    return 0;
}