Submission #1360822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1360822		po_rag526	Bitaro the Brave (JOI19_ho_t1)	C++17	0 / 100	0 ms	344 KiB

joi2019_ho_t1

/// Day Created: apr 27th 2026
#include <iostream>
#include <algorithm>
#include <vector>

#define fname "."
#define ll long long
#define pii pair<int, int>
#define pil pair<int, ll>
#define fi first
#define se second

using namespace std;
int n;
pii a[50005], b[50005];
int sz;
ll dp[50005];

struct CHT {
	vector<pil> vec;
	int sz=0;
	void update(int a, ll b) { // (a2-a1)/(b1-b2)>=(a3-a2)/(b2-b3) -> useless
		while(sz>=2 && 1ll*(vec[sz-1].se-vec[sz-2].se)*(vec[sz-1].fi-a)>=1ll*(b-vec[sz-1].se)*(vec[sz-2].fi-vec[sz-1].fi)) 
			vec.pop_back(), --sz;
		vec.emplace_back(a, b);
		++sz;
	}

	ll get(int x) {
		auto check=[x](const vector<pil> &vec, int m)->bool {
			return 1ll*vec[m].fi*x+vec[m].se>=1ll*vec[m+1].fi*x+vec[m+1].se;
		};
		int res=0;
		int l=0, r=sz-1;
		while(l<r) {
			int m=(l+r)>>1;
			if(m+1<sz) 
				check(vec, m)?(l=m+1, res=l):(r=m, res=r);
			else {
				res=m;
				break;
			}
		}
		return 1ll*vec[res].fi*x+vec[res].se;
	}
} *cht;

main() {
	if(fopen(fname"inp", "r")) {
		freopen(fname"inp", "r", stdin);
		freopen(fname"out", "w", stdout);
	}
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	for(int i=1; i<=n; ++i) cin>>a[i].fi>>a[i].se;
	sort(a+1, a+n+1, [] (pii a, pii b) {
		if(a.fi==b.fi) return a.se<b.se;
		return a.fi<b.fi;
	});
	for(int i=1; i<=n; ++i) {
		while(sz>0 && b[sz].se<=a[i].se) --sz;
		b[++sz]=a[i];
	}
	
	// fi1<fi2<fi3
	// se1>se2>se3
	cht=new CHT();
	cht->update(b[1].se, 0);
	for(int i=1; i<=sz; ++i) {
		dp[i]=cht->get(b[i].fi);
		if(i<sz) 
			cht->update(b[i+1].se, dp[i]);
	}
	cout<<dp[sz];
}

Compilation message (stderr)

joi2019_ho_t1.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main() {
      | ^~~~
joi2019_ho_t1.cpp: In function 'int main()':
joi2019_ho_t1.cpp:50:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |                 freopen(fname"inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t1.cpp:51:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |                 freopen(fname"out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50