Submission #1160358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160358		dwuy	Cultivation (JOI17_cultivation)	C++20	100 / 100	896 ms	1560 KiB

cultivation

#include <algorithm>
#include <iostream>
using ll = long long;

const int N = 300;
struct pt
{
    int x, y;
} a[N];
struct el
{
    ll a[N], b[N];
    int f[N][N], l, r;
} p, q, c;
int v[N];
int main()
{
#define taskname "NGRASS"
    if (fopen(taskname ".inp", "r"))
    {
        freopen(taskname ".inp", "r", stdin);
        freopen(taskname ".out", "w", stdout);
    }
    int h, w, n, m;
    ll ans = 1e18;
    scanf("%d%d%d", &h, &w, &n);

    for (int i = 0; i < n; i++)
        scanf("%d%d", v + i, &a[i].x), a[i].y = v[i];

    std::sort(v, v + n), v[m = std::unique(v, v + n) - v] = 1e9, std::sort(a, a + n, [](pt &x, pt &y)
                                                                           { return x.x < y.x; });

    for (int i = 0; i < n; i++)
        a[i].y = std::lower_bound(v, v + m, a[i].y) - v;

    for (int l = 0, r, i, t; l < m; l++)
        for (r = l; r < m; q.f[l][r++] = w - a[t].x)
            for (i = 0, t = -1; i < n; i++)
                if (l <= a[i].y && a[i].y <= r)
                    ~t ? c.f[l][r] = std::max(c.f[l][r], a[i].x - a[t].x - 1) : p.f[l][r] = a[i].x - 1, t = i;

    auto work = [&](int t)
    {
        int i = 0, j = 0;
        ll k;
        auto cl = [&](el &s)
        {
            s.l = 0, s.r = -1;
        };
        auto ad = [&](el &s)
        {
            int x = j < i ? s.f[j][i - 1] : 1e9;

            while (s.l <= s.r && s.a[s.r] <= x)
                s.r--;

            s.a[++s.r] = x, s.b[s.r] = k;
        };
        auto qr = [&](el &s) -> ll
        {
            while (s.l <= s.r && s.b[s.l] <= k - h)
                s.l++;

            return s.a[s.l];
        };

        for (cl(p), cl(q), cl(c); i < m; i += v[i] == k, j += v[j] + t == k)
            k = std::min(v[i], v[j] + t), ad(p), ad(q), ad(c),
            ans = std::min(ans, std::max(qr(p) + qr(q), qr(c)) + t);

        for (; j < m; j++)
            k = v[j] + t, ad(p), ad(q), ad(c),
            ans = std::min(ans, std::max(qr(p) + qr(q), qr(c)) + t);
    };

    for (int i = 0; i < m; i++)
        for (int j = i; j < m; j++)
            work(v[j] - v[i]), work(v[i] - v[j] + h), work(v[j] - v[i] + h);

    printf("%lld", ans - 1);
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(taskname ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen(taskname ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d%d%d", &h, &w, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%d%d", v + i, &a[i].x), a[i].y = v[i];
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20
• Subtask 6: 20 / 20