Submission #1356922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1356922		pqhxapple	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	0 / 100	1096 ms	25052 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b)        for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b)       for (int i = (a), _b = (b); i >= _b; --i)
#define REP(i, n)           for (int i = (0), _n = (n); i < _n; ++i)
#define MASK(x)             (1LL << (x))
#define ON(mask, i)         (((mask) >> (i)) & (1LL))
#define ALL(x)              begin(x), end(x)
#define el                  cout << '\n'

template <class X, class Y> inline bool maximize(X &x, const Y &y) { return (x < y) ? x = y, 1 : 0; }
template <class X, class Y> inline bool minimize(X &x, const Y &y) { return (x > y) ? x = y, 1 : 0; }

constexpr int MAXN = 2e5 + 10;
int n;
int a[MAXN];
int b[MAXN], c[MAXN];

void load_input(void)
{
    cin >> n;
    FOR(i, 1, n) cin >> a[i];
}

void prepare(void)
{
    FOR(i, 1, n)    b[i] = max(b[i - 1] + 1, a[i]);
    FORD(i, n, 1)   c[i] = max(c[i + 1] + 1, a[i]);

//    FOR(i, 1, n) cout << b[i] << ' ';el;
//    FOR(i, 1, n) cout << c[i] << ' ';el;

}

namespace subtask1
{
    int d[2002], e[2002];
    int calc(int L, int R, int arr[])
    {
        if (L > R) return 0;
        if (L == R) return arr[L];

        int mn = *min_element(arr + L, arr + R + 1);

//        cout << L << ' ' << R << '\n';
//        FOR(i, L, R) cout << arr[i] << ' ';el;

        int res = mn;
        FOR(i, L, R)
        {
            arr[i] -= mn;
            if (arr[i] == 0) continue;

            int mn = arr[i];
            int j = i;
            while (j < R && arr[j + 1] > 0) ++j;

            res = res + calc(i, j, arr);
            i = j;
        }

        return res;
    }

    void solve(void)
    {
        if (!(n <= 2e3)) return;

        int res = 1e9;
        FOR(i, 1, n)
        {
            FOR(j, 1, n)
            if (j <= i) d[j] = b[j] - a[j];
            else e[j] = c[j] - a[j];

            if (b[i] == c[i + 1])
            {
                if (i <= n / 2)
                    FOR(j, 1, i) ++d[j];
                else
                    FOR(j, i + 1, n) ++e[j];
            }

            minimize(res, calc(1, i, d) + calc(i + 1, n, e));
        }

        cout << res << '\n';

        cerr << "[2]\n";
        exit(0);
    }
}

void process(void)
{
    prepare();

    subtask1::solve();
}

signed main(void)
{
    cin.tie(nullptr)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);

    #define task "B"
    if (fopen(task".INP", "r"))
    {
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    int testcase = 1;
    while (testcase--)
    {
        load_input();
        process();
    }

    return 1 ^ 1;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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