Submission #1010790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010790		ivopav	Luxury burrow (IZhO13_burrow)	C++17	100 / 100	1691 ms	14520 KiB

burrow

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    int m;
    int k;
    cin >> n >> m >> k;
    vector<vector<int>> mat={};
    for (int i=0;i<n;i++){
        mat.push_back({});
        for (int j=0;j<m;j++){
            int unos;
            cin >> unos;
            mat[i].push_back(unos);
        }
    }
    int l=1;
    int r=1e9+1;
    int mid=5e8;
    int ofs=1;
    while (ofs<n){
        ofs*=2;
    }
    int rje=0;
    while (l<mid){
     //   cout << mid << "-----------\n";
        vector<vector<bool>> mat2={};
        for (int i=0;i<n;i++){
            mat2.push_back({});
            for (int j=0;j<m;j++){
                if (mat[i][j]>=mid){
                    mat2[i].push_back(1);
                }
                else {
                    mat2[i].push_back(0);
                }
            }
        }
   //     cout << mid << "\n";
        vector<int> lis2(n,0);
       // cout << mid << "\n";
        int najv=0;
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
     //           cout << j << "\n";
                if (lis2[j]>0){
                    lis2[j]--;
                }
                else if (mat2[j][i]){
                    int kol=0;
                    int sad=i;
                    while (sad<m && mat2[j][sad]){
                        kol++;
                        sad++;
                    }
           //         if (sad>0){
         //               cout << i << " " << j << " " << kol << "+++__+_+_____+\n";
      ///              }
                    lis2[j]=kol;
                }
            }
    //        cout << i << "\n";
            //for (int j=0;j<ofs*2;j++){
          //      cout << tour[j].first << " " << tour[j].second << "\n";
        //    }
          //  for (int j=0;j<n;j++){
        //        cout << lis2[j] << "++\n";
      //      }
            vector<int> prosind={};
            stack<pair<int,int>> st1={};
            for (int j=0;j<n;j++){
              //  cout << j << " " << lis2.size() << "\n";
                while (st1.size()>0 && st1.top().first>=lis2[j]){
                    st1.pop();
                }
                if (st1.size()==0){
                    prosind.push_back(0);
                }
                else {
                    prosind.push_back(st1.top().second+1);
                }
           //     cout << prosind.back() << " ";
                st1.push({lis2[j],j});
            }
           // cout << "\n";
            stack<pair<int,int>> st2={};
            vector<int> sljeind={};
            for (int j=n-1;j>-1;j--){
                while (st2.size()>0 && st2.top().first>=lis2[j]){
                    st2.pop();
                }
                if (st2.size()==0){
                    sljeind.push_back(n-1);
                }
                else {
                    sljeind.push_back(st2.top().second-1);
                }
         //       cout << sljeind.back() << " ";
                st2.push({lis2[j],j});
            }
       //     cout << "\n";
     //       cout << najv << "+++++++++\n";
            reverse(sljeind.begin(),sljeind.end());
            for (int j=0;j<n;j++){
                
                najv=max(najv,(sljeind[j]-prosind[j]+1)*lis2[j]);
            }
        }
        if (najv>=k){
            l=mid;
            rje=najv;   
        }
        else {
            r=mid;
        }
        mid=(l+r)/2;
    }
    cout << mid << " " << rje << "\n";
}

• Subtask 1: 100 / 100