Cod sursa(job #2442853)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 25 iulie 2019 15:00:09
Problema Euro Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <fstream>
#define DIM 34600
#define INF 2000000000000000000000000LL
using namespace std;

ifstream fin ("euro.in");
ofstream fout ("euro.out");
struct dreapta{
    long long a,b;
};
dreapta aint[4*DIM];
long long d[DIM],s[DIM];
int n,t,x,i;
long long f (long long a, long long b, int x){
    return 1LL*a*x+b;
}
void add (int nod, int st, int dr, long long a, long long b){
    if (st == dr){
        if (f(a,b,st) > f(aint[nod].a,aint[nod].b,st))
            aint[nod] = {a,b};
        return;
    }
    int mid = (st+dr)>>1;
    int ok_mid = 0, ok_dr = 0;
    /// vad daca functia poate actualiza un intervalul din mid sau din dr
    if (f(a,b,mid) >= f(aint[nod].a,aint[nod].b,mid))
        ok_mid = 1;
    if (f(a,b,dr) >= f(aint[nod].a,aint[nod].b,dr))
        ok_dr = 1;

    if (!ok_mid && !ok_dr) /// trebuie sa merg in stanga
        add ((nod<<1),st,mid,a,b);
    else {
        if (!ok_mid && ok_dr) /// ma duc in dreapta
            add ((nod<<1)|1,mid+1,dr,a,b);
        else {
            /// inseamna ca imi actualizeaza nodul curent
            swap (aint[nod].a,a);
            swap (aint[nod].b,b);
            if (ok_dr)
                add ((nod<<1),st,mid,a,b);
            else add ((nod<<1)|1,mid+1,dr,a,b);
        }}}
long long query (int nod, int st, int dr, int x){
    if (st == dr)
        return f(aint[nod].a,aint[nod].b,x);
    int mid = (st+dr)>>1;
    long long sol = -INF;
    if (x <= mid)
        sol = query ((nod<<1),st,mid,x);
    else sol = query ((nod<<1)|1,mid+1,dr,x);
    return max (sol,f(aint[nod].a,aint[nod].b,x));
}
int main (){

    fin>>n>>t;
    for (i=1;i<=n;i++){
        fin>>x;
        s[i] = s[i-1] + x;
    }
    for (i=1;i<=n;i++){
        fin>>x;
        d[i] = s[i]*i - t + query (1,1,n,i);
        add (1,1,n,-s[i],d[i]); /// adaugam o dreapta noua
    }
    fout<<d[n];



    return 0;
}