Submission #1300139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300139		khoianh	Discharging (NOI20_discharging)	C++20	100 / 100	113 ms	33024 KiB

Discharging

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int mn = 1e6 + 5;
ll n, a[mn];

struct line{
	ll m, b;
	ld x;
	line(ll m_ = 0, ll b_ = 0, ld x_ = -1e30){
		m = m_;
		b = b_;
		x = x_;
	}
};

ld intersect(const line &l1, const line &l2){
	return (ld)(l2.b - l1.b) / (ld)(l1.m - l2.m);
}

struct node{
	ll val, l, r;
};
vector<node> v;

struct convexhulltrick{
	deque<line> hull;
	void add_line(ll m, ll b){
		line cur(m, b);
		if(!hull.empty() && hull.back().m == m){
			if(hull.back().b <= b) return;
			hull.pop_back();
		}
		while(!hull.empty()){
			ld ix = intersect(hull.back(), cur);
			if(ix <= hull.back().x) hull.pop_back();
			else{
				cur.x = ix;
				break;
			}
		}
		hull.push_back(cur);
	}
	
	ll query(ll x){
		while(hull.size() >= 2 &&  hull[1].x <= (ld)x) hull.pop_front();
		line l = hull.front();
//		cout << l.m << " " << l.b << "*\n";
		return l.m * x + l.b;
	}
};

void solve(){
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	for(int i = 1; i <= n; ++i){
		if(v.empty() || v.back().val < a[i]) v.push_back({a[i], i, i});
		else ++v.back().r;
	}
	convexhulltrick cht;
	cht.add_line(0, 0);
	ll ans;
	for(auto i : v){
//		cout << i.val << " " << i.r << "\n";
		ll dp = cht.query(i.val) + i.val * n;
////		cout << dp << "\n";
		ans = dp;
		cht.add_line(-i.r, dp);
	}
	cout << ans;
    return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	if(fopen(".INP", "r")) {
		freopen(".INP", "r", stdin);
		freopen(".OUT", "w", stdout);
	}
	int testCase = 1;
	//cin >> testCase;
	while(testCase--) solve();
}

Compilation message (stderr)

Discharging.cpp: In function 'int main()':
Discharging.cpp:79:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |                 freopen(".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Discharging.cpp:80:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |                 freopen(".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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