Submission #227706

#	Time	Username	Problem	Language	Result	Execution time	Memory
227706		emil_physmath	Luxury burrow (IZhO13_burrow)	C++17	0 / 100	2093 ms	12280 KiB

burrow

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;

int n, m, k;
int price[1000][1000], a[1000][1000];
pair<int, int> t[4000];

void Build(int v, int vl, int vr, vector<int>& a)
{
    if (vl == vr)
    {
        t[v] = {a[vr], vr};
        return;
    }
    int vm = (vl + vr) / 2;
    Build(v * 2, vl, vm, a);
    Build(v * 2 + 1, vm + 1, vr, a);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
}
pair<int, int> Min(int v, int vl, int vr, int l, int r)
{
    if (l > vr || vl > r)
        return {10000, 0};
    if (l <= vl && vr <= r)
        return t[v];
    int vm = (vl + vr) / 2;
    return min(Min(v * 2, vl, vm, l, r), Min(v * 2 + 1, vm + 1, vr, l, r));
}
int Solve(int l, int r)
{
    if (l > r)
        return 0;
    pair<int, int> p = Min(1, 0, m - 1, l, r);
    int hei = p.first, i = p.second;
    int ans = (r - l + 1) * hei;
    ans = max(ans, Solve(l, i - 1));
    ans = max(ans, Solve(i + 1, r));
    return ans;
}
int Solve()
{
    vector<int> up(m);
    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
            if (a[i][j])
                ++up[j];
            else
                up[j] = 0;
        Build(1, 0, m - 1, up);
        ans = max(Solve(0, m - 1), ans);
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> price[i][j];
    pair<int, int> ans = {0, n * m};
    int ans_l = 1, ans_r = 1000'000'000;
    while (ans_l <= ans_r)
    {
        int ans_m = (ans_l + ans_r) / 2;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                a[i][j] = (price[i][j] >= ans_m);
        int x = Solve();
        if (x >= k)
        {
            ans = {ans_m, x};
            ans_l = ans_m + 1;
        }
        else
            ans_r = ans_m - 1;
    }
    cout << ans.first << ' ' << ans.second;
}

• Subtask 1: 0 / 100