fork download
copy 
  1. /*
  2.   Zenit CK 2011/2012, uloha e)
  3.   Riesenie by Zemco
  4.  
  5.   Dynamicke programovanie, DP[i][j] znamena, aby najvacsi
  6.   otoceny stvorec ma dolny bod v mieste [i][j]?
  7.   Pocitame postupne pre zvacsujuce sa i a zvacsujuce sa j.
  8.   Cas O(R*C), pamat (R*C) dala by sa zlepsit.
  9.    */
  10. #include<cstdio>
  11. #include<cstring>
  12. #include<algorithm>
  13. #define FOR(i,N) for(int i=0;i<N;i++)
  14. using namespace std;
  15. int R,C;
  16. //vstup si pamatame s ramom 2 stlpce a 2 riadky, tvorenym bodkami. zjednodusuje to program
  17. char I[1050][1050];
  18. int DP[1050][1050];
  19.  
  20. //velkost hrany ->  velkost diamantu
  21. int edgetosize(int e){
  22.   return (2*e-1)*(2*e-1) - 2*(e*(e-1));
  23. }
  24.  
  25. int main(){
  26.   scanf("%d %d ",&R,&C);
  27.   memset(I,'.',sizeof(I));
  28.   //maly implementacny trik. scanfu podhodime adresu az od tretieho znaku, nech nam necha 2 ramove bodky
  29.   FOR(i,R) scanf("%s ",&I[i+2][2]);
  30.   int mx = 0;
  31.   FOR(ii,R)FOR(jj,C){
  32.     int i = ii+2;
  33.     int j = jj+2;
  34.     if (I[i][j] == '.') DP[i][j] = 0;
  35.     else DP[i][j] = 1+min(min(DP[i-1][j-1],DP[i-1][j+1]),min(DP[i-2][j],DP[i-1][j]));
  36.     mx = max(mx,DP[i][j]);
  37.   }
  38.   printf("%d\n",edgetosize(mx));
  39. }
Success #stdin #stdout 0.02s 8108KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/PyScX
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!