Cod sursa(job #961288)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 20:56:20
Problema Wanted Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <algorithm>
 
using namespace std;
 
ifstream fin("wanted.in"); ofstream fout("wanted.out");
 
pair <int, int> a[300];
 
int n;
long long b[300][300][2];
 
long long Div(int st ,int dr, int tata)
{
    int semn;
 
    if(tata < st)
        semn = 1;
 
    else
        semn= 0;
 
    if(b[st][dr][semn] < ((1LL << 40)) && b[st][dr][semn])
        return b[st][dr][semn];
 
    if(st > dr)
        return 0;
 
    b[st][dr][semn] = 1LL << 40;
 
    for(int i = st; i <= dr; i++)
    {
        b[st][dr][semn] = min(max(Div(st, i - 1, i), Div(i + 1, dr, i)) + a[i].second + a[tata].second + max(a[tata].first - a[i].first, -a[tata].first + a[i].first), b[st][dr][semn]);
    }
 
    return b[st][dr][semn];
}
 
int main()
{
 
    fin >> n;
 
    for(int i = 1; i <= n; i++)
        fin >> a[i].first >> a[i].second;
 
    sort(a + 1, a + n + 1);
 
    fout << Div(1, n, 0);
 
    fin.close(); fout.close();
    return 0;
}