Maybe you have to make a larger array to put the answer.

3 4
1   100 1000 0
1   1   1000 0
100 0   1000 100
//answer 1 1 2 2

1 1
1000000000
//answer 1

5 6
525   0 171   0 872 673
  0 843   0   0   0   0
  0 277   0 202   0   0
  0   0 733 957  65  96
637 566   0   0   0 441
//answer: 4 4 5 5 5 5

10 1  10 10 10
1  1  10 10 10
1  10 1  1  1
1  1  1  10 1
10 10 10 10 1
//answer: 2 2 1 1 1 1

1 10
100 90 80 70 60 50 40 30 20 10
//answer: 10

5 6
1 0 1 1 1 1
1 0 0 1 1 1
1 1 0 1 1 1
1 0 0 1 1 1
1 0 1 1 1 1
//answer: 2 2 3 3 3 2 2

3 2
3 1
1 1
1 3
//answer: 2 2 1 1

3 1
1
1
1
//answer: 1 1 1

I solved this problem with algo of Dijkstra.
Edge : (i,j)->(i+1,j), (i-1, j), (i, j+1) with weight of a[i]j];

I am using DP, it works for all TC on discussion. what could be wrong?

My code fails with WA#1 although it passes every test cases that I've found in comments. Any hints?

Need help. Stuck for serval weeks!
What is wa3 like?
What is wa6 like?

i also got wa on 5 and then found out i considered room and floor both can be at most 100. but problem says floor is 100 and room can be at most 500.

what is test #6

I used dijkstra to do in O(mnlog(mn))? Whats your approach?

If you have WA15 use for dp and for fees long long, because not optimal answer for official, which can be before program find optimal answer, may be more then 10^9.

Может, я чего и не понимаю, но почему подобный код получает TL#1?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define inf 2100000000

int a[2][510],res[2][510];
char fy[110][510];
int n,m,min,i1,i2;

void Rec(int i, int j)
{
   if (i > 1) {
      if (fy[i][j] == j) Rec(i-1,j); else Rec(i,fy[i][j]);
   };
   printf("%d\n",j);
};

int main(void)
{
   int i,j;

   scanf("%d%d",&m,&n);

   for (j = 1; j <= n; j++) scanf("%d",&a[1][j]);
   for (i = 1; i <= n; i++) res[1][i] = a[1][i];
   for (i = 2; i <= m; i++)
      for (j = 1; j <= n; j++) res[i][j] = inf;

   for (i = 1; i < m; i++) {
      i1 = i%2; i2 = (i+1)%2;
      for (j = 1; j <= n; j++) scanf("%d",&a[i2][j]);
      for (j = 1; j <= n; j++) {
         res[i2][j] = res[i1][j] + a[i2][j]; fy[i+1][j] = j;
      };
      for (j = 2; j <= n; j++)
         if (res[i2][j] > res[i2][j-1] + a[i2][j]) {
            res[i2][j] = res[i2][j-1] + a[i2][j]; fy[i+1][j] = j-1;
         };
      for (j = n-1; j >= 1; j--)
         if (res[i2][j] > res[i2][j+1] + a[i2][j]) {
            res[i2][j] = res[i+1][j+1] + a[i2][j]; fy[i+1][j] = j+1;
         };
      };

   min = inf;
   for (i = 1; i <= n; i++)
      if (res[m%2][i] < min) {
         min = res[m%2][i]; i1 = i;
      };

   Rec(m,i1);
   return 0;
};

I don't know why my program has WA#1.
My computer gives correct answer.
Please help me, maybe you had the same problem.

I don't know why I get WA on test 4!
Can there be a negative number?
This is my code:

#include<iostream>
#include<cmath>
using namespace std;
long long dyn[110][510] , a[110][510] , big, sum[110][510] , p[110][510][2] , o , m, n;
int main(){
    cin>>m>>n;
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
           cin>>a[i][j];
    for(int i=0;i<m;i++)
    {
        sum[i][0]=a[i][0];
        dyn[i][0]=100000000000000000;
        for(int j=1;j<n;j++)
        {
            sum[i][j]=sum[i][j-1]+a[i][j];
            dyn[i][j]=100000000000000000;
        }
    }
if((m==1)&&(n==1))
{
cout<<1<<endl;
return 0;
}
    dyn[m-1][0]=a[m-1][0];
    for(int i=1;i<n;i++)
    {
        dyn[m-1][i]=a[m-1][i];
    }
    for(int i=m-2;i>=0;i--)
    {
        for(int j=n-1;j>=0;j--)
        {
            for(int k=0;k<n;k++)
            {
                if(j>k)
                {
                    if(dyn[i+1][k]+sum[i][j]-sum[i][k-1]<dyn[i][j])
                    {
                        dyn[i][j]=dyn[i+1][k]+sum[i][j]-sum[i][k-1];
                        p[i][j][0]=j;
                        p[i][j][1]=k;
                    }
                }
                else
                {
                    if(dyn[i+1][k]+sum[i][k]-sum[i][j-1]<dyn[i][j])
                    {
                        dyn[i][j]=dyn[i+1][k]+sum[i][k]-sum[i][j-1];
                        p[i][j][0]=j;
                        p[i][j][1]=k;
                    }
                }
            }
        }
    }
    big=dyn[0][0];
    o=0;
    for(int i=1;i<n;i++)
    {
        if(dyn[0][i]<big)
        {
            big=dyn[0][i];
            o=i;
        }
    }
    cout<<o+1;
    for(int i=1;i<m-1;i++)
    {
    if(p[i][o][0]<=p[i][o][1])
    {
        for(int j=p[i][o][0];j<=p[i][o][1];j++)
            cout<<" "<<j+1;
            }
            else
            {
            for(int j=p[i][o][0];j>=p[i][o][1];j--)
                cout<<" "<<j+1;
                }
            o=p[i][o][1];
    }
    cout<<" "<<o+1<<endl;
return 0;
}

This test helped me to get AC, though I think it's good only against my solution:

3 4
1   100 1000 0
1   1   1000 0
100 0   1000 100
//answer 1 1 2 2

I don't understand what the output means?

thanks for help!

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;
}

Can anyone help me ? I have WA16 and i don't know what is wrong with my code .


UPD : Test 16 is a big test . I replaced in one place int with long long and i got AC.
Good Luck :) !

Edited by author 25.05.2013 14:23

Think about this case If you use DP
2 2
1 1
0 0

when considering the elem 0 at [1, 0] , you can find the way from [0, 1] -> [1, 0] and [0, 1] -> [1, 1] -> [1, 0] have the same sum(both are 1), how to handle this situation ?
I handle this by giving the way from `ABOVE` higher priority, or else when printing the path to the answer, you wil get [1, 0] <- [1, 1] <- [1, 0] <- [1, 1] ....... which is WA.

and another thing to notice is you may need long long to hold.

hope it helps  :)

What is test #4?