Cod sursa(job #163552)

Utilizator slayer4uVictor Popescu slayer4u Data 22 martie 2008 14:46:35
Problema Wanted Scor 10
Compilator cpp Status done
Runda preONI 2008, Runda Finala, Clasa a 10-a Marime 2.01 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

long n, i, j, maxim, sumi, sumj, poz, sum, v[256];

struct lol
{
       long x, y;
};
lol x[256];

inline long abss(long a)
{
     return a < 0 ? -a : a;
}

void search(long oras, long poz, long sum)
{
     if (!v[oras])
     {
       v[oras] = 1;
       sum = sum + abss(poz - x[oras].x) + x[oras].y;
       maxim = maxim < sum ? sum : maxim;
       sum = sum + x[oras].y;
       if (oras == 1 || oras == n)
         return;
         /*if (oras == 2)
           search(1, 2, sum);
            if (oras == n - 1)
              search(n, n - 1, sum);*/
       search(oras + 1, x[oras].x, sum);
       search(oras - 1, x[oras].x, sum);
     }        
}

int cmpf(lol a, lol b)
{
    return a.x < b.x;
}

int main()
{
    freopen ("wanted.in", "rt", stdin);
    freopen ("wanted.out", "wt", stdout);
    
    scanf("%ld", &n);
    for (i = 1; i <= n; ++i)
        scanf("%ld %ld", &x[i].x, &x[i].y);
        
    sort(x + 1, x + n + 1, cmpf);
    
    while (x[i].x < 0)
          ++i;
    
    i = 1;
    j = n;
    while (i <= j)
    {
          if (sumi < sumj)
             sumi += abss(x[i].x) + x[i].y, ++i;
          else
             sumj += abss(x[j].x) + x[j].y, --j;      
    }
    
//    if (x[i - 1].x + x[i - 1].y > x[j].x + x[j].y)
  //      search(i - 1, 0, 0);
  //  else
    //    search(j + 1, 0, 0);
    
  if (x[i - 1].x + x[i - 1].y > x[j + 1].x + x[j + 1].y)
  {
    poz = 0;
    sum = 0;
    j ++;
    while (j)
    {
          sum += abss(poz - x[j].x) + x[j].y + x[j].y;
          poz = x[j].x;
          --j;
    }
    maxim = maxim < sum - x[j + 1].y ? sum - x[j + 1].y : maxim;
}
else
{
    poz = 0;
    sum = 0;
    i --;
    while (i <= n)
    {
          sum += abss(poz - x[i].x) + x[i].y + x[i].y;
          poz = x[i].x;
          ++i;
    }
    maxim = maxim < sum - x[i - 1].y ? sum - x[i - 1].y : maxim;
    }
    printf("%ld\n", maxim);
    
    return 0;
}