Submission #93479

#	Time	Username	Problem	Language	Result	Execution time	Memory
93479		Kastanda	Building Bridges (CEOI17_building)	C++11	100 / 100	196 ms	15224 KiB

building

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
struct CHT
{
    const ll INF = 1e18 + 10;
    typedef pair < ll , ll > Line;
    set < pair < Line , ll > > S;
    set < pair < ll , Line > > I;
    inline void Add(Line X)
    {
        ll t = -INF;
        auto it = S.lower_bound({X, -INF});
        while (S.size())
        {
            if (it == S.begin())
                {t = - INF; break;}
            it --;
            ll r = Intersection(it->first, X);
            if (r > it->second)
                {t = r; break;}
            I.erase({it->second, it->first});
            it = S.erase(it);
        }
        it = S.lower_bound({X, -INF});
        while (S.size())
        {
            if (it == S.end())
                break;
            Line Y = it->first;
            I.erase({it->second, it->first});
            it = S.erase(it);
            ll r = Intersection(X, Y);
            if (r <= t)
            {
                r = -INF;
                if (it != S.begin())
                    it --, r = Intersection(it->first, Y);
                S.insert({Y, r});
                I.insert({r, Y});
                return ;
            }
            if (it != S.end() && it->second <= r)
                continue;
            S.insert({Y, r});
            I.insert({r, Y});
            break;
        }
        S.insert({X, t});
        I.insert({t, X});
    }
    ll GetMax(ll X)
    {
        auto it = I.upper_bound({X, {INF, INF}}); it --;
        return (it->second.first * X + it->second.second);
    }
    ll Intersection(Line X, Line Y)
    {
        if (X.first == Y.first && X.second <= Y.second)
            return (-INF);
        if (X.first == Y.first)
            return (INF);
        return ((X.second - Y.second) / (Y.first - X.first) + ((X.second - Y.second) % (Y.first - X.first) > 0));
    }
};
int n, H[N], W[N];
ll sum, dp[N];
CHT C;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &H[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &W[i]);
    for (int i = 1; i <= n; i++)
    {
        sum += W[i];
        if (i != 1)
            dp[i] = - C.GetMax(H[i] * 2) + 1LL * H[i] * H[i];
        dp[i] -= W[i];
        C.Add({H[i], - dp[i] - 1LL * H[i] * H[i]});
    }
    return !printf("%lld\n", dp[n] + sum);
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
building.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &H[i]);
         ~~~~~^~~~~~~~~~~~~
building.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &W[i]);
         ~~~~~^~~~~~~~~~~~~

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