제출 #1155439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155439		vicvic	Discharging (NOI20_discharging)	C++20	100 / 100	274 ms	16072 KiB

Discharging

#include <iostream>
#include <fstream>
#include <deque>
#include <cstdint>
#define int long long
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;
int32_t 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: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 11 / 11
• Subtask 5: 14 / 14
• Subtask 6: 28 / 28