Submission #912944

#	Time	Username	Problem	Language	Result	Execution time	Memory
912944		12345678	Discharging (NOI20_discharging)	C++17	100 / 100	118 ms	22612 KiB

Discharging

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
 
const ll nx=1e6+5, inf=1e18;
ll n, t[nx], dp[nx];

struct line
{
    ll m, c, p;
    line(ll m, ll c, ll p): m(m), c(c), p(p){}
};

struct convexhull
{
    deque<line> dq;
    ll div(ll a, ll b)
    {
        if ((a%b)==0||(a^b)>=0) return a/b;
        return a/b-1;
    }
    void add(ll m, ll c)
    {
        while (dq.size()>1)
        {
            line tmp=dq.back();
            dq.pop_back();
            if (div(c-tmp.c, tmp.m-m)>dq.back().p) 
            {
                dq.push_back(tmp);
                break;
            }
        }
        if (!dq.empty()) dq.back().p=div(c-dq.back().c, dq.back().m-m);
        dq.push_back(line(m, c, inf));
    }
    ll query(ll x)
    {
        while (dq.front().p<x) dq.pop_front();
        return dq.front().m*x+dq.front().c;
    }
    void show()
    {
        for (auto tmp:dq) printf("line %d %d %lld\n", tmp.m, tmp.c, tmp.p);
    }
} c;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>t[i], t[i]=max(t[i], t[i-1]);
    c.add(0, 0);
    //c.show();
    for (int i=1; i<=n; i++) dp[i]=c.query(t[i])+t[i]*n,  c.add(-i, dp[i]); //c.show();
    cout<<dp[n];
}

Compilation message (stderr)

Discharging.cpp: In member function 'void convexhull::show()':
Discharging.cpp:46:41: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   46 |         for (auto tmp:dq) printf("line %d %d %lld\n", tmp.m, tmp.c, tmp.p);
      |                                        ~^             ~~~~~
      |                                         |                 |
      |                                         int               long long int
      |                                        %lld
Discharging.cpp:46:44: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   46 |         for (auto tmp:dq) printf("line %d %d %lld\n", tmp.m, tmp.c, tmp.p);
      |                                           ~^                 ~~~~~
      |                                            |                     |
      |                                            int                   long long int
      |                                           %lld

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