#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define FF first.first
#define FS first.second
#define pb push_back
using namespace std;
const ll N=1000006, INF=1e18, P=998244353;
ll q=1, n, m, x, y, z, l, r, k, a[N], b[N], f[N], ans, o, u, Ans[N];
vector <pii> v[N], V;
stack <int> s;
main(){ios_base::sync_with_stdio(false), cin.tie(0);
cin>>n;
for(int i=1; i<=n; i++){
cin>>a[i];
if(a[i]==a[i-1])continue;
if(a[i]>a[i-1]){
s.push(a[i]-a[i-1]);
ans++;
}else{
l=s.top();s.pop();
r=a[i-1]-a[i];
while(r>l){
r-=l;
l=s.top();
s.pop();
}
if(r<l)ans++,s.push(l-r);
}
}
cout<<ans;
}
Compilation message
Main.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
16 | main(){ios_base::sync_with_stdio(false), cin.tie(0);
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
16 ms |
23756 KB |
Output is correct |
| 2 |
Correct |
15 ms |
23744 KB |
Output is correct |
| 3 |
Correct |
15 ms |
23776 KB |
Output is correct |
| 4 |
Correct |
18 ms |
24124 KB |
Output is correct |
| 5 |
Correct |
20 ms |
24392 KB |
Output is correct |
| 6 |
Correct |
25 ms |
24780 KB |
Output is correct |
| 7 |
Correct |
25 ms |
24524 KB |
Output is correct |
