oj.uz

Submission #881821

# Submission time Handle Problem Language Result Execution time Memory
881821 2023-12-02T03:18:06 Z abysmal Building Bridges (CEOI17_building) C++14
100 / 100
 40 ms 10580 KB 
#include<iostream>
#include<stdio.h>
#include<stdint.h>
#include<iomanip>
#include<algorithm>
#include<utility>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<deque>
#include<math.h>
#include<assert.h>
#include<string.h>
#include<chrono>
#include<bitset>

using namespace std;
using namespace std::chrono;

const int64_t INF = (int64_t) 9e18 + 100;
const int64_t mINF = (int64_t) 1e6 + 5;
const int64_t MOD = 1e9;
const int64_t MOD2 = 998244353;
const int nbit = 63;
const int ndig = 10;
const int nchar = 26;
const int p1 = 31;
const int p2 = 53;
const int D = 4;
int dr[D] = {-1, 0, 1, 0};
int dc[D] = {0, 1, 0, -1};
const int Dk = 8;
int drk[Dk] = {2, 2, -2, -2, 1, 1, -1, -1};
int dck[Dk] = {1, -1, 1, -1, 2, -2, 2, -2};
bool Q = false;

struct Line
{
    int64_t k;
    int64_t m;
    mutable int64_t p;

    bool operator < (const Line& o) const
    {
        if(Q) return p < o.p;
        return k < o.k;
    }
};

struct LineContainer : multiset<Line, less<> >
{
    int64_t div(int64_t a, int64_t b)
    {
        return a / b - ((a ^ b) < 0 && a % b);
    }

    bool isect(iterator x, iterator y)
    {
        if(y == end())
        {
            x->p = INF;
            return false;
        }

        if(x->k == y->k)
        {
            if(x->m > y->m) x->p = INF;
            else x->p = -INF;
        }
        else x->p = div(y->m - x->m, x->k - y->k);

        return x->p >= y->p;
    }

    void add(int64_t k, int64_t m)
    {
        auto z = insert({-k, -m, 0});
        auto y = z++;
        auto x = y;

        while(isect(y, z)) z = erase(z);
        if(x != begin() && isect(--x, y)) isect(x, y = erase(y));

        while((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
    }

    int64_t query(int64_t x)
    {
        assert(!empty());

        Q = true;
        auto l = *lower_bound({0, 0, x});
        Q = false;

        return -(l.k * x + l.m);
    }
};

struct Solution
{
    int n;
    vector<int64_t> h;
    vector<int64_t> w;
    vector<int64_t> suffix;

    Solution() {}

    void solve()
    {
        cin >> n;
        h.resize(n, 0);
        w.resize(n, 0);
        suffix.resize(n + 1, 0);
        for(int i = 0; i < n; i++)
        {
            cin >> h[i];
        }

        for(int i = 0; i < n; i++)
        {
            cin >> w[i];
        }

        for(int i = n - 1; i >= 0; i--)
        {
            suffix[i] = suffix[i + 1] + w[i];
        }

        LineContainer lc;
        vector<int64_t> dp(n, -INF);
        dp[0] = 0;
        for(int i = 0; i < n; i++)
        {
            if(i != 0)
            {
                int64_t max_ = lc.query(h[i]);
                dp[i] = h[i] * h[i] + max_ - suffix[i];
            }

            lc.add(-2 * h[i], h[i] * h[i] + suffix[i + 1] + dp[i]);
        }

        cout << dp[n - 1] << "\n";
    }

    int modadd(int t1, int t2)
    {
        int res = t1 + t2;
        if(res >= MOD) res -= MOD;
        return res;
    }

    int modsub(int t1, int t2)
    {
        int res = t1 - t2;
        if(res < 0) res += MOD;
        return res;
    }

    int modmul(int t1, int t2)
    {
        int64_t res = 1LL * t1 * t2;
        return res % MOD;
    }

    int Abs(int t1)
    {
        if(t1 < 0) return -t1;
        return t1;
    }

    int64_t MASK(int j)
    {
        return (1LL << j);
    }

    bool BIT(int64_t t1, int j)
    {
        return (t1 & MASK(j));
    }
};

void __setup()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

//    freopen("XAYCAU.INP", "r", stdin);
//    freopen("XAYCAU.OUT", "w", stdout);
}

int main()
{
    __setup();
//        auto start = high_resolution_clock::now();
    int t = 1;
//    cin >> t;
    for(int i = 1; i <= t; i++)
    {
        Solution().solve();
    }

//    auto stop = high_resolution_clock::now();
//    auto duration = duration_cast<microseconds>(stop - start);
//    cerr << duration.count() << "\n";
    return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3896 KB Output is correct
2 Correct 32 ms 3676 KB Output is correct
3 Correct 32 ms 3664 KB Output is correct
4 Correct 29 ms 4560 KB Output is correct
5 Correct 29 ms 5540 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 36 ms 3896 KB Output is correct
7 Correct 32 ms 3676 KB Output is correct
8 Correct 32 ms 3664 KB Output is correct
9 Correct 29 ms 4560 KB Output is correct
10 Correct 29 ms 5540 KB Output is correct
11 Correct 31 ms 4816 KB Output is correct
12 Correct 32 ms 4444 KB Output is correct
13 Correct 27 ms 4696 KB Output is correct
14 Correct 32 ms 4816 KB Output is correct
15 Correct 40 ms 10580 KB Output is correct
16 Correct 28 ms 5720 KB Output is correct
17 Correct 18 ms 4444 KB Output is correct
18 Correct 18 ms 4444 KB Output is correct