Submission #227715

#	Time	Username	Problem	Language	Result	Execution time	Memory
227715		emil_physmath	Luxury burrow (IZhO13_burrow)	C++17	100 / 100	1852 ms	18168 KiB

burrow

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

int n, m, k;
int price[1000][1000], a[1000][1000];
const int lg = 10;
pair<int, int> t[lg + 1][4000];

inline int pow2(int i) { return 1 << i; }
void Build(vector<int>& a)
{
    int n = a.size();
    for (int i = 0; i < n; ++i)
        t[0][i] = {a[i], i};
    for (int l = 1; l <= lg; ++l)
        for (int i = 0; i + (1 << l) - 1 < n; ++i)
            t[l][i] = min(t[l - 1][i], t[l - 1][i + pow2(l - 1)]);
}
pair<int, int> Min(int l, int r)
{
    int x = __lg(r - l + 1);
    return min(t[x][l], t[x][r - (1 << x) + 1]);
}
int Solve(int l, int r)
{
    queue<pair<int, int>> q;
    q.push({l, r});
    int ans = 0;
    while (q.size())
    {
        l = q.front().first, r = q.front().second;
        q.pop();
        if (l > r)
            continue;
        pair<int, int> p = Min(l, r);
        int hei = p.first, i = p.second;
        ans = max(ans, (r - l + 1) * hei);
        q.push({l, i - 1});
        q.push({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(up);
        ans = max(Solve(0, m - 1), ans);
    }
    return ans;
}
int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            scanf("%d", 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;
}

Compilation message (stderr)

burrow.cpp: In function 'int main()':
burrow.cpp:69:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", price[i] + j);
             ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100