Submission #859230

#	Time	Username	Problem	Language	Result	Execution time	Memory
859230		willychan	Sightseeing in Kyoto (JOI22_kyoto)	C++14	100 / 100	23 ms	3156 KiB

kyoto

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds



int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int h,w;cin>>h>>w;
	vector<pair<int,int> > ah;
	vector<pair<int,int> > bh;
	for(int i=1;i<=h;i++){
		int a;cin>>a;
		while(ah.size()>=2){
			int g = ah.size();
			if(1LL*(ah[g-1].first-ah[g-2].first)*(a-ah[g-1].second)<=1LL*(i-ah[g-1].first)*(ah[g-1].second-ah[g-2].second)) ah.pop_back();
			else break;
		}
		ah.push_back({i,a})	;
	}
	for(int i=1;i<=w;i++){
		int a;cin>>a;
		while(bh.size()>=2){
			int g = bh.size();
			if(1LL*(bh[g-1].first-bh[g-2].first)*(a-bh[g-1].second)<=1LL*(i-bh[g-1].first)*(bh[g-1].second-bh[g-2].second)) bh.pop_back();
			else break;
		}
		bh.push_back({i,a})	;
	}
	
	int x=0;int y=0;
	ll ans = 0;
	while(ah[x].first!=h && bh[y].first!=w){
		if(1LL*(ah[x+1].second-ah[x].second)*(bh[y+1].first-bh[y].first)<1LL*(bh[y+1].second-bh[y].second)*(ah[x+1].first-ah[x].first)){ans+=(1LL*bh[y].second*(ah[x+1].first-ah[x].first));x++;}
		else{ans+=(1LL*ah[x].second*(bh[y+1].first-bh[y].first));y++;}
	}
	if(ah[x].first!=h){
		ans+=1LL*bh[y].second*(h-ah[x].first);
	}
	if(bh[y].first!=w){
		ans+=1LL*ah[x].second*(w-bh[y].first);
	}
	cout<<ans<<"\n";
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60