1    2    3
1->2:180     180 -180
1->3:180     180      -180
2->3:180          180 -180
overall:     360   0  -360
prefix sum:  360  360   0

hence max from 1 to 3 is 360
do this similarly from 3 to 1

Попробуйте использовать массив, в котором a[i] означает, что из станции i выйдут a[i] пассажиров.

wrong answer 3

Can you please give me some tests?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _1869_2
{
    class Program
    {
        static void Main(string[] args)
        {
            Random random = new Random();
            int rand;
            int i, j, k, max;



            int N = int.Parse(Console.ReadLine());
            int[,] A = new int[100, 100];

            for (i = 0; i <N; ++i)
                for (j = 0; j <N; ++j)
                {
                    if (i == j)
                        A[i, j] = 0;
                    else
                    {
                        rand = random.Next(0, 1000);
                        A[i, j] = rand;
                    }
                }
            for (i = 0; i < N; i++)
                for (j = 0; j < N; j++)
                {
                    if (A[i,j] == 0)
                        continue;

                    // Vladi -> Moscow
                    if (i < j && j - i > 1)
                    {
                        for (k = i; k < j; k++)
                        {
                            A[k,k + 1] += A[i,j];
                        }
                    }
                    // Moscow -> Vladi
                    else if (i > j && i - j > 1)
                    {
                        for (k = i; k > j; k--)
                        {
                            A[k,k - 1] += A[i,j];
                        }
                    }
                };

            // get maximum for each pair of stations
            max = 0;
            for (i = 0; i < N - 1; i++)
            {
                if (Math.Max(A[i,i + 1], A[i + 1,i]) > max)
                {
                    max = Math.Max(A[i, i + 1], A[i + 1, i]);
                }
            }
            if (max % 36 == 0)
            {
                max /= 36;
                Console.WriteLine(max);
            }
            else
            {
                max /= 36;
                max = max + 1;
                Console.WriteLine(max);
            }

            //Console.ReadKey();

        }
    }
}

please give me some tests

I have WA#2

Edited by author 15.10.2011 20:34

Edited by author 15.10.2011 20:34

My solution is that
1. I calulate how many passengers go off when the train arrive the station i , called Di[i] (assume we are doing on the first turn that is from Vladivostok to Moscow). And I also have similar manipulation on doing the second turn that is from Moscow to Vladivostok), called Ve[i]
2. Then, I do for (i = 2; i <= n; i++) to browse all stations that the train will come. At station i, I subtract the number of passengers who go off the train at the station (i - 1) and plus the number of passengers who will come to the station i. And, I find the MAX from them at every station i, called luotDi. I do the same with the second turn from Moscow to Vladi..., called luotVe
4. I find maxPassengers = max(luotDi, luotVe)
5. I print the result (how many cars) = maxPassengers / 36 + 1 * (maxPassengers % 36 == 0 ? 0 : 1)

I can't find what I was wrong. Please help me! Here my source code

#include <iostream>
using namespace std;

int main()
{
    int n;
    int tam;
    int a[106][106];
    int Di[106];
    int Ve[106];


    int luotDi = 0;
    int luotVe = 0;
    cin >> n;
    for (int i = 0; i <= n + 5; i++)
    {
        Di[i] = Ve[i] = 0;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> a[i][j];
            if (i < j)
            {
                Di[j] += a[i][j];
            }
            else
            {
                if (i > j)
                    Ve[j] += a[i][j];
            }
        }
    }

    // the first turn (Vla... -> Moscow)
    int soKhach = 0;
    // station j th
    for (int j = 2; j <= n; j++)
    {
        // drop passengers
        soKhach -= Di[j - 1];

        // pick up passengers
        for (int i = 1; i < j; i++)
        {

            soKhach += a[i][j];
        }

        // find MAX
        if (soKhach > luotDi)
        {
            luotDi = soKhach;
        }
    }

    // the second turn (Moscow -> Vla...)
    soKhach = 0;
    // station j th
    for (int j = n - 1; j >= 1; j--)
    {
        // drop passenger
        soKhach -= Ve[j + 1];
        // pick up passenger
        for (int i = n; i > j; i--)
        {
            soKhach += a[i][j];
        }
        // find MAX
        if (soKhach > luotVe)
        {
            luotVe = soKhach;
        }
    }

    int result;
    float lDi = (float) luotDi;
    float lVe = (float) luotVe;
    if (luotDi > luotVe)
    {
        lDi = lDi / 36;
        result = (int) lDi;
        if (result < lDi)
        {
            result++;
        }
    }
    else
    {
        lVe = lVe / 36;
        result = (int) lVe;
        if (result < lVe)
        {
            result++;
        }
    }

    cout << result;
    return 0;
}

Thanks very much!

Edited by author 15.10.2011 17:52