| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 885397 |
2023-12-09T15:13:58 Z |
alexdd |
Hard route (IZhO17_road) |
C++17 |
|
1 ms |
2396 KB |
#include<iostream>
using namespace std;
int n,m;
char mat[2505][2505];
int sump[2505][2505];
int mars[2505][2505];
bool verif(int cntx, int cnty)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
mars[i][j]=0;
for(int i=1;i+cntx-1<=n;i++)
{
for(int j=1;j+cnty-1<=m;j++)
{
if(sump[i+cntx-1][j+cnty-1] - sump[i+cntx-1][j-1] - sump[i-1][j+cnty-1] + sump[i-1][j-1] == cntx*cnty)///toate is 1
{
mars[i][j]++;
mars[i][j+cnty]--;
mars[i+cntx][j]--;
mars[i+cntx][j+cnty]++;
}
mars[i][j] += mars[i-1][j] + mars[i][j-1] - mars[i-1][j-1];
if(mars[i][j]==0 && mat[i][j]=='1')
return 0;
}
}
return 1;
}
void solve_n3_y(int minx, int miny)
{
int poz=0, mxm=0;
for(int i=minx;i>0;i--)
{
if(i*miny <= mxm)
break;
while(poz+1<=miny && verif(i,poz+1))
{
poz++;
}
mxm = max(mxm, i*poz);
}
cout<<mxm;
}
void solve_n3_x(int minx, int miny)
{
int poz=0, mxm=0;
for(int i=miny;i>0;i--)
{
if(i*minx <= mxm)
break;
while(poz+1<=minx && verif(poz+1,i))
{
poz++;
}
mxm = max(mxm, i*poz);
}
cout<<mxm;
}
void solve_bulaneala(int minx, int miny)
{
int mxm=0,prec=1;
//for(int i=miny;i>max(0,miny-4);i--)
for(int i=min(miny,3);i>0;i--)
{
if(i*minx <= mxm)
break;
int st,dr,mij,ans=0;
st=1;
dr=minx;
while(st<=dr)
{
mij=(st+dr)/2;
if(verif(mij,i))
{
ans = max(ans, mij);
st=mij+1;
}
else
{
dr=mij-1;
}
}
mxm = max(mxm, i*ans);
prec=ans;
}
prec=1;
//for(int i=minx;i>max(0,minx-4);i--)
for(int i=min(minx,3);i>0;i--)
{
if(i*miny <= mxm)
break;
int st,dr,mij,ans=0;
st=1;
dr=miny;
while(st<=dr)
{
mij=(st+dr)/2;
if(verif(i,mij))
{
ans = max(ans, mij);
st=mij+1;
}
else
{
dr=mij-1;
}
}
mxm = max(mxm, i*ans);
prec=ans;
}
cout<<mxm;
}
signed main()
{
cin>>n>>m;
int minx=n,miny=m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>mat[i][j];
sump[i][j] = sump[i-1][j] + sump[i][j-1] - sump[i-1][j-1];
if(mat[i][j]=='1')
sump[i][j]++;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(mat[i][j]=='1' && (j==m || mat[i][j+1]=='0'))
{
int cnt=0;
for(int u=j;u>0;u--)
{
if(mat[i][u]=='0')
break;
cnt++;
}
miny = min(miny, cnt);
}
}
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(mat[j][i]=='1' && (j==n || mat[j+1][i]=='0'))
{
int cnt=0;
for(int u=j;u>0;u--)
{
if(mat[u][i]=='0')
break;
cnt++;
}
minx = min(minx, cnt);
}
}
}
if(1LL*miny * n * m <= 170000000)
{
solve_n3_y(minx,miny);
return 0;
}
else if(1LL*minx*n*m <= 170000000)
{
solve_n3_x(minx,miny);
return 0;
}
else if(1)
{
solve_bulaneala(minx,miny);
return 0;
}
else
{
cout<<minx*miny;
return 0;
}
return 0;
}
Compilation message
road.cpp: In function 'void solve_bulaneala(int, int)':
road.cpp:62:15: warning: variable 'prec' set but not used [-Wunused-but-set-variable]
62 | int mxm=0,prec=1;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
