Submission #1017813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017813		Unforgettablepl	Sightseeing in Kyoto (JOI22_kyoto)	C++17	40 / 100	50 ms	33496 KiB

kyoto

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

const int INF = 1e15;

void strat1(int h,int w){
	vector<int> a(h+1);
	vector<int> b(w+1);
	for(int i=1;i<=h;i++)cin>>a[i];
	for(int i=1;i<=w;i++)cin>>b[i];
	vector<vector<int>> DP(h+1,vector<int>(w+1,INF));
	DP[1][1]=0;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(j!=1)DP[i][j]=min(DP[i][j],DP[i][j-1]+a[i]);
			if(i!=1)DP[i][j]=min(DP[i][j],DP[i-1][j]+b[j]);
		}
	}
	cout << DP[h][w] << '\n';
	exit(0);
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int h,w;
	cin >> h >> w;
	if(h<=1000 and w<=1000)strat1(h,w);
	vector<int> a(h+1);
	vector<int> b(w+1);
	for(int i=1;i<=h;i++)cin>>a[i];
	for(int i=1;i<=w;i++)cin>>b[i];
	vector<int> acti={0},actj={0};
	{
		vector<int> maxidx(1001),minidx(1001);
		for(int i=1;i<=h;i++)maxidx[a[i]]=i;
		for(int i=h;i;i--)minidx[a[i]]=i;
		for(int i=1;i<=h;i++)if(i==minidx[a[i]] or i==maxidx[a[i]])acti.emplace_back(i);
	}
	{
		vector<int> maxidx(1001),minidx(1001);
		for(int i=1;i<=w;i++)maxidx[b[i]]=i;
		for(int i=w;i;i--)minidx[b[i]]=i;
		for(int i=1;i<=w;i++)if(i==minidx[b[i]] or i==maxidx[b[i]])actj.emplace_back(i);
	}
	int sh = acti.size()-1;
	int sw = actj.size()-1;
	vector<vector<int>> DP(sh+1,vector<int>(sw+1,INF));
	DP[1][1]=0;
	for(int i=1;i<=sh;i++){
		for(int j=1;j<=sw;j++){
			if(j!=1)DP[i][j]=min(DP[i][j],DP[i][j-1]+(a[acti[i]]*(actj[j]-actj[j-1])));
			if(i!=1)DP[i][j]=min(DP[i][j],DP[i-1][j]+(b[actj[j]]*(acti[i]-acti[i-1])));
		}
	}
	cout << DP[sh][sw] << '\n';
}

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