Submission #1177165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177165		vicvic	Building Bridges (CEOI17_building)	C++20	60 / 100	125 ms	22904 KiB

building

#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include <map>
#include <limits>
using namespace std;
const long double inf=numeric_limits <long double>::infinity();
const long double MAX_SLOPE=1e6+5;
const int NMAX=1e5;
struct line
{
    long double slope, intercept;
    line (long double _slope, long double _intercept)
    {
        slope=_slope;
        intercept=_intercept;
    }
    long long operator () (long long x)
    {
        return slope*x+intercept;
    }
};
line ultra_slopper (MAX_SLOPE, 0);
bool operator < (line a, line b)
{
    if (a.slope==b.slope)
        return a.intercept<b.intercept;
    return a.slope<b.slope;
}
long double meet (line a, line b)
{
    return (long double) (a.intercept-b.intercept)/ (long double) (b.slope-a.slope);
}
class ConvexHull
{
public:
    set <pair <long double, line>> prevX;
    map <line, pair <long double, long double>> limits;
    ConvexHull (line a)
    {
        limits[a]={-inf, inf};
        prevX.insert ({-inf, a});
    }
    void insert (line function)
    {
        if (limits.count (function))
            return;
        auto poz=limits.insert ({function, {0, 0}}).first;
        if (poz!=limits.begin() && prev (poz) -> first.slope==function.slope)
        {
            limits.erase (poz);
            return;
        }
        if (next (poz)!=limits.end() && next (poz) -> first.slope==function.slope)
        {
            prevX.erase ({next (poz) -> second.first, next(poz) -> first});
            limits.erase (next (poz));
        }
        if (poz!=limits.begin() && next (poz)!=limits.end() && meet (next (poz) -> first, function)>=next (poz) -> second.second && meet (prev (poz) -> first, function)<=prev (poz) -> second.first)
        {
            limits.erase (poz);
            return;
        }
        while (next(poz)!=limits.end())
        {
            if (meet (next (poz) -> first, function)<=next (poz) -> second.first)
            {
                prevX.erase ({next (poz) -> second.first, next (poz) -> first});
                limits.erase (next (poz));
            }
            else
            {
                next (poz) -> second.second=meet (next (poz) -> first, function);
                poz -> second.first=meet (next (poz) -> first, function);
                break;
            }
        }
        if (next (poz)==limits.end())
        {
            poz -> second.first=-inf;
        }
        while (poz!=limits.begin())
        {
            if (meet (prev (poz) -> first, function)>=prev (poz) -> second.second)
            {
                prevX.erase ({prev (poz) -> second.first, prev (poz) -> first});
                limits.erase (prev (poz));
            }
            else
            {
                prevX.erase ({prev (poz) -> second.first, prev (poz) -> first});
                prev (poz) -> second.first=meet (prev (poz) -> first, function);
                prevX.insert ({prev (poz) -> second.first, prev (poz) -> first});
                poz -> second.second=meet (prev (poz) -> first, function);
                break;
            }
        }
        if (poz==limits.begin())
        {
            poz -> second.second=inf;
        }
        prevX.insert ({poz -> second.first, function});
    }
    long long query (long long x)
    {
        line seg=prev (prevX.upper_bound ({x, ultra_slopper})) -> second;
        return seg (x);
    }
};
long long int n, h[NMAX+5], dp[NMAX+5], v[NMAX+5];
int main ()
{
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        cin >> h[i];
    }
    for (int i=1;i<=n;i++)
    {
        cin >> v[i];
    }
    int sum=v[1];
    ConvexHull cht (line (h[1], -sum+h[1]*h[1]+dp[1]));
    for (int i=2;i<=n;i++)
    {
        dp[i]=sum+h[i]*h[i]+cht.query (-2*h[i]);
        sum+=v[i];
        cht.insert (line (h[i], -sum+h[i]*h[i]+dp[i]));
    }
    cout << dp[n];
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40