Submission #494815

#	Time	Username	Problem	Language	Result	Execution time	Memory
494815		blue	Discharging (NOI20_discharging)	C++17	100 / 100	155 ms	21828 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()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    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 = 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;
        }

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

        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