Submission #366876

#	Time	Username	Problem	Language	Result	Execution time	Memory
366876		Ruxandra985	Bomb (IZhO17_bomb)	C++14	3 / 100	537 ms	67968 KiB

bomb

#include <bits/stdc++.h>

using namespace std;
char a[2510][2510] , b[2510][2510];
int sl[2510][2510] , sr[2510][2510] , v[2510];
int dp[2510] , n , m;

void solve (){
    int i , j , minil , minir , last;

    for (i = 1 ; i <= n ; i++){
        for (j = 1 ; j <= m ; j++)
            sl[i][j] = sr[i][j] = 0;
    }

    for (i = 1 ; i <= n ; i++){
        for (j = 1 ; j <= m ; j++){
            if (a[i][j] == '1'){
                sl[i][j] = 1 + sl[i][j - 1];
                if (a[i][j + 1] != '1')
                    dp[1] = min(dp[1] , sl[i][j]);
                /// daca am o linie, pot sa am dp[1] coloane
            }
        }
        for (j = m ; j ; j--){
            if (a[i][j] == '1')
                sr[i][j] = 1 + sr[i][j + 1];
        }
    }

    /// ce se intampla daca vreau mai mult de o linie

    for (j = 1 ; j <= m ; j++){
        minil = minir = 2000000000;
        last = 0;
        for (i = 0 ; i <= n + 1 ; i++){

            if (a[i][j] != '1'){
                if (last && i - last != 1)
                    dp[i - last] = 0; /// nu poti sa ai atatea linii
                last = i; /// utlima linie pe care e 0 pe pozitia asta
                minil = minir = 2000000000;
            }
            else {
                minir = min(minir , sr[i][j]);
                minil = min(minil , sl[i][j]);
                dp[i - last] = min(dp[i - last] , minil + minir - 1);
            }


        }
    }

    for (i = 2 ; i <= n ; i++)
        dp[i] = min (dp[i] , dp[i - 1]);

    //printf ("%d ",dp[1]);

}

int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int i , j , miniw , minih , lenc , sol;
    fscanf (fin,"%d%d\n",&n,&m);
    for (i = 1 ; i <= n ; i++){
        for (j = 1 ; j <= m ; j++)
            a[i][j] = fgetc(fin);
        fgetc(fin);
    }

    for (i = 1 ; i <= max(n , m) ; i++)
        dp[i] = 2000000000;

    sol = 0;

    solve();

    for (i = 1 ; i <= n ; i++){
        for (j = 1 ; j <= m ; j++){
            b[i][j] = a[n - i + 1][j];
        }
    }

    for (i = 1 ; i <= n ; i++){
        for (j = 1 ; j <= m ; j++){
            a[i][j] = b[i][j];
        }
    }

    solve();
    for (i = 1 ; i <= n ; i++){
        if (dp[i] != 2000000000)
            sol = max(sol , i * dp[i]);
    }
    fprintf (fout,"%d",sol);

    /// raspuns

    return 0;
}

Compilation message (stderr)

bomb.cpp: In function 'int main()':
bomb.cpp:65:17: warning: unused variable 'miniw' [-Wunused-variable]
   65 |     int i , j , miniw , minih , lenc , sol;
      |                 ^~~~~
bomb.cpp:65:25: warning: unused variable 'minih' [-Wunused-variable]
   65 |     int i , j , miniw , minih , lenc , sol;
      |                         ^~~~~
bomb.cpp:65:33: warning: unused variable 'lenc' [-Wunused-variable]
   65 |     int i , j , miniw , minih , lenc , sol;
      |                                 ^~~~
bomb.cpp:66:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     fscanf (fin,"%d%d\n",&n,&m);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 100