Submission #335747

#	Time	Username	Problem	Language	Result	Execution time	Memory
335747		nafis_shifat	Discharging (NOI20_discharging)	C++14	100 / 100	446 ms	25868 KiB

Discharging

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e6+5;
const ll inf=1e18;


vector<ll> m,b;

ll f(int i, ll x) { return m[i] * x + b[i]; }


bool bad(int f1,int f2,int f3) {
	return __int128(b[f3] - b[f1]) * (m[f1] - m[f2]) <= __int128(b[f2] - b[f1]) * (m[f1] - m[f3]);
}

void add(ll m_, ll b_) {
	m.push_back(m_);
	b.push_back(b_);

	int sz = m.size();

	while(sz >=3 && bad(sz-3,sz-2,sz-1)) {
		m.erase(m.end() - 2);
		b.erase(b.end() - 2);
		sz--;
	}
}

ll query(ll x) {
	ll ans = inf;

	int lo = 0;
	int hi = m.size() - 1;

	while(lo <= hi) {
		int mid1 = lo + (hi - lo) / 3;
		int mid2 = hi - (hi - hi) / 3;

		ll v1 = f(mid1,x);
		ll v2 = f(mid2,x);

		if(v1 <= v2) {
			ans = min(ans,v1);
			hi = mid2 - 1;
		} else {
			ans = min(ans,v2);
			lo = mid1 + 1;
		}
	}

	return ans;
}



int main() {
	int n;
	cin>>n;

	ll t[n+1];


	for(int i = 1; i <= n; i++) cin>>t[i];


	ll dp[n+1];

    dp[0] = 0;

    add(0,0);
    ll cm = 0;
    int lp = 1;


    for(int i = 1; i <= n; i++) {
    	if(t[i] >= cm) {
    		cm = t[i];
    		for(; lp < i; lp++) {
    			add(-lp,dp[lp]);
    		}
    	}
    	dp[i] = query(cm) + cm * n;
    	
    }

    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