Submission #640370

#	Time	Username	Problem	Language	Result	Execution time	Memory
640370		sumit_kk10	Discharging (NOI20_discharging)	C++17	72 / 100	100 ms	21968 KiB

Discharging

#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define F first
#define S second
#define int long long
using namespace std;
const int N = 1e6 + 5, MOD = 1e9 + 7;
int n, a[N], dp[N];

struct Line{
    int m, c;

    int val(int x){
        return m*x + c;
    }
};

vector<Line> hulls;

bool check(Line a, Line b, Line cc){
    if(((b.c - a.c) * (a.m - cc.m)) > ((cc.c - a.c) * (a.m - b.m)))
        return true;
    return false;
}

void insert(int mm, int cc){
    Line cur;
    cur.m = mm;
    cur.c = cc;
    while(hulls.size() > 1){
        if(check(hulls[hulls.size() - 2], hulls[hulls.size() - 1], cur))
            hulls.pop_back();
        else
            break;
    }
    hulls.pb(cur);
}

int get(int x){
    int low = 0, high = (int) hulls.size() - 2, ans = (int) hulls.size() - 1;
    while(low <= high){
        int mid = (low + high) / 2;
        if(hulls[mid].val(x) <= hulls[mid + 1].val(x)){
            ans = mid;
            high = mid - 1;
        }
        else
            low = mid + 1;
    }
    return hulls[ans].val(x);
}

void solve(){
    cin >> n;
    a[0] = LLONG_MAX;
    bool ok = true;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        if(a[i] > a[i - 1])
            ok = false;
    }
    if(ok){
        cout << a[1] * n << "\n";
        return;
    }
    int mx = 0;
    for(int i = 1; i <= n; ++i){
        mx = max(mx, a[i]);
        insert(n - i + 1, dp[i - 1]);
        dp[i] = get(mx);
    }
    cout << dp[n] << "\n";
}
 
int32_t main(){
    fast;
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

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