Submission #691305

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
691305	2023-01-31T04:53:34 Z	saayan007	Discharging (NOI20_discharging)	C++17	38 / 100	133 ms	25516 KB

Discharging

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
using vi = vector<int>;
using vl = vector<long long>;
using vpi = vector<pair<int, int>>;
using vpl = vector<pair<long long, long long>>;

#define fur(i, a, b) for(ll i = a; i <= (ll)b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll)b; --i)
#define fr first 
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define nl "\n"
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

const ll inf = 1e16L;
struct CHT {
    struct Line {
        ll m, c;

        Line(ll a, ll b){
            m = a;
            c = b;
        }

        ll isect(Line &other) {
            return (c - other.c + other.m - m + 1) / (other.m - m);
        }

        ll val(ll x) {
            return m*x + c;
        }
    };

    deque<pair<Line, ll>> dq;

    void insert(ll m, ll c) {
        Line nex(m, c);
        if(dq.empty()) {
            dq.eb(nex, 0);
            return;
        }

        while(!dq.empty()) {
            Line pr = dq.back().fr;
            ll x = dq.back().sc;
            if(nex.m == pr.m) {
                if(nex.c > pr.c) {
                    return;
                }
            } else if(nex.isect(pr) > x) {
                break;
            }
            dq.pop_back();
        }

        if(dq.empty()) {
            dq.eb(nex, 0);
            return;
        }

        dq.eb(nex, nex.isect(dq.back().fr));
    }

    ll query(ll x) {
        ll m = dq.size();
        while(m > 1 && dq[1].sc <= x) {
            dq.pop_front();
            --m;
        }
        return dq.front().fr.val(x);
    }
};

int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll n;
    cin >> n;

    ll t[n + 1];
    fur(i, 1, n)
        cin >> t[i];

    CHT cht;
    ll dp[n + 1];
    dp[0] = 0;

    fur(i, 1, n) {
        cht.insert(n - i + 1, dp[i - 1]); 
        dp[i] = cht.query(t[i]);
    }

    cout << dp[n] << nl;
}

Subtask #1
0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	316 KB	Output is correct
3	Incorrect	212 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #2
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	1 ms	328 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	224 KB	Output is correct
13	Correct	1 ms	324 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	328 KB	Output is correct

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	1 ms	328 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	224 KB	Output is correct
13	Correct	1 ms	324 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	328 KB	Output is correct
16	Correct	101 ms	20940 KB	Output is correct
17	Correct	112 ms	21816 KB	Output is correct
18	Correct	86 ms	20268 KB	Output is correct
19	Correct	96 ms	21752 KB	Output is correct
20	Correct	102 ms	21544 KB	Output is correct
21	Correct	100 ms	21672 KB	Output is correct
22	Correct	95 ms	21296 KB	Output is correct
23	Correct	106 ms	22348 KB	Output is correct
24	Correct	102 ms	21832 KB	Output is correct
25	Correct	133 ms	22212 KB	Output is correct
26	Correct	105 ms	22604 KB	Output is correct
27	Correct	91 ms	21036 KB	Output is correct
28	Correct	103 ms	21964 KB	Output is correct
29	Correct	119 ms	21932 KB	Output is correct
30	Correct	104 ms	22204 KB	Output is correct