Submission #1155434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155434		vicvic	Discharging (NOI20_discharging)	C++20	0 / 100	251 ms	8268 KiB

Discharging

#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
class ConvexHull
{
public:
    deque <pair <int, int>> coada;
    int evaluate (pair <int, int> crt, int x)
    {
        return crt.first*x+crt.second;
    }
    long double intersection (pair <int, int> line, pair <int, int> line1)
    {
        return (line1.second-line.second)/(line.first-line1.first);
    }
    bool isRedundant (pair <int, int> check, pair <int, int> before, pair <int, int> after)
    {
        return intersection (after, check)>=intersection (after, before);
    }
    void add (int m, int a)
    {
        while (coada.size()>1 && isRedundant (coada.back(), {m, a}, coada[coada.size()-2])) coada.pop_back ();
        coada.push_back ({m, a});
    }
    int query (int x)
    {
        while (coada.size()>1 && evaluate (coada[0], x)>evaluate (coada[1], x))
        {
            coada.pop_front ();
        }
        return evaluate (coada[0], x);
    }
};
int dp[1000005], v[1000005], n;
ConvexHull cht;
int main ()
{
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        cin >> v[i];
        v[i]=max (v[i-1], v[i]);
        cht.add (-i, dp[i-1]);
        dp[i]=v[i]*(n+1)+cht.query (v[i]);
    }
    cout << dp[n];
    return 0;
}

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