Submission #494814

#	Time	Username	Problem	Language	Result	Execution time	Memory
494814		blue	Discharging (NOI20_discharging)	C++17	100 / 100	402 ms	27148 KiB

Discharging

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
#define sz(x) int(x.size())

const ll INF = 1'000'000'000'000'000'000LL;


struct line
{
    double a;
    double b;
};

double intersect(line A, line B)
{
    return (B.b-A.b)/(A.a-B.a);
}


int main()
{
    int N;
    cin >> N;

    int TS = N;

    vector<pll> T;

    T.push_back({0, 0});
    for(int i = 1; i <= N; i++)
    {
        ll t;
        cin >> t;
        if(t <= T.back().first)
            T.back().second++;
        else
            T.push_back({t, 1});
    }

    N = sz(T)-1;

    vll suff(1+N, 0);
    suff[0] = TS;
    for(int i = 1; i <= N; i++) suff[i] = suff[i-1] - T[i].second;


    vll dp(1+N, INF);

    dp[0] = 0;

    vector<line> L;
    L.push_back(line{double(suff[0]), double(dp[0])});

    // for(int i = 0; i <= N; i++) cerr << T[i].first << ' ' << T[i].second << ' ' << suff[i] << '\n';

    for(int i = 1; i <= N; i++)
    {
        int lo = 0;
        int hi = sz(L) - 1;

        double x = T[i].first;

        while(lo != hi)
        {
            int mid = (lo+hi)/2;
            if(intersect(L[mid], L[mid+1]) <= x)    ///!!!!!!!!
                lo = mid+1;
            else
                hi = mid;
        }

        // if(i == 2)
        // {
        //     cerr << "!!!\n";
        //     cerr << intersect(L[0], L[1]) << '\n';
        //     cerr << "x = " << x << '\n';
        // }

        dp[i] = ll(L[lo].a) * T[i].first  +  ll(L[lo].b);

        // for(auto y: L) cerr << y.a << "/" << y.b << " ";
        // cerr << '\n';
        // cerr << "lo = " << lo << '\n';

        // cerr << i << " : " << dp[i] << '\n';

        if(i < N)
        {
            line new_line{double(suff[i]), double(dp[i])};
            while(sz(L) >= 2 && intersect(L[sz(L)-2], L[sz(L)-1]) >= intersect(L[sz(L)-1], new_line)) //!!!!!!!!!!!
                L.pop_back();

            L.push_back(new_line);
        }
    }
    cout << dp[N] << '\n';
}

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 11 / 11
• Subtask 5: 14 / 14
• Subtask 6: 28 / 28