제출 #830783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
830783		vjudge1	Garden (JOI23_garden)	C++17	30 / 100	3087 ms	8280 KiB

garden

#include <bits/stdc++.h>

using namespace std;

int ceil(int a, int b)
{
    return (a + b - 1) / b;
}

int cnt(int st, int d, int x) // cate numere dau restul x la impartire prin d pana in st
{
    if (st < x)
    {
        return 0;
    }
    return (st - x) / d + 1;
}

bool in_range(int st, int dr, int d, int x)
{
    return cnt(dr, d, x) - cnt(st - 1, d, x);
}

int get_min(vector<int> resturi, int d) // lungime minima care acopera resturile
{
    sort(resturi.begin(), resturi.end());
    int ans = resturi.back() - resturi.front() + 1;
    for (int i = 1; i < (int)resturi.size(); ++i)
    {
        ans = min(ans, d - (resturi[i] - resturi[i - 1] - 1));
    }
    return ans;
}

int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int d, n, m;
    cin >> n >> m >> d;
    vector<pair<int, int>> si(n + 1);
    vector<pair<int, int>> sau(m + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> si[i].first >> si[i].second;
    }
    for (int i = 1; i <= m; ++i)
    {
        cin >> sau[i].first >> sau[i].second;
    }
    int ans = INT_MAX;
    for (int i = 0; i < d; ++i)
    {
        for (int j = i; j < i + d; ++j)
        {
            bool ok = true;
            for (int k = 1; k <= n; ++k)
            {
                if (!in_range(i, j, d, si[k].first))
                {
                    ok = false;
                    break;
                }
            }
            if (!ok)
                continue;
            vector<int> resturi;
            for (int k = 1; k <= n; ++k)
            {
                resturi.push_back(si[k].second);
            }
            for (int k = 1; k <= m; ++k)
            {
                if (in_range(i, j, d, sau[k].first))
                {
                    continue;
                }
                resturi.push_back(sau[k].second);
            }
            ans = min(ans, (j - i + 1) * get_min(resturi, d));
        }
    }
    cout << ans;
}

• Subtask 1: 0 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25