Cod sursa(job #1116251)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 22 februarie 2014 14:09:18
Problema Wanted Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <fstream>
#include <cmath>
#include <algorithm>

#define inf 2000000001

using namespace std;

ifstream fin("wanted.in");
ofstream fout("wanted.out");

struct city
{
    int x,y;
}v[201];
int n,current0,current1;
long long ans;
long long dp[201][201][2];

bool cmp (city a, city b)
{
    return a.x < b.x;
}

int main()
{
    fin>>n;

    for (int i=1; i<=n; ++i)
    {
        fin>>v[i].x>>v[i].y;
    }

    if (n == 1)
    {
        fout<<abs(v[1].x)+v[1].y;
        return 0;
    }

    sort (v+1,v+n+1,cmp);

    for (int i=0; i<n-1; ++i)
    {
        for (int j=1; i+j<=n; ++j)
        {
            dp[j][j+i][0] = dp[j][j+i][1] = inf;

            int current0 = 0;
            int current1 = v[j+i].x - v[j].x;

            for (int k=j; k<=i+j; ++k)
            {
                int h = 2*v[k].y;
                if (j == i+j)
                    h = v[k].y;

                int dist0 = v[k].x-v[k-1].x;
                    if (k == j)
                        dist0 = 0;
                int dist1 = v[k+1].x - v[k].x;
                if (k == j+i)
                    dist1 = 0;

                if (j != 1)
                {
                    dp[j][j+i][0] = min (dp[j][j+i][0] , max(dp[j][k-1][1] + dist0 ,dp[k+1][j+i][0] + dist1) + current0 + h);
                }
                if (j+i!=n)
                {
                    dp[j][j+i][1] = min (dp[j][j+i][1] , max(dp[j][k-1][1] + dist0,dp[k+1][j+i][0] + dist1) + current1 + h);
                }

                current0 += v[j+1].x - v[j].x;
                current1 -= v[j+1].x - v[j].x;
            }
        }
    }

    ans = inf;

    for (int k = 1; k<=n; ++k)
    {
        int dist0 = v[k].x-v[k-1].x;
           if (k == 1)
                dist0 = 0;
        int dist1 = v[k+1].x - v[k].x;
            if (k == n)
                dist1 = 0;

        ans = min (ans , max(dp[1][k-1][1] + dist0, dp[k+1][n][0] + dist1) + abs(v[k].x) + 2*v[k].y);
    }

    fout<<ans;
}