oj.uz

Submission #974041

# Submission time Handle Problem Language Result Execution time Memory
974041 2024-05-02T16:10:36 Z n3rm1n Building Bridges (CEOI17_building) C++17
100 / 100
 43 ms 24664 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAXN = 1e5 + 10, MAXX = 1e6+10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long n, h[MAXN], w[MAXN];
long long pref[MAXN];
void read()
{
    cin >> n;
    for (long long i = 1; i <= n; ++ i)
        cin >> h[i];
    for (long long i = 1; i <= n; ++ i)
    {
        cin >> w[i];
        pref[i] = pref[i-1] + w[i];
    }
}
struct line
{
    long long k, m;
    line(){};
    line(long long _k, long long _m)
    {
        k = _k;
        m = _m;
    }
    long long calc(long long x)
    {
        return (x * k + m);
    }
};

struct li_chao
{
    line t[MAXX * 4];
    bool used[MAXX * 4];
    void update(long long i, long long l, long long r, line curr)
    {
        if(l > r)return;
        if(!used[i])
        {
            t[i] = curr;
            used[i] = 1;
            return;
        }

        if(t[i].calc(l) > curr.calc(l))swap(t[i], curr);
        if(l == r)return;

        long long mid = (l + r) / 2;



        if(t[i].calc(mid) < curr.calc(mid))
            update(i * 2 + 1, mid + 1, r, curr);
        else
        {
            swap(t[i], curr);
            update(i * 2, l, mid, curr);
        }
    }


    long long query(long long i, long long l, long long r, long long x)
    {
        if(l > r)return 1e17;
        if(!used[i])return 1e17;
        if(l == r)return t[i].calc(x);

        long long mid = (l + r) / 2, res = t[i].calc(x);
        if(x <= mid)res = min(res, query(i * 2, l, mid, x));
        else res = min(res, query(i * 2 + 1, mid + 1, r, x));
        return res;
    }

};
li_chao li;
long long dp[MAXN];
void solve()
{
    dp[1] = 0;
    line neww = line(- 2 * h[1], h[1] * h[1] - pref[1]);

    //cout << "k = " << - 2 * h[1] << " m = " << h[1] * h[1] - pref[1] << endl;
    li.update(1, 0, 1e6, neww);
    for (long long i = 2; i <= n; ++ i)
    {

        dp[i] = li.query(1, 0, 1e6, h[i]) + h[i] * h[i] + pref[i-1];
       // cout << dp[i] << endl;

        neww = line(- 2*h[i], h[i] * h[i] - pref[i] + dp[i]);
       // cout << "k = " << - 2 * h[i] << " m = " << h[i] * h[i] - pref[i] + dp[i] << endl;
        li.update(1, 1, 1e6, neww);
    }
    cout << dp[n] << endl;
}
int main()
{
    speed();

    read();
    solve();
    return 0;
}

/**
100
3436 3707 211 2852 3723 3542 4138 3373 1257 3694 194 2423 1597 4278 1247 4633 2137 504 4266 1001 4785 4080 4825 3452 256 1905 2170 2693 1069 3330 2484 4641 3440 2675 1170 4601 3327 168 4939 1991 2610 418 58 1916 1278 3865 1246 3118 3039 2363 3030 70 4598 830 379 1097 3936 828 1345 899 1599 4273 331 2916 414 4127 2400 968 4758 3311 2562 479 3621 2091 1716 422 3280 934 2435 3893 2252 3294 1534 665 3314 2806 3464 2167 4096 2152 4186 3938 3367 3100 1690 3165 3454 1427 2775 2211
238 681 29 2543 1088 1217 2344 285 1431 1017 1978 733 2461 2482 404 931 1039 1203 398 298 2251 921 1212 2976 505 766 2928 1388 2612 2181 2156 21 2883 2540 2885 1766 85 2973 1443 2252 1903 1950 1177 1513 1761 4 767 1255 2157 1086 1624 512 2517 1544 825 1887 96 2832 2894 693 27 2375 1696 2430 232 22 2530 1001 305 1339 1176 2927 2934 1012 858 54 2847 1255 1785 1268 611 530 1818 845 1314 2640 955 215 1003 2314 2064 1503 2212 694 708 263 2664 2886 1028 2020


*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 10840 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15176 KB Output is correct
2 Correct 34 ms 15364 KB Output is correct
3 Correct 34 ms 13144 KB Output is correct
4 Correct 33 ms 21332 KB Output is correct
5 Correct 25 ms 15364 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 10840 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 34 ms 15176 KB Output is correct
7 Correct 34 ms 15364 KB Output is correct
8 Correct 34 ms 13144 KB Output is correct
9 Correct 33 ms 21332 KB Output is correct
10 Correct 25 ms 15364 KB Output is correct
11 Correct 43 ms 22864 KB Output is correct
12 Correct 34 ms 18512 KB Output is correct
13 Correct 33 ms 23120 KB Output is correct
14 Correct 35 ms 18632 KB Output is correct
15 Correct 24 ms 14160 KB Output is correct
16 Correct 24 ms 16472 KB Output is correct
17 Correct 20 ms 20568 KB Output is correct
18 Correct 20 ms 24664 KB Output is correct