oj.uz

Submission #966188

# Submission time Handle Problem Language Result Execution time Memory
966188 2024-04-19T13:51:53 Z happy_node Sightseeing in Kyoto (JOI22_kyoto) C++17
0 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX=1005;
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;
			}
		}
		mn=2e9;
		for(int i=H-1;i>=0;i--) {
			if(mn>A[i]) {
				mn=A[i];
				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(H);
		int mn=2e9;
		for(int i=0;i<W;i++) {
			if(mn>B[i]) {
				mn=B[i];
				C[i]=1;
			}
		}
		mn=2e9;
		for(int i=W-1;i>=0;i--) {
			if(mn>B[i]) {
				mn=B[i];
				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();

	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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 1 ms 604 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 1 ms 604 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -