Merge branch 'gdoi'
[srcbox.git] / sgu.ru / 104.cpp
blobc29ba8d70c6ffd8f90e8e08511f3cbbfbef28293
1 #include <iostream>
2 using namespace std;
3 int a[100][100],f[100][100],p[100][100],m,n,i,j,k,ps,ans=-2147483647;
4 void write(int dep,int r) {
5 if (dep>1) write(dep-1,p[dep][r]-1);
6 cout<<p[dep][r]<<" ";
8 int main() {
9 cin>>m>>n;
10 for (i=1;i<=m;i++) {
11 for (j=1;j<=n;j++) { cin>>a[i][j]; f[i][j]=0; }
13 for (i=1;i<=m;i++) {
14 for (j=i;j<=n-m+i;j++) {
15 f[i][i-1]=-2147483647;
16 if (f[i-1][j-1]+a[i][j]>f[i][j-1]) { f[i][j]=f[i-1][j-1]+a[i][j]; p[i][j]=j; }
17 else { f[i][j]=f[i][j-1]; p[i][j]=p[i][j-1]; }
20 ps=0;
21 for (i=m;i<=n;i++) {
22 if (f[m][i]>ans) { ans=f[m][i]; ps=i; }
24 cout<<ans<<endl;
25 write(m,ps);
26 return 0;