Submission #983986

#	Time	Username	Problem	Language	Result	Execution time	Memory
983986		vjudge1	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	1 ms	348 KiB

Main

/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_[1]t;

//// order_of_key(k) : ���������� ���������� ���������, ������� ������ ������ ������ �������� k �� ����� O(logn).
//// find_by_order(k) : ���������� �������� � k-�� �������� (������ �� ����) � ������ �� ����� O(logn).
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define str string
#define ld long double
#define fi first
#define pb push_back
#define pf push_front
#define se second
#define all(a) a.begin() , a.end()
#define run_vasya_run ios_base::sync_with_stdio(0) , cin.tie(0) ,cout.tie(0)
#define ull unsigned long long
#define open freopen ("cereal.in", "r", stdin);
#define close freopen("cereal.out", "w", stdout);
#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> order_set;
const ll mod = 998244353;
const ll N = 1e6 + 100;
ll lcm(ll a, ll b)
{
    return (a * b) / __gcd(a, b);
}
ll binpow(ll a, ll n)
{
    if(n < 1)
    {
        return 1;
    }
    if(n == 1)
    {
        return a % mod;
    }
    ll b = binpow(a, n / 2);
    b = (b * b) % mod;
    if(n % 2 == 1)
    {
        b = (b * a) % mod;
    }
    return b % mod;
}
main()
{
    run_vasya_run;
    //open ; close;
    ///kam kam podgon
    ll _;
    _ = 1;
    //cin >> _;
    while(_ --)
    {
        ll n , answer , kol;
        cin >> n;
        pair<ll,ll>dp[n + 18] , dp1[n + 19];
        ll a[n + 18] , b[n + 19];
        for(int i = 1;i <= n;i ++)
        {
            cin >> a[i];
            b[i] = a[i];
        }
        for(int i = 0;i <= n + 10;i ++)
        {
            dp[i].fi = 0;
            dp1[i].fi = 0;
            dp[i].se = 0;
            dp1[i].se = 0;
        }
        dp[1].fi = 0;
        dp[1].se = a[1];
        for(int i = 2;i <= n;i ++)
        {
            dp[i].fi = dp[i - 1].fi;
            if(a[i] <= a[i - 1])
            {
                dp[i].fi += (a[i - 1] + 1 - a[i]);
                a[i] += (a[i - 1] + 1 - a[i]);
            }
            dp[i].se = a[i];
        }
        dp1[n].fi = 0;
        dp1[n].se = b[n];
        for(int i = n - 1;i >= 1;i --)
        {
            dp1[i].fi = dp1[i + 1].fi;
            if(b[i] <= b[i + 1])
            {
                dp1[i].fi += (b[i + 1] - b[i] + 1);
                b[i] += (b[i + 1] - b[i] + 1);
            }
            dp1[i].se = b[i];
        }
        answer = 1e18;
        for(int i = 1;i <= n;i ++)
        {
            kol = 0;
            if(dp[i].se == dp1[i + 1].se)
            {
                kol = 1;
            }
            answer = min(answer , max(min(dp[i].fi , dp1[i + 1].fi) + kol , max(dp[i].fi , dp1[i + 1].fi)));
        }
        cout << answer;
    }
}

Compilation message (stderr)

Main.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main()
      | ^~~~

• Subtask 1: 0 / 40
• Subtask 2: 0 / 60