Submission #830821

#	Time	Username	Problem	Language	Result	Execution time	Memory
830821		vjudge1	Garden (JOI23_garden)	C++17	30 / 100	3082 ms	8436 KiB

garden

#include <bits/stdc++.h>

using namespace std;

struct lying
{
    int d;
    vector<int> a;
    void add(int rest)
    {
        a.push_back(rest);
    }
    int getmin()
    {
        sort(a.begin(), a.end());
        int ans = a.back() - a.front() + 1;
        for (int i = 1; i < (int)a.size(); ++i)
        {
            ans = min(ans, d - (a[i] - a[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);

    vector<bool> isneeded(d);

    for (int i = 1; i <= n; ++i)
    {
        cin >> si[i].first >> si[i].second;
        isneeded[si[i].first] = true;
    }
    vector<vector<int>> adam(d);
    for (int i = 1; i <= m; ++i)
    {
        cin >> sau[i].first >> sau[i].second;
        adam[sau[i].first].push_back(sau[i].second);
    }
    int ans = INT_MAX;
    for (int i = 0; i < d; ++i)
    {
        lying pensive;
        pensive.d = d;
        for (int j = 1; j <= n; ++j)
        {
            pensive.add(si[j].second);
        }
        for (int j = i + d - 1; j >= i; --j)
        {
            ans = min(ans, (j - i + 1) * pensive.getmin());
            for (auto k : adam[j % d])
            {
                pensive.add(k);
            }
            if (isneeded[j % d])
            {
                break;
            }
        }
    }
    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