Submission #567406

#	Time	Username	Problem	Language	Result	Execution time	Memory
567406		jamezzz	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	426 ms	16308 KiB

kyoto

#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define fi first
#define se second
#define LINF 1023456789123456789
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<double,ii> iii;

#define maxn 100005

int h,w;
ll a[maxn],b[maxn];
priority_queue<iii,vector<iii>,greater<iii>> pqh,pqv;
set<int> s1,s2;

int main(){
	sf("%d%d",&h,&w);
	for(int i=1;i<=h;++i){
		sf("%lld",&a[i]);
		s1.insert(i);
		if(i>1)pqh.push({a[i-1]-a[i],{i-1,i}});
	}
	for(int i=1;i<=w;++i){
		sf("%lld",&b[i]);
		s2.insert(i);
		if(i>1)pqv.push({b[i-1]-b[i],{i-1,i}});
	}
	
	pqh.push({LINF,{-1,-1}});
	pqv.push({LINF,{-1,-1}});
	
	ll ans=0;
	while(pqh.size()+pqv.size()>2){
		if(pqh.top().fi<pqv.top().fi){
			ii p=pqh.top().se;pqh.pop();
			if(!s1.count(p.fi)||!s1.count(p.se))continue;//already removed adjacent thing
			int l=p.fi,r=-1;
			auto it=s1.find(p.se);
			if(it!=--s1.end())r=*next(it);
			s1.erase(it);
			
			if(r!=-1){
				pqh.push({(double)(a[l]-a[r])/(r-l),{l,r}});
			}
			else ans+=b[*(--s2.end())]*(p.se-p.fi);
		}
		else{
			ii p=pqv.top().se;pqv.pop();
			if(!s2.count(p.fi)||!s2.count(p.se))continue;//already removed adjacent thing
			int l=p.fi,r=-1;
			auto it=s2.find(p.se);
			if(it!=--s2.end())r=*next(it);
			s2.erase(it);
			
			if(r!=-1){
				pqv.push({(double)(b[l]-b[r])/(r-l),{l,r}});
			}
			else ans+=a[*(--s1.end())]*(p.se-p.fi);
		}
	}
	
	pf("%lld\n",ans);
}

Compilation message (stderr)

kyoto.cpp: In function 'int main()':
kyoto.cpp:21:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  sf("%d%d",&h,&w);
      |    ^
kyoto.cpp:23:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   sf("%lld",&a[i]);
      |     ^
kyoto.cpp:28:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   sf("%lld",&b[i]);
      |     ^

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