oj.uz

Submission #93479

# Submission time Handle Problem Language Result Execution time Memory
93479 2019-01-08T18:17:50 Z Kastanda Building Bridges (CEOI17_building) C++11
100 / 100
 196 ms 15224 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 3108 KB Output is correct
2 Correct 127 ms 3192 KB Output is correct
3 Correct 126 ms 3064 KB Output is correct
4 Correct 196 ms 2808 KB Output is correct
5 Correct 143 ms 5212 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 130 ms 3108 KB Output is correct
7 Correct 127 ms 3192 KB Output is correct
8 Correct 126 ms 3064 KB Output is correct
9 Correct 196 ms 2808 KB Output is correct
10 Correct 143 ms 5212 KB Output is correct
11 Correct 114 ms 3116 KB Output is correct
12 Correct 130 ms 3064 KB Output is correct
13 Correct 71 ms 2936 KB Output is correct
14 Correct 123 ms 3192 KB Output is correct
15 Correct 127 ms 15224 KB Output is correct
16 Correct 144 ms 5212 KB Output is correct
17 Correct 32 ms 2936 KB Output is correct
18 Correct 32 ms 2936 KB Output is correct