oj.uz

Submission #930619

# Submission time Handle Problem Language Result Execution time Memory
930619 2024-02-20T08:18:18 Z mocha Growing Vegetables is Fun 4 (JOI21_ho_t1) C++14
0 / 100
 1 ms 6492 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mx = 2e5+5;

int n;
int a[mx], b[mx], c[mx];
int dp[2][mx];

signed main() {
	cin.tie(0);ios::sync_with_stdio(0);

	cin >> n;
	for (int i=0;i<n;i++) {
		cin >> a[i];
	}
	dp[0][0] = 0; b[0] = a[0];
	for (int i=1;i<n;i++) {
		if (a[i] > b[i-1]) {
		   dp[0][i] = dp[0][i-1];
		   b[i] = a[i];
		} else {
		   b[i] = b[i-1]+1;
		   dp[0][i] = dp[0][i-1];
		   if (b[i]-a[i] > b[i-1]-a[i-1]) {
			  dp[0][i] += b[i]-a[i]-b[i-1]+a[i-1];
		   } 
		}	   		   
	}
	dp[1][n-1] = 0;c[n-1] = a[n-1];
	for (int i=n-1;i>=0;i--) {
		if (a[i] > c[i+1]) {
		   dp[1][i] = dp[1][i+1];
		   c[i] = a[i];
		} else {
		   c[i] = c[i+1]+1;
		   dp[1][i] = dp[1][i+1];
		   if (c[i]-a[i] > c[i+1]-a[i+1]) {
			  dp[1][i] += c[i]-a[i]-c[i+1]+a[i+1];
		   } 
		}	   		   
	}

	long long ans = min(dp[0][n-1],dp[1][0]);

	for (int i=1;i<n-1;i++) {
		if (b[i]>c[i+1]) {
			ans = min(ans,
				   	dp[0][i]+dp[1][i+1]-min(b[i]-a[i],c[i+1]-a[i+1]));
		} else {
			ans = min(ans,
				dp[0][i-1]+dp[1][i]-min(b[i-1]-a[i-1],c[i]-a[i]));
		}
	}
	cout << ans << "\n";	
			
}

Subtask #1
0 / 40.0

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

Subtask #2
0 / 60.0

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