oj.uz

Submission #366348

# Submission time Handle Problem Language Result Execution time Memory
366348 2021-02-14T03:52:53 Z _eve Po (COCI21_po) C++17
50 / 70
 1000 ms 2668 KB 
#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

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.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 82 ms 876 KB Output is correct
5 Correct 144 ms 1260 KB Output is correct
6 Execution timed out 1087 ms 1772 KB Time limit exceeded
7 Execution timed out 1087 ms 2668 KB Time limit exceeded