제출 #885397

#제출 시각아이디문제언어결과실행 시간메모리
885397alexddHard route (IZhO17_road)C++17
0 / 100
1 ms2396 KiB
#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; }

컴파일 시 표준 에러 (stderr) 메시지

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...