oj.uz

Submission #1109795

# Submission time Handle Problem Language Result Execution time Memory
1109795 2024-11-07T15:33:26 Z Tsagana Skyline (IZhO11_skyline) C++14
100 / 100
 44 ms 49984 KB 
#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define lnl long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int antiloop = 0;

int dp[305][205][205];
int a[305];

void solve () {
	int n; cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];

	for (int i = 1; i <= 301; i++)
	for (int j = 0; j <= 201; j++)
	for (int k = 0; k <= 201; k++)
		dp[i][j][k] = 1e9;

	for (int i = 0; i <= a[1]; i++) dp[2][a[1]-i][a[2]] = dp[1][0][a[1]-i] = i*3;

	for (int i = 2; i <= n; i++) {
		for (int j = a[i-1]; j >= 0; j--)
		for (int k = a[i];   k >= 0; k--)
			dp[i][j][k] = min(dp[i][j][k], dp[i][j][k+1]+3);

		for (int j = a[i-1]; j >= 0; j--)
		for (int k = a[i];   k >= 0; k--)
			dp[i][j][k] = min(dp[i][j][k], dp[i][j+1][k+1]+5);

		if (i != n) {
			for (int j = min({a[i-1], a[i], a[i+1]}); j >= 0; j--)
			for (int k = a[i]; k >= j; k--)
				dp[i+1][k-j][a[i+1]-j] = min(dp[i+1][k-j][a[i+1]-j], dp[i][j][k] + j*7);
		}
	}
	cout << dp[n][0][0];
}
int main() {IOS solve(); return 0;}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 49744 KB Output is correct
2 Correct 11 ms 49744 KB Output is correct
3 Correct 11 ms 49948 KB Output is correct
4 Correct 11 ms 49744 KB Output is correct
5 Correct 10 ms 49744 KB Output is correct
6 Correct 11 ms 49744 KB Output is correct
7 Correct 11 ms 49984 KB Output is correct
8 Correct 11 ms 49744 KB Output is correct
9 Correct 11 ms 49744 KB Output is correct
10 Correct 12 ms 49744 KB Output is correct
11 Correct 16 ms 49744 KB Output is correct
12 Correct 12 ms 49980 KB Output is correct
13 Correct 17 ms 49744 KB Output is correct
14 Correct 19 ms 49744 KB Output is correct
15 Correct 38 ms 49760 KB Output is correct
16 Correct 33 ms 49744 KB Output is correct
17 Correct 43 ms 49744 KB Output is correct
18 Correct 44 ms 49744 KB Output is correct
19 Correct 40 ms 49744 KB Output is correct
20 Correct 44 ms 49760 KB Output is correct