oj.uz

Submission #227715

# Submission time Handle Problem Language Result Execution time Memory
227715 2020-04-28T14:53:08 Z emil_physmath Luxury burrow (IZhO13_burrow) C++17
100 / 100
 1852 ms 18168 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 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 6 ms 640 KB Output is correct
6 Correct 7 ms 640 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 21 ms 1152 KB Output is correct
9 Correct 41 ms 2040 KB Output is correct
10 Correct 77 ms 1896 KB Output is correct
11 Correct 127 ms 2304 KB Output is correct
12 Correct 90 ms 4224 KB Output is correct
13 Correct 95 ms 1232 KB Output is correct
14 Correct 280 ms 3568 KB Output is correct
15 Correct 275 ms 3456 KB Output is correct
16 Correct 287 ms 3576 KB Output is correct
17 Correct 384 ms 4344 KB Output is correct
18 Correct 693 ms 5240 KB Output is correct
19 Correct 860 ms 6008 KB Output is correct
20 Correct 1344 ms 6904 KB Output is correct
21 Correct 1453 ms 13908 KB Output is correct
22 Correct 1801 ms 18168 KB Output is correct
23 Correct 1852 ms 18040 KB Output is correct
24 Correct 1322 ms 10872 KB Output is correct
25 Correct 1630 ms 11256 KB Output is correct