Submission #567144

#	Time	Username	Problem	Language	Result	Execution time	Memory
567144		jamielim	Sightseeing in Kyoto (JOI22_kyoto)	C++14	40 / 100	2061 ms	204816 KiB

kyoto

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

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int h,w;
ll a[100005],b[100005];
ll pa[100005],sa[100005],pb[100005],sb[100005];
ll dp[5005][5005];

int main(){
	scanf("%d%d",&h,&w);
	pa[0]=LLINF;pb[0]=LLINF;
	sa[h+1]=LLINF;sb[w+1]=LLINF;
	for(int i=1;i<=h;i++){
		scanf("%lld",&a[i]);
		pa[i]=min(pa[i-1],a[i]);
	}
	for(int i=h;i>=1;i--)sa[i]=min(sa[i+1],a[i]);
	for(int i=1;i<=w;i++){
		scanf("%lld",&b[i]);
		pb[i]=min(pb[i-1],b[i]);
	}
	for(int i=w;i>=1;i--)sb[i]=min(sb[i+1],b[i]);
	vector<pair<ll,ll> > A,B;
	for(int i=1;i<=h;i++){
		if(a[i]<pa[i-1]||a[i]<sa[i+1])A.pb(a[i],i);
	}
	for(int i=1;i<=w;i++){
		if(b[i]<pb[i-1]||b[i]<sb[i+1])B.pb(b[i],i);
	}
	
	h=SZ(A);w=SZ(B);
	dp[0][0]=0;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(i==0&&j==0)continue;
			dp[i][j]=LLINF;
			if(i!=0)dp[i][j]=min(dp[i][j],dp[i-1][j]+B[j].fi*(A[i].se-A[i-1].se));
			if(j!=0)dp[i][j]=min(dp[i][j],dp[i][j-1]+A[i].fi*(B[j].se-B[j-1].se));
		}
	}
	printf("%lld",dp[h-1][w-1]);
}

Compilation message (stderr)

kyoto.cpp: In function 'int main()':
kyoto.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%d%d",&h,&w);
      |  ~~~~~^~~~~~~~~~~~~~
kyoto.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |   scanf("%lld",&a[i]);
      |   ~~~~~^~~~~~~~~~~~~~
kyoto.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%lld",&b[i]);
      |   ~~~~~^~~~~~~~~~~~~~

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