oj.uz

Submission #672983

# Submission time Handle Problem Language Result Execution time Memory
672983 2022-12-19T09:43:16 Z Alihan_8 Luxury burrow (IZhO13_burrow) C++17
100 / 100
 682 ms 25676 KB 
#include <bits/stdc++.h>
// include <ext/pb_ds/assoc_container.hpp>
// include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
// define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
#define mpr make_pair
#define ln '\n'
void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
#define int long long
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k; cin >> n >> m >> k;
    vector <vector<int>> p(n);
    for ( auto &i: p ){
        i.resize(m);
        for ( auto &j: i ) cin >> j;
    }
    auto chmax = [&](int &l, int r){l = max(l, r);};
    auto calc = [&](vector <int> &x){
        auto f = [&](){
            stack <int> stk;
            vector <int> res(m);
            stk.push(-1);
            for ( int i = 0; i < m; i++ ){
                while ( stk.top() != -1 and x[stk.top()] >= x[i] ) stk.pop();
                res[i] = stk.top()+1;
                stk.push(i);
            }
            return res;
        };
        vector <int> l = f();
        reverse(all(x));
        vector <int> r = f();
        reverse(all(x));
        for ( int i = 0; i < m; i++ ) r[i] = m-1-r[i];
        reverse(all(r));
        int Mx = 0;
        for ( int i = 0; i < m; i++ ) chmax(Mx, (r[i]-l[i]+1)*x[i]);
        return Mx;
    };
    auto f = [&](int T){
        vector <vector<int>> bits(n, vector <int> (m));
        for ( int i = 0; i < n; i++ ){
            for ( int j = 0; j < m; j++ ){
                bits[i][j] = p[i][j] >= T;
            }
        }
        vector <int> x(m);
        int Mx = 0;
        for ( int i = 0; i < n; i++ ){
            for ( int j = 0; j < m; j++ ){
                if ( bits[i][j] ) x[j]++;
                else x[j] = 0;
            }
            chmax(Mx, calc(x));
        }
        return Mx;
    };
    int l = 1, r = 1e9+1;
    while ( l+1 < r ){
        int md = (l+r)>>1;
        if ( f(md) < k ) r = md;
        else l = md;
    }
    cout << l << ' ' << f(l);

    cout << '\n';
}

Compilation message

burrow.cpp: In function 'void IO(std::string)':
burrow.cpp:11:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
burrow.cpp:11:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 8 ms 504 KB Output is correct
9 Correct 12 ms 724 KB Output is correct
10 Correct 31 ms 1236 KB Output is correct
11 Correct 60 ms 1912 KB Output is correct
12 Correct 36 ms 1268 KB Output is correct
13 Correct 38 ms 1472 KB Output is correct
14 Correct 98 ms 3428 KB Output is correct
15 Correct 101 ms 3428 KB Output is correct
16 Correct 105 ms 3928 KB Output is correct
17 Correct 122 ms 4784 KB Output is correct
18 Correct 271 ms 8772 KB Output is correct
19 Correct 318 ms 9884 KB Output is correct
20 Correct 580 ms 16076 KB Output is correct
21 Correct 569 ms 19324 KB Output is correct
22 Correct 670 ms 25676 KB Output is correct
23 Correct 682 ms 25620 KB Output is correct
24 Correct 472 ms 14948 KB Output is correct
25 Correct 535 ms 18892 KB Output is correct