Submission #270357

#	Time	Username	Problem	Language	Result	Execution time	Memory
270357		doowey	Discharging (NOI20_discharging)	C++14	36 / 100	1144 ms	719220 KiB

Discharging

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

struct Line{
    ld ai;
    ld bi;
    ld ti;
};

ld intersect(Line t1, Line t2){
    return (t2.bi-t1.bi)/(t1.ai-t2.ai);
}

struct O{
    ll vv;
    deque<Line> hull;
    ll pf;
    void add_line(Line X){
        if(hull.empty()){
            hull.push_back(X);
        }
        else{
            while(hull.size() >= 2 && intersect(hull[hull.size() - 2], X) <= intersect(hull[hull.size() - 2], hull[hull.size() - 1])){
                hull.pop_back();
            }
            hull.push_back(X);

            hull[hull.size() - 2].ti = intersect(hull[hull.size() - 2], hull[hull.size() - 1]);
        }
    }
    ll getval(ll t){
        int li = 0, ri = (int)hull.size()-1;
        int mid;
        while(li < ri){
            mid = (li + ri) / 2;
            if(hull[mid].ti < t)
                li = mid + 1;
            else
                ri = mid;
        }
        return t * hull[li].ai + hull[li].bi;
    }
};

const int N = (int)1e6 + 10;
ll dp[N];
ll f[N];
ll a[N];

int main(){
    fastIO;
    int n;
    cin >> n;
    for(int i = 1 ; i <= n; i ++ ){
        f[i] = n-i+1;
        cin >> a[i];
    }
    ll x;
    vector<O> mono;
    O cur;
    ll ca, cb;
    for(int i = 1; i <= n; i ++ ){
        x = a[i];
        cur = {x, {{-f[i],-dp[i-1], (ll)1e18}}, -(ll)1e18};
        while(!mono.empty() && mono.back().vv <= cur.vv){
            swap(mono.back().hull, cur.hull);
            for(auto x : mono.back().hull){
                ca = x.ai;
                cb = x.bi;
                cur.add_line({ca, cb, (ll)1e18});
            }
            mono.pop_back();
        }
        cur.pf = cur.getval(x);
        if(!mono.empty())
            cur.pf = max(cur.pf, mono.back().pf);
        mono.push_back(cur);
        dp[i] = -mono.back().pf;
    }
    cout << dp[n];
    return 0;
}

Compilation message (stderr)

Discharging.cpp: In function 'int main()':
Discharging.cpp:74:21: warning: narrowing conversion of '- f[i]' from 'll' {aka 'long long int'} to 'ld' {aka 'long double'} [-Wnarrowing]
   74 |         cur = {x, {{-f[i],-dp[i-1], (ll)1e18}}, -(ll)1e18};
      |                     ^~~~~
Discharging.cpp:74:27: warning: narrowing conversion of '- dp[(i - 1)]' from 'll' {aka 'long long int'} to 'ld' {aka 'long double'} [-Wnarrowing]
   74 |         cur = {x, {{-f[i],-dp[i-1], (ll)1e18}}, -(ll)1e18};
      |                           ^~~~~~~~
Discharging.cpp:80:31: warning: narrowing conversion of 'ca' from 'll' {aka 'long long int'} to 'ld' {aka 'long double'} [-Wnarrowing]
   80 |                 cur.add_line({ca, cb, (ll)1e18});
      |                               ^~
Discharging.cpp:80:35: warning: narrowing conversion of 'cb' from 'll' {aka 'long long int'} to 'ld' {aka 'long double'} [-Wnarrowing]
   80 |                 cur.add_line({ca, cb, (ll)1e18});
      |                                   ^~

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