Cod sursa(job #2970950)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 26 ianuarie 2023 10:48:47
Problema Wanted Scor 10
Compilator cpp-64 Status done
Runda sa_fac_schema Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAX_N = 200;
int n;
struct oras{
    int x, y;
    inline bool operator < (const oras &rhs) const{
        return x < rhs.x;
    }
} o[MAX_N + 5];

long long sol;
static inline long long solve(int st, int dr, int start){
    int md = ((st + dr) >> 1);

    ///merg de la start la o[md]
    long long answer = abs(start - o[md].x);

    ///vizitez oras-ul o[md]
    answer += 2 * o[md].y;

    ///in functie de raspuns ma duc in stanga respectiv dreapta
    if(st == dr)
        return answer - o[md].y; ///nu trebuie sa ma mai intorc
    else if(st+1 == dr)
        return answer + solve(dr, dr, o[md].x);
    else
        return answer + max(solve(st, md-1, o[md].x), solve(md+1, dr, o[md].x));
}

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>n;
    for(int i=1; i<=n; i++)
        fin>>o[i].x>>o[i].y;
    sort(o+1, o+n+1);

    fout<<solve(1, n, 0);
    return 0;
}
/**
4
-10 3
-5 2
5 4
8 2
**/