Submission #1288657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288657		samarthkulkarni	Discharging (NOI20_discharging)	C++20	100 / 100	84 ms	15952 KiB

Discharging

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// #pragma GCC target ("avx2")
// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize("fast-math")

#define ll long long
#define ld long double
#define vi vector<ll>
#define endl "\n"
#define pr pair<ll, ll>
#define ff first 
#define ss second
#define all(x) x.begin(), x.end()
const int mod = 1e9+7;
void _p(ll a){cout<<a<<endl;}
void _p(string a){cout<<a<<endl;}
void _p(ld a) {cout<<a<<endl;}
template <class T>
void _p(vector<T> a){for(T val:a)cout<<val<<" ";cout<<endl;}
#define debug(x) cout<<#x<<" -> ";_p(x)

typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update > ordered_set;

vector<pr> move8 = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};
vector<pr> move4 = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector<pr> move2 = {{0, 1}, {1, 0}};


void solution();
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}

struct CHT {
    deque<pr> lines;
    bool bad(pr L1, pr L2, pr L3) {
        return (__int128)(L2.ss - L1.ss) * (L2.ff - L3.ff) >= 
               (__int128)(L3.ss - L2.ss) * (L1.ff - L2.ff);
    }
    
    void addLine(ll m, ll c) {
        pr newLine = {m, c};
        while (lines.size() >= 2 && 
               bad(lines[lines.size()-2], lines[lines.size()-1], newLine)) {
            lines.pop_back();
        }
        
        lines.push_back(newLine);
    }
    
    ll query(ll x) {
        while (lines.size() >= 2 && 
               lines[0].ff * x + lines[0].ss >= 
               lines[1].ff * x + lines[1].ss) {
            lines.pop_front();
        }
        
        return lines[0].ff * x + lines[0].ss;
    }
    
    void clear() {
        lines.clear();
    }
};

// dp of form:
// dp[i] = min ( dp[j] + cost(j, i)*Bi )  where j < i


void solution() {
	ll n; cin >> n;
	vi a(n+1);
	for (int i = 1; i <= n; i++) cin >> a[i];


	vi dp(n+1);
	ll mx = -1e18;

	CHT cht;
	dp[0] = 0;
	cht.addLine(0, 0);

	for (int i = 1; i <= n; i++) {
		mx = max(mx, a[i]);

		dp[i] = mx*n + cht.query(mx);
		cht.addLine(-i, dp[i]);
	}


	cout << dp[n] << endl;



}

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