oj.uz

Submission #966195

# Submission time Handle Problem Language Result Execution time Memory
966195 2024-04-19T13:56:27 Z happy_node Sightseeing in Kyoto (JOI22_kyoto) C++17
10 / 100
 4 ms 8284 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;
				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();
 
	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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 4 ms 8284 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 4 ms 8284 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 2 ms 4700 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 4 ms 8284 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 4 ms 8284 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Incorrect 2 ms 4700 KB Output isn't correct
32 Halted 0 ms 0 KB -