#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")
void upd(vector<pair<int,int>>& tour,int ind,int val,int ofs){
tour[ind].first=val;
while (ind>0){
ind/=2;
tour[ind]=min(tour[ind*2],tour[ind*2+1]);
}
}
pair<int,int> que(vector<pair<int,int>>& tour,int ind,int ofs,int l,int r,int l2,int r2){
if (r<l2 || r2<l){
return {1e9,1e9};
}
if (l<=l2 && r2<=r){
return tour[ind];
}
return min(que(tour,ind*2,ofs,l,r,l2,(l2+r2)/2),que(tour,ind*2+1,ofs,l,r,(l2+r2)/2+1,r2));
}
int dq(int l,int r,vector<pair<int,int>>& tour,int ofs){
if (l>r){
return 0;
}
pair<int,int> pom=que(tour,1,ofs,l,r,0,ofs-1);
// cout << l << " " << pom.second << " " << r << "++\n";
// cout << pom.first << "--\n";
int rje1=pom.first*(r-l+1);
int rje2=dq(l,pom.second-1,tour,ofs);
int rje3=dq(pom.second+1,r,tour,ofs);
return max(rje1,max(rje2,rje3));
}
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<pair<int,int>> tour(ofs*2,{0,0});
for (int i=ofs;i<ofs*2;i++){
tour[i].second=i-ofs;
}
for (int i=ofs-1;i>0;i--){
tour[i]=min(tour[i*2],tour[i*2+1]);
}
// cout << mid << "\n";
int najv=0;
for (int i=0;i<m;i++){
for (int j=0;j<n;j++){
// cout << j << "\n";
if (tour[ofs+j].first>0){
upd(tour,ofs+j,tour[ofs+j].first-1,ofs);
}
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";
/// }
upd(tour,ofs+j,kol,ofs);
}
}
// cout << i << "\n";
//for (int j=0;j<ofs*2;j++){
// cout << tour[j].first << " " << tour[j].second << "\n";
// }
najv=max(najv,dq(0,n-1,tour,ofs));
}
// cout << najv << "+++++++++\n";
if (najv>=k){
l=mid;
rje=najv;
}
else {
r=mid;
}
mid=(l+r)/2;
}
cout << mid << " " << rje << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
452 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
2 ms |
456 KB |
Output is correct |
| 6 |
Correct |
4 ms |
348 KB |
Output is correct |
| 7 |
Correct |
2 ms |
348 KB |
Output is correct |
| 8 |
Correct |
28 ms |
348 KB |
Output is correct |
| 9 |
Correct |
52 ms |
604 KB |
Output is correct |
| 10 |
Correct |
112 ms |
860 KB |
Output is correct |
| 11 |
Correct |
260 ms |
1116 KB |
Output is correct |
| 12 |
Correct |
173 ms |
932 KB |
Output is correct |
| 13 |
Correct |
136 ms |
1116 KB |
Output is correct |
| 14 |
Correct |
450 ms |
1936 KB |
Output is correct |
| 15 |
Correct |
481 ms |
1884 KB |
Output is correct |
| 16 |
Correct |
609 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
603 ms |
2072 KB |
Output is correct |
| 18 |
Correct |
1533 ms |
5820 KB |
Output is correct |
| 19 |
Correct |
1700 ms |
5304 KB |
Output is correct |
| 20 |
Execution timed out |
2025 ms |
9452 KB |
Time limit exceeded |
| 21 |
Halted |
0 ms |
0 KB |
- |
