oj.uz

Submission #765120

# Submission time Handle Problem Language Result Execution time Memory
765120 2023-06-24T08:27:46 Z ymm Sightseeing in Kyoto (JOI22_kyoto) C++17
0 / 100
 6 ms 3916 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 2020;
ll A[N], B[N];
ll cA[N], cB[N];
ll dp[N][N];
int n, m;

void input(int &n, ll *A, ll *cA)
{
	Loop (i,0,n) {
		cin >> A[i];
		while (i >= 2) {
			if (A[i-2] > A[i-1] || A[i-1] < A[i])
				break;
			A[i-1] = A[i];
			cA[i-2]++;
			--i;
			--n;
		}
		cA[i]=1;
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	input(n, A, cA);
	input(m, B, cB);
	Loop (i,0,n) Loop (j,0,m) {
		if (!i && !j)
			continue;
		ll ans = LONG_LONG_MAX;
		if (i)
			ans = min(ans, dp[i-1][j] + B[j] * cA[i-1]);
		if (j)
			ans = min(ans, dp[i][j-1] + A[i] * cB[j-1]);
		dp[i][j] = ans;
	}
	cout << dp[n-1][m-1] << '\n';
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 3 ms 3916 KB Output is correct
4 Incorrect 6 ms 2140 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

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