Code Collection: VIJOS 1255

Code Collection: VIJOS 1255

METHOD: O(n^3), Prefix Sum + O(n) Kadane's Algorithm (10/10)

#include <algorithm>

#include <iostream>

#include <cstring>

using namespace std;

int aray[305][305], psum[305][305], comp[305];

const int SMALL = -22950001;

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int R, C;

cin >> R >> C;

for(int i=1; i<=R; i++)

for(int j=1; j<=C; j++)

{

cin >> aray[i][j];

if(aray[i][j] == 0) aray[i][j] = SMALL;

psum[i][j] = aray[i][j] + psum[i-1][j];

}

int best = aray[1][1];

for(int s=1; s<=R; s++)

for(int e=s; e<=R; e++)

{

memset(comp, 0, sizeof comp);

for(int i=1; i<=C; i++)

{

comp[i] = psum[e][i] - psum[s-1][i];

if(comp[i] < 0) comp[i] = SMALL;

}

int cmax = comp[1], cbest = comp[1];

for(int i=2; i<=C; i++)

{

cmax = max(comp[i], cmax+comp[i]);

cbest = max(cbest, cmax);

}

best = max(best, cbest);

}

cout << best << endl;

}

METHOD: O(n^4), 2-D Prefix Sum + Enumeration (6/8)

#include <algorithm>

#include <iostream>

#include <cstring>

using namespace std;

int psum[305][305], comp[305];

const int SMALL = -22950001;

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int R, C;

cin >> R >> C;

for(int i=1; i<=R; i++)

for(int j=1; j<=C; j++)

{

int x; cin >> x;

if(x == 0) x = SMALL;

psum[i][j] = x + psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1];

}

int best = psum[1][1];

for(int x1=1; x1<=R; x1++)

for(int y1=1; y1<=C; y1++)

for(int x2=x1; x2<=R; x2++)

for(int y2=y1; y2<=C; y2++)

{

best = max(best, psum[x2][y2] - psum[x1-1][y2] - psum[x2][y1-1] + psum[x1-1][y1-1]);

}

cout << best << endl;

}