Max Sum Plus Plus
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Appoint description:
System Crawler (2015-09-05)
System Crawler (2015-09-05)
Description
Now I think you have got an AC in Ignatius.L's "Max Sum" problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.
Given a consecutive number sequence S 1, S 2, S 3, S 4 ... S x, ... S n (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ S x ≤ 32767). We define a function sum(i, j) = S i + ... + S j (1 ≤ i ≤ j ≤ n).
Now given an integer m (m > 0), your task is to find m pairs of i and j which make sum(i 1, j 1) + sum(i 2, j 2) + sum(i 3, j 3) + ... + sum(im, j m) maximal (i x ≤ i y ≤ j x or i x ≤ j y ≤ j x is not allowed).
But I`m lazy, I don't want to write a special-judge module, so you don't have to output m pairs of i and j, just output the maximal summation of sum(i x, j x)(1 ≤ x ≤ m) instead. ^_^
Input
Each test case will begin with two integers m and n, followed by n integers S 1, S 2, S 3 ... S n.
Process to the end of file.
Process to the end of file.
Output
Output the maximal summation described above in one line.
Sample Input
1 3 1 2 3
2 6 -1 4 -2 3 -2 3
2 6 -1 4 -2 3 -2 3
Sample Output
6
8
8
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; const int SIZE = ;
const int INF = 0x7ffffff0;
long long DP[SIZE][];
int S[SIZE]; long long max(long long a,long long b);
int main(void)
{
int n,m,i_0,i_1;
long long box,ans,temp; while(scanf("%d%d",&m,&n) != EOF)
{
memset(DP,,sizeof(DP));
ans = -INF;
i_0 = ;
i_1 = ; for(int i = ;i <= n;i ++)
scanf("%d",&S[i]);
for(int j = ;j <= m;j ++)
{
for(int i = ;i <= n;i ++)
{
DP[i][i_1] = i - < j ? -INF : DP[i - ][i_1];
if(i == )
{
temp = -INF;
for(int k = j - ;k < i;k ++)
temp = max(temp,DP[k][i_0]);
}
else
temp = temp > DP[i - ][i_0] ? temp : DP[i - ][i_0];
DP[i][i_1] = (temp > DP[i][i_1] ? temp : DP[i][i_1]) + S[i];
if(j == m)
ans = ans > DP[i][i_1] ? ans : DP[i][i_1];
}
swap(i_0,i_1);
}
printf("%lld\n",ans);
}
} long long max(long long a,long long b)
{
return a > b ? a : b;
}