oj.uz

Submission #227707

# Submission time Handle Problem Language Result Execution time Memory
227707 2020-04-28T14:45:01 Z emil_physmath Luxury burrow (IZhO13_burrow) C++17
0 / 100
 2000 ms 6136 KB 
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#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)
{
    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(1, 0, m - 1, 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(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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 8 ms 640 KB Output is correct
7 Correct 8 ms 384 KB Output is correct
8 Correct 34 ms 1152 KB Output is correct
9 Correct 63 ms 1920 KB Output is correct
10 Correct 153 ms 1920 KB Output is correct
11 Correct 292 ms 2304 KB Output is correct
12 Correct 156 ms 4316 KB Output is correct
13 Correct 218 ms 1152 KB Output is correct
14 Correct 605 ms 3712 KB Output is correct
15 Correct 621 ms 3576 KB Output is correct
16 Correct 684 ms 3576 KB Output is correct
17 Correct 853 ms 4352 KB Output is correct
18 Correct 1714 ms 5240 KB Output is correct
19 Execution timed out 2001 ms 6136 KB Time limit exceeded
20 Halted 0 ms 0 KB -