Submission #366348

#	Time	Username	Problem	Language	Result	Execution time	Memory
366348		_eve	Po (COCI21_po)	C++17	50 / 70	1087 ms	2668 KiB

Main

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define ll long long
#define ld long double
#define pl pair<ll,ll>
#define pi pair<int,int>
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define int ll
const int N = 100505,P = 998244353;
int n,a[N];
int solve(int l,int r){
    if(l>r)return 0;
    if(l==r)return (a[l]>0);
    int p,mn=INT_MAX;
    for(int i=l;i<=r;i++){
        if(mn > a[i]){
            mn=a[i],p=i;
        }
    }
    for(int i=l;i<=r;i++)a[i]-=mn;
    return min((mn?1:0)+solve(l,p-1)+solve(p+1,r),r-l+1);
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    cout<<solve(1,n); 
}

Compilation message (stderr)

Main.cpp: In function 'long long int solve(long long int, long long int)':
Main.cpp:27:43: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |     return min((mn?1:0)+solve(l,p-1)+solve(p+1,r),r-l+1);
      |                                      ~~~~~^~~~~~~

• Subtask 1: 50 / 70