제출 #1153782

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153782		gelastropod	Po (COCI21_po)	C++20	70 / 70	23 ms	2492 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
	int n, a;
	cin >> n;
	vector<int> A;
	for (int i = 0; i < n; i++) {
		cin >> a;
		A.push_back(a);
	}
	vector<int> diff;
	diff.push_back(A[0]);
	for (int i = 0; i < n - 1; i++) {
		diff.push_back(A[i + 1] - A[i]);
	}
	diff.push_back(-A.back());
	stack<int> stk;
	int ans = 0;
	for (int i = 0; i <= n; i++) {
		if (diff[i] > 0)
			stk.push(diff[i]);
		if (diff[i] < 0) {
			while (!stk.empty() && - diff[i] >= stk.top()) {
				diff[i] += stk.top();
				stk.pop();
				ans++;
			}
			if (!stk.empty() && diff[i] != 0)
				stk.top() += diff[i], ans++;
		}
	}
	cout << ans << '\n';
}

• Subtask 1: 70 / 70