Submission #170824

#	Time	Username	Problem	Language	Result	Execution time	Memory
170824		davitmarg	Luxury burrow (IZhO13_burrow)	C++17	100 / 100	788 ms	18164 KiB

burrow

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 1005;

int n, m, k, a[N][N], d[N][N];
int l, r, mid, ans;

int solve(int x)
{
    int res = 0;
    //cout << x << endl;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] >= x)
                d[i][j] = d[i - 1][j] + 1;
            else
                d[i][j] = 0;
            //cout << i << " : " << j << " = " << d[i][j] << endl;
        }
        vector<int> v, nxt(m + 5, m + 1), lst(m + 1, 0);
        for (int j = 1; j <= m; j++)
        {
            while (!v.empty() && d[i][v.back()] >= d[i][j])
                v.pop_back();
            if (!v.empty())
                lst[j] = v.back();
            lst[j]++;
            v.PB(j);
        }
        v.clear();
        for (int j = m; j >= 1; j--)
        {
            while (!v.empty() && d[i][v.back()] >= d[i][j])
                v.pop_back();
            if (!v.empty())
                nxt[j] = v.back();
            nxt[j]--;
            v.PB(j);
        }
        for (int j = 1; j <= m; j++)
        {
            res = max(d[i][j] * (nxt[j] - lst[j] + 1), res);
            //cout << i << " : " << j << " = " << lst[j] << " : " << nxt[j] << endl;
        }
    }
    return res;
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", a[i] + j);
    l = 0;
    r = mod;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (solve(mid) >= k)
        {
            ans = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    cout << ans << " " << solve(ans) << endl;
    return 0;
}

/*

2 
2 0
3



*/

Compilation message (stderr)

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

• Subtask 1: 100 / 100