Submission #544542

#	Time	Username	Problem	Language	Result	Execution time	Memory
544542		benson1029	Sightseeing in Kyoto (JOI22_kyoto)	C++14	100 / 100	548 ms	18968 KiB

kyoto

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

int h,w;
long long a[2][100005];
long long l[2][100005], r[2][100005];
set< pair<double, pair<int,int> > > st;

double calc(int id, int y) {
	int x = l[id][y];
	return ((double)(a[id][y]-a[id][x])) / (y-x);
}

int main() {
	ios::sync_with_stdio(false);
	cin >> h >> w;
	l[0][h+1] = h;
	for(int i=1; i<=h; i++) {
		cin >> a[0][i];
		l[0][i] = i-1; r[0][i] = i+1;
	}
	l[1][w+1] = w;
	for(int i=1; i<=w; i++) {
		cin >> a[1][i];
		l[1][i] = i-1; r[1][i] = i+1;
	}
	for(int i=2; i<=h; i++) {
		 st.insert({calc(0, i), {0, i} });
	}
	for(int i=2; i<=w; i++) {
		st.insert({{calc(1, i), {1, i} }});
	}
	long long ans = 0;
	for(int i=0; i<h+w-2; i++) {
		int id = (*prev(st.end())).second.first;
		int y = (*prev(st.end())).second.second;
				
		if(id==0) {
			if(r[0][y] > h) {
				ans += (a[1][l[1][w+1]] * (y - l[0][y]));
			} else {
				st.erase({calc(0, r[0][y]), {0, r[0][y]} });
			}
		} else {
			if(r[1][y] > w) {
				ans += (a[0][l[0][h+1]] * (y - l[1][y]));
				 
			} else {
				st.erase({calc(1, r[1][y]), {1, r[1][y]} });
			}
		}
		
		st.erase(prev(st.end())); 
		l[id][r[id][y]] = l[id][y];
		r[id][l[id][y]] = r[id][y];
		
		if(r[id][y] <= (id==0?h:w) && l[id][y] > 0) {
			st.insert({calc(id, r[id][y]), {id, r[id][y]} });
		}
	}
	
	cout << ans << "\n";
}

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