#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define _READ freopen("input.txt", "r", stdin);
#define _FAST \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
const int mod = 1e9 + 7;
void max_self(int &a,int b)
{
a=max(a,b);
}
int32_t main()
{
//_READ
int n,m,w;
cin>>n>>m>>w;
vector<vector<int>> ar(n,vector<int>(m,0));
for(auto &i:ar)
for(auto &j:i)
cin>>j;
vector<vector<int>> items(n,vector<int>(m+1,0));
for(int i=0;i<n;i++)
{
vector<int> prefix(m,0);
prefix[0]=ar[i][0];
for(int j=1;j<m;j++)
prefix[j]=prefix[j-1]+ar[i][j];
for(int j=0;j<m;j++)
{
for(int k=j;k<m;k++)
{
if(j>=1)
max_self(items[i][k-j+1],prefix[k]-prefix[j-1]);
else if(j==0)
max_self(items[i][k-j+1],prefix[k]);
}
}
}
vector<int> dp(w+1,0);
for(int i=0;i<n;i++)
{
vector<int> temp_dp=dp;
vector<int> cur=dp;
for(int j=1;j<=m;j++)//items
{
for(int k=w;k>=j;k--)
{
max_self(temp_dp[k],temp_dp[k-j]+items[i][j]);
}
bool ok=true;
// for(int k=1;k<=w;k++)
// cout<<temp_dp[k]<<" ";
// cout<<"\n";
for(int k=j;k<=w;k++)
if(dp[k]>temp_dp[k])
ok=false;
//cout<<ok<<" ";
if(ok==true)
for(int k=j;k<=w;k++)
dp[k]=temp_dp[k];
temp_dp=cur;
}
//cout<<"====\n";
}
cout<<*max_element(dp.begin(),dp.end());
return 0;
}
You should understand that competitive programming isn't always about trying to convert the problem to the most classical problem you know, but rather applying the concepts you learn from solving classical problems to the new one. Why doesn't your approach work? Simply because it opens the possibility of taking multiple segments or even multiple of the same item from the same row, which is clearly forbidden. What should you do instead?
Let $$$dp[i][j]$$$ represent the maximum attainable sum from the first $$$i$$$ days with $$$j$$$ lectures already attended. Transition is as straightforward as it gets:
$$$dp[i][j] = \max\limits_{0 \le sz \le M} dp[i - 1][j - sz] + f(i, sz)$$$
where $$$f(i, sz)$$$ represents the maximum sum of a contiguous subarray of size $$$sz$$$ on day $$$i$$$. Hopefully you are capable enough to implement this in $$$O(NM^2)$$$.
Your rating graph is motivational <3