oj.uz

Submission #227706

# Submission time Handle Problem Language Result Execution time Memory
227706 2020-04-28T14:42:00 Z emil_physmath Luxury burrow (IZhO13_burrow) C++17
0 / 100
 2000 ms 12280 KB 
#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.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 5 ms 512 KB Output is correct
5 Correct 7 ms 640 KB Output is correct
6 Correct 8 ms 640 KB Output is correct
7 Correct 8 ms 384 KB Output is correct
8 Correct 29 ms 1152 KB Output is correct
9 Correct 53 ms 2048 KB Output is correct
10 Correct 126 ms 2308 KB Output is correct
11 Correct 257 ms 2944 KB Output is correct
12 Correct 130 ms 4480 KB Output is correct
13 Correct 184 ms 1664 KB Output is correct
14 Correct 530 ms 4216 KB Output is correct
15 Correct 523 ms 4096 KB Output is correct
16 Correct 583 ms 4732 KB Output is correct
17 Correct 729 ms 4984 KB Output is correct
18 Correct 1492 ms 8056 KB Output is correct
19 Correct 1740 ms 7800 KB Output is correct
20 Execution timed out 2093 ms 12280 KB Time limit exceeded
21 Halted 0 ms 0 KB -