제출 #1196000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196000		LGQ_A3K25	Cultivation (JOI17_cultivation)	C++20	15 / 100	15 ms	440 KiB

cultivation

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define db double
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*b / __gcd(a,b)
#define I first
#define II second
#define pb push_back
#define ii pair<int,int>
const int INF = 2 * 1e18;
const int N = 2e5 + 1;
const int MOD = 1e9 + 7;
int n, m, k;
namespace sub1
{
int a[41][41], b[41][41];
    int main()
    {
        vector<ii> s;
        for (int i = 0; i < k; i++)
        {
            int u, v; cin >> u >> v;
            s.pb({u, v});
            a[u][v] = 1;
        }
        int ans = INF;
        for (int x = 0; x <= 40; x++)
            for (int y = 0; y <= 40; y++)
                if (x + y <= ans)
        {
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++) b[i][j] = a[i][j];
            for (auto [u, v] : s)
            {
                int ox = 1, oy = 1;
                for (int i = 1; i <= max(x, y) && (ox | oy); i++)
                {
                    if (ox && i <= x)
                    {
                        if (u - i == 0 || b[u - i][v] == 1) ox = 0; else
                        b[u - i][v] = 1;
//                        if (x == 4 && y == 5) cout << u - i << ' ' << v << '\n';
                    }
                    if (oy && i <= y)
                    {
                        if (u + i == n + 1 || b[u + i][v] == 1) oy = 0; else
                        b[u + i][v] = 1;
                    }
                }
            }
//            if (x == 4 && y == 5)
//            {
//                for (int i = 1; i <= n; i++)
//                    for (int j = 1; j <= m; j++) cout << (b[i][j]) << (j == m ? '\n' : ' ');
//            }
            int l = 0, r = 0, mid = 0, ok = 1;
            for (int i = 1; i <= n; i++)
            {
                int last = 0, nxt = m + 1, ok1 = 0;
                for (int j = 1; j <= m; j++)
                {
                    if (b[i][j])
                    {
                        ok1 = 1;
                        if (!last) l = max(l, j - 1); else
                            mid = max(mid, j - last - 1);
                        last = j;
                    }
                    int jj = m - j + 1;
                    if (b[i][jj])
                    {
                        if (nxt == m + 1) r = max(r, nxt - jj - 1); else
                            mid = max(mid, nxt - jj - 1);
                        nxt = jj;
                    }
                }
                if (!ok1)
                {
                    ok = 0;
                    break;
                }
            }
            if (ok)
            {
                mid = max(0ll, mid - l - r);
                ans = min(ans, x + y + l + r + mid);
            }
//            if (ans == 16) cout << x << ' ' << y << '\n';
        }
        cout << ans;
        return 0;
    }
}
namespace sub2
{
int a[41][41];
    bool cmp(ii x, ii y)
    {
        if (x.II < y.II) return true; else
            if (x.II == y.II) return x.I < y.I;
        return false;
    }
    int main()
    {
        vector<ii> s;
        int mn = INF, mx = 0;
        for (int i = 1; i <= k; i++)
        {
            int u, v;
            cin >> u >> v;
            s.pb({u, v});
            mx = max(mx, u);
            mn = min(mn, u);
        }
        mn--, mx = n - mx;
        sort(s.begin(), s.end(), cmp);
        vector<int> t;
        for (int i = 0; i < k; i++)
        {
            if (s[i].I > 1) t.pb(s[i].I - 1);
            if (s[i].I < n) t.pb(n - s[i].I);
            int MN = INF;
            for (int j = 0; j < i; j++)
                if (s[i].I + mx < s[j].I - mn - 1)
                {
                    MN = min(MN, s[j].I);
//                    t.pb({s[j].I - mn - 1 - s[i].I});
//                    t.pb({s[j].I - (s[i].I + mx) - 1});
//                    break;
                }
            t.pb({MN - mn - 1 - s[i].I});
            t.pb({MN - (s[i].I + mx) - 1});
            MN = INF;
            for (int j = i + 1; j < k; j++)
                if (s[i].I + mx < s[j].I - mn - 1)
                {
                    MN = min(MN, s[j].I);
//                    t.pb({s[j].I - mn - 1 - s[i].I});
//                    t.pb({s[j].I - (s[i].I + mx) - 1});
//                    break;
                }
            t.pb({MN - mn - 1 - s[i].I});
            t.pb({MN - (s[i].I + mx) - 1});
        }
        t.pb(0);
        sort(t.begin(), t.end());
        t.resize(unique(t.begin(), t.end()) - t.begin());
        int ans = INF;
//        cout << t.size() << '\n';
        for (auto x : t)
            for (auto y : t)
        {
            if (x + y > ans) break;
//            cout << x << ' ' << y << '\n';
            int cur = x + y;
            vector<array<int, 3> > p;
            vector<array<int, 2> > b;
            for (auto [u, v] : s)
            {
                int l = max(1ll, u - x), r = min(n, u + y);
                b.pb({l, r});
                p.pb({v, l, r});
            }
            sort(b.begin(), b.end());
            if (b[0][0] != 1) continue;
            int R = b[0][2], ok = 1;
            for (int i = 1; i < k; i++)
            {
//                if (x == 2 && y == 0) cout << b[i][0] << ' ' << b[i][1] << '\n';
                if (b[i][0] > R + 1)
                {
                    ok = 0;
                    break;
                } else R = b[i][1];
            }
            if (!ok || R != n) continue;
//            if (x == 2 && y == 0) cout << "fwef";
            int l = 0, r = 0, mid = 0;
            for (int i = 0; i < k; i++)
            {
                int u = p[i][1], v = p[i][2];
                for (int j = 0; j < i && (u <= v); j++)
                {
                    int c = p[j][1], d = p[j][2];
                    if (c <= u && d >= u)
                    {
                        mid = max(mid, p[j][0] - p[i][0] - 1);
                        u = d + 1;
                    } else
                    if (c <= v && d >= v)
                    {
                        mid = max(mid, p[j][0] - p[i][0] - 1);
                        v = c - 1;
                    }
                }
                if (u <= v) l = max(l, p[i][0] - 1);
            }
            for (int i = k - 1; i >= 0; i--)
            {
                int u = p[i][1], v = p[i][2];
                for (int j = i + 1; j < k && (u <= v); j++)
                {
                    int c = p[j][1], d = p[j][2];
                    if (c <= u && d >= u)
                    {
                        mid = max(mid, p[j][0] - p[i][0] - 1);
                        u = d + 1;
                    } else
                    if (c <= v && d >= v)
                    {
                        mid = max(mid, p[j][0] - p[i][0] - 1);
                        v = c - 1;
                    }
                }
                if (u <= v) r = max(r, m - p[i][0]);
            }
            cur += l + r + max(0ll, mid - l - r);
//            if (cur == 2) cout << x << ' ' << y << '\n';
            ans = min(ans, cur);
        }
        cout << ans << '\n';
        return 0;
    }
}
namespace sub3
{
    bool cmp(ii x, ii y)
    {
        if (x.II < y.II) return true; else
            if (x.II == y.II) return x.I < y.I;
        return false;
    }
    void init(vector<int>& t)
    {
        t.pb(0);
        sort(t.begin(), t.end());
        t.resize(unique(t.begin(), t.end()) - t.begin());
    }
    int main()
    {
        vector<ii> s;
        int mn = INF, mx = 0;
        for (int i = 1; i <= k; i++)
        {
            int u, v;
            cin >> u >> v;
            s.pb({u, v});
            mx = max(mx, u);
            mn = min(mn, u);
        }
        mn--, mx = n - mx;
        sort(s.begin(), s.end(), cmp);
        vector<int> U, D;
        for (int i = 0; i < k; i++)
        {
            if (s[i].I > 1) U.pb(s[i].I - 1);
            if (s[i].I < n) D.pb(n - s[i].I);
            int MN = INF;
            for (int j = 0; j < i; j++)
                if (s[i].I + mx < s[j].I - mn - 1)
                {
                    MN = min(MN, s[j].I);
//                    t.pb({s[j].I - mn - 1 - s[i].I});
//                    t.pb({s[j].I - (s[i].I + mx) - 1});
//                    break;
                }
            if (MN != INF)
            {
                D.pb({MN - mn - 1 - s[i].I});
                U.pb({MN - (s[i].I + mx) - 1});
            }
            MN = INF;
            for (int j = i + 1; j < k; j++)
                if (s[i].I + mx < s[j].I - mn - 1)
                {
                    MN = min(MN, s[j].I);
//                    t.pb({s[j].I - mn - 1 - s[i].I});
//                    t.pb({s[j].I - (s[i].I + mx) - 1});
//                    break;
                }
            if (MN != INF)
            {
                D.pb({MN - mn - 1 - s[i].I});
                U.pb({MN - (s[i].I + mx) - 1});
            }
        }
        init(U);
        init(D);
        int ans = INF;
        vector<ii> t = s;
        sort(t.begin(), t.end());
        int dem = 0;
        for (auto x : U)
            for (auto y : D)
        {
            if (x + y > ans) break;
            int cnt = 0, ok = 1, last;
            vector<array<int, 3> > p;
            for (int i = 0; i < k; i++)
            {
                int l = max(1ll, s[i].I - x), r = min(n, s[i].I + y);
                int L = max(1ll, t[i].I - x), R = min(n, t[i].I + y);
                if (cnt > 0) ok &= (L - 1 <= last); else
                    ok &= (L == 1);
                last = R;
                cnt++;
                p.pb({s[i].II, l, r});
//                if (!x && y == 3) cout << v << ' ' << l << ' ' << r << '\n';
                if (cnt == k) ok &= (R == n);
            }
//            if (!x && y == 2) cout << ok << '\n';
            if (!ok) continue;
            int l = 0, r = 0, mid = 0;
            set<array<int, 3> > S;
            S.insert({n, 1, 0});
            for (auto [i, u, v] : p)
            {
                while (1)
                {
                    auto it = S.upper_bound({u, 0, 0});
                    if (it == S.end()) break;
                    auto [d, c, j] = *it;
                    if (c > v) break;
                    S.erase(it);
                    dem++;
                    if (c <= u && v <= d)
                    {
                        if (!j) l = max(l, i - 1);
                        mid = max(mid, i - j - 1);
                        if (u - 1 >= c) S.insert({u - 1, c, j});
                        if (v + 1 <= d) S.insert({d, v + 1, j});
                    } else
                    if (d < v)
                    {
                        if (!j) l = max(l, i - 1);
                        mid = max(mid, i - j - 1);
                        if (u - 1 >= c) S.insert({u - 1, c, j});
                    } else
                    {
                        if (!j) l = max(l, i - 1);
                        mid = max(mid, i - j - 1);
                        if (v + 1 <= d) S.insert({d, v + 1, j});
                    }
                }
                S.insert({v, u, i});
            }
            reverse(p.begin(), p.end());
            S.clear();
            S.insert({n, 1, 0});
            for (auto [i, u, v] : p)
            {
                while (1)
                {
                    auto it = S.upper_bound({u, 0, 0});
                    if (it == S.end()) break;
                    auto [d, c, j] = *it;
                    if (c > v) break;
                    S.erase(it);
                    if (c <= u && v <= d)
                    {
                        if (!j) r = max(r, m - i);
                        if (u - 1 >= c) S.insert({u - 1, c, j});
                        if (v + 1 <= d) S.insert({d, v + 1, j});
                    } else
                    if (d < v)
                    {
                        if (!j) r = max(r, m - i);
                        if (u - 1 >= c) S.insert({u - 1, c, j});
                    } else
                    {
                        if (!j) r = max(r, m - i);
                        if (v + 1 <= d) S.insert({d, v + 1, j});
                    }
                }
                S.insert({v, u, i});
            }
            ans = min(ans, x + y + l + r + max(0ll, mid - l - r));
//            if (ans == 1260007575) cout << x << ' ' << y << '\n';
        }
//        cout << U.size() << ' ' << D.size() << ' ' << dem << '\n';
        cout << ans << '\n';
    }
}
int32_t main()
{
#define TASKNAME ""
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen(TASKNAME".inp","r" ))
    {
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> n >> m >> k;
    if (max(n, m) <= 40) sub1 :: main(); else
        if (k <= 25) sub2 :: main(); else
            sub3 :: main();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

cultivation.cpp: In function 'long long int sub3::main()':
cultivation.cpp:383:5: warning: no return statement in function returning non-void [-Wreturn-type]
  383 |     }
      |     ^
cultivation.cpp: In function 'int32_t main()':
cultivation.cpp:392:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  392 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:393:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  393 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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