Submission #270444

#	Time	Username	Problem	Language	Result	Execution time	Memory
270444		doowey	Discharging (NOI20_discharging)	C++14	100 / 100	203 ms	14840 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);
}

vector<Line> hull;

void add_line(Line nw){
    while(hull.size() >= 2 && intersect(hull[hull.size() - 2], nw) <= intersect(hull[hull.size() - 2],hull[hull.size() - 1])){
        hull.pop_back();
    }
    if(!hull.empty())
        hull.back().ti = intersect(hull.back(), nw);
    hull.push_back(nw);
}

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

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

int main(){
    fastIO;
    int n;
    cin >> n;
    ll a, x=0ll;
    add_line({-n,0,(ll)1e18});
    ll vl;
    for(int i = 1; i <= n; i ++ ){
        cin >> a;
        x = max(x, a);
        vl = get(x);
        dp[i]=-vl;
        add_line({-(n-i), -dp[i], (ll)1e18});
    }
    cout << dp[n] << "\n";
    return 0;
}

Compilation message (stderr)

Discharging.cpp: In function 'int main()':
Discharging.cpp:56:15: warning: narrowing conversion of '- n' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
   56 |     add_line({-n,0,(ll)1e18});
      |               ^~
Discharging.cpp:63:19: warning: narrowing conversion of '-(n - i)' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
   63 |         add_line({-(n-i), -dp[i], (ll)1e18});
      |                   ^~~~~~
Discharging.cpp:63:27: warning: narrowing conversion of '- dp[i]' from 'll' {aka 'long long int'} to 'ld' {aka 'long double'} [-Wnarrowing]
   63 |         add_line({-(n-i), -dp[i], (ll)1e18});
      |                           ^~~~~~

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