/*
user: php
time: 0.016 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1015
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
using namespace std;
#define MAXX 101
bool graph[MAXX][MAXX];
int presum[MAXX+1][MAXX+1];
int columns, rows;
int MIS()
{
loop(i, columns)
{
loop(j, rows)
{
if(graph[j][i] == 1)
{
presum[j][i] = j;
}
else
{
if(j == 0) presum[j][i] = -1;
else presum[j][i] = presum[j-1][i];
}
}
}
int longest_sum = 0;
int sum;
loop(i, rows)
{
FOR(j,i, rows)
{
sum = 0;
loop(k, columns)
{
if(presum[i][k] < i && presum[j][k] < i)
{
sum = sum + (j - i + 1);
if(longest_sum < sum)
{
longest_sum = sum;
}
}
else
{
sum = 0;
}
}
}
}
return longest_sum;
}
int main()
{
while(true)
{
getint(rows); getint(columns);
if(rows == 0 && columns == 0) break;
loop(i, rows)
{
loop(j, columns)
{
getint(graph[i][j]);
}
}
printf("%d\n", MIS());
}
return 0;
}
Category Archives: Maximum Interval Sum(MIS)
(UVa) 108 – Maximum Sum
0
/*
user: php
time: 0.012 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=44
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int( a.size() )
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
using namespace std;
#define MAXX 102
int array[MAXX][MAXX];
ll prefixsum[MAXX][MAXX];
int N;
ll MIS()
{
loop(i, N)
{
prefixsum[0][i] = 0;
for(int j=1; j <= N; j++)
{
prefixsum[j][i] = prefixsum[j-1][i] + array[j-1][i];
}
}
ll maxsum = 0;
ll sum = 0;
for(int i=0; i <= N; i++)
{
for(int j=i+1; j <= N; j++)
{
sum = 0;
loop(k, N)
{
sum += prefixsum[j][k] - prefixsum[i][k];
if(sum > maxsum)
{
maxsum = sum;
}
else if(sum < 0)
{
sum = 0;
}
}
}
}
return maxsum;
}
int main()
{
getint(N);
loop(i, N)
{
loop(j, N)
{
getint(array[i][j]);
}
}
ll result = MIS();
printf("%lld\n", result);
return 0;
}
(UVa) 10684 – The jackpot
0
/*
user: php
time: 0.084 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1625
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
using namespace std;
#define MAXX 10001
int main()
{
int N;
int num;
ll maxbet;
ll sum;
while(getint(N) && N != 0)
{
sum = 0;
maxbet = 0;
loop(i, N)
{
getint(num);
sum += num;
if(sum > maxbet)
{
maxbet = sum;
}
else if( sum < 0 )
{
sum = 0;
}
}
if(maxbet > 0)
{
printf("The maximum winning streak is %lld.\n", maxbet);
}
else
{
printf("Losing streak.\n");
}
}
return 0;
}
(UVa) 507 – Jill Rides Again
0
/*
user: php
time: 0.132 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=448
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
using namespace std;
#define MAXX 20001
int ara[MAXX];
int paths;
int start, end;
int maxcycleride;
struct DATA{
int start, end, cycleride;
int maxsum;
};
DATA result;
void MIS()
{
result.maxsum = -INF;
result.cycleride = -INF;
int sum = 0;
int current_ride = 0;
end = paths;
for(int i=paths-1; i>-1; i--)
{
sum += ara[i];
if(ara[i] > 0 ) current_ride++;
if( sum < 0 )
{
sum = 0;
end = i;
current_ride = 0;
}
else if( sum == result.maxsum)
{
if(current_ride >= result.cycleride )
{
start = i;
result.start = start;
result.cycleride = current_ride;
result.end = end;
}
}
else if(sum > result.maxsum)
{
start = i;
result.maxsum = sum;
result.cycleride = current_ride;
result.end = end;
result.start = start;
}
}
}
int main()
{
int kases;
int kaseno = 0;
getint(kases);
while(kases--)
{
getint(paths);
paths--;
loop(i, paths)
{
getint(ara[i]);
}
MIS();
if(result.maxsum != -INF)
printf("The nicest part of route %d is between stops %d and %d\n", ++kaseno, result.start+1, result.end+1);
else
printf("Route %d has no nice parts\n", ++kaseno);
}
return 0;
}
UnLucky Codes 