Submission #1010790

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1010790	2024-06-29T11:18:29 Z	ivopav	Luxury burrow (IZhO13_burrow)	C++17	100 / 100	1691 ms	14520 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	2 ms	348 KB	Output is correct
6	Correct	3 ms	348 KB	Output is correct
7	Correct	3 ms	344 KB	Output is correct
8	Correct	17 ms	348 KB	Output is correct
9	Correct	31 ms	728 KB	Output is correct
10	Correct	73 ms	832 KB	Output is correct
11	Correct	100 ms	1116 KB	Output is correct
12	Correct	71 ms	920 KB	Output is correct
13	Correct	95 ms	856 KB	Output is correct
14	Correct	243 ms	1916 KB	Output is correct
15	Correct	234 ms	2172 KB	Output is correct
16	Correct	249 ms	2392 KB	Output is correct
17	Correct	357 ms	1888 KB	Output is correct
18	Correct	591 ms	5776 KB	Output is correct
19	Correct	760 ms	5264 KB	Output is correct
20	Correct	1059 ms	9408 KB	Output is correct
21	Correct	1242 ms	10328 KB	Output is correct
22	Correct	1557 ms	14160 KB	Output is correct
23	Correct	1691 ms	14520 KB	Output is correct
24	Correct	1149 ms	7332 KB	Output is correct
25	Correct	1505 ms	7704 KB	Output is correct