Submission #966201

#	Time	Username	Problem	Language	Result	Execution time	Memory
966201		happy_node	Sightseeing in Kyoto (JOI22_kyoto)	C++17	40 / 100	100 ms	128180 KiB

kyoto

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MX=4005;
int H,W;
ll dp[MX][MX];
 
int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
 
	cin>>H>>W;
	vector<ll> A(H),B(W);
	for(int i=0;i<H;i++) cin>>A[i];
	for(int i=0;i<W;i++) cin>>B[i];
 
	vector<pair<ll,ll>> a, b;
	{
		vector<bool> C(H);
		int mn=2e9;
		for(int i=0;i<H;i++) {
			if(mn>A[i]) {
				mn=A[i];
				C[i]=1;
				while(i+1<H && A[i+1]==A[i]) i++;
				C[i]=1;
			}
		}
		mn=2e9;
		for(int i=H-1;i>=0;i--) {
			if(mn>A[i]) {
				mn=A[i];
				C[i]=1;
				while(i-1>=0 && A[i-1]==A[i]) i--;
				C[i]=1;
			}
		}
		int lst=0;
		for(int i=0;i<H;i++) 
			if(C[i]) {
				a.push_back({A[i],i-lst});
				lst=i;
			}
	}
 
	{
		vector<bool> C(W);
		int mn=2e9;
		for(int i=0;i<W;i++) {
			if(mn>B[i]) {
				mn=B[i];
				C[i]=1;
				while(i+1<W && B[i+1]==B[i]) i++;
				C[i]=1;
			}
		}
		mn=2e9;
		for(int i=W-1;i>=0;i--) {
			if(mn>B[i]) {
				mn=B[i];
				C[i]=1;
				while(i-1>=0 && B[i-1]==B[i]) i--;
				C[i]=1;
			}
		}
		int lst=0;
		for(int i=0;i<W;i++) 
			if(C[i]) {
				b.push_back({B[i],i-lst});
				lst=i;
			}
	}
 
	H=a.size();
	W=b.size();

	assert(H<=4000 && W<=4000);
 
	for(int i=0;i<=H;i++) {
		for(int j=0;j<=W;j++) {
			dp[i][j]=2e18;
		}
	}
 
	dp[0][0]=0;
	for(int i=0;i<H;i++) {
		for(int j=0;j<W;j++) {
			if(i+1<H)
				dp[i+1][j]=min(dp[i+1][j],dp[i][j]+b[j].first*a[i+1].second);
			if(j+1<W)
				dp[i][j+1]=min(dp[i][j+1],dp[i][j]+a[i].first*b[j+1].second);
		}	
	}
 
	cout<<dp[H-1][W-1]<<'\n';
}

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