Cod sursa(job #2148940)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 2 martie 2018 10:36:35
Problema Wanted Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int modul (int x){
    if (x>=0)
        return x;
    return -x;
}
pair <int,int> v[201];
int maxoptim (int st,int dr,int poz){
    int mid,drum;
    //if (st==1 && dr==1)
    //printf ("%d %d\n",st,dr);
    if (st>dr)
        return 0;
    mid=(st+dr)/2;
    drum=2*v[mid].second+modul (v[mid].first-poz);
    if (st==dr)
        return drum-v[mid].second;
    return drum+max(maxoptim(mid+1,dr,v[mid].first),maxoptim(st,mid-1,v[mid].first));
}
int main()
{
    FILE *fin=fopen ("wanted.in","r");
    FILE *fout=fopen ("wanted.out","w");
    int n,i;
    fscanf (fin,"%d",&n);
    for (i=1;i<=n;i++)
        fscanf (fin,"%d%d",&v[i].first,&v[i].second);
    sort (v+1,v+n+1);
    fprintf (fout,"%d",maxoptim(1,n,0)); // maxoptim e un fel de cautare binara la care ma duc pe ambele ramuri
    return 0;
}