Bài 1:

467C - George and Job

The solution to this problem is dynamic programming. Initially, you need to calculate psum_R, where psum_R is the sum on the prefix of the array p of length R.

Let’s denote dp_(i,j) - the maximum profit that Jura can get if we have already chosen i sequences and the last element in the i-th sequence has index j.

Obviously, if i.m>j then do_(i,j)=0. Otherwise dp_(i,j)=max(dp_(i,j-1),dp_(i-1,j-m)+psum_j-psum_(j-m)). The answer is dp_(k,n).

You also had to remember to use long long in calculations.

Asymptotics: O(NK)

#include <iostream>
#define ll long long
using namespace std;
ll n,m,k,s[5005],d[5005][5005],i,j;
int main()
{
cin>>n>>m>>k;
for(i=1;i<=n;i++)cin>>s[i],s[i]+=s[i-1];
for(i=1;i<=k;i++)for(j=m;j<=n;j++)d[i][j]=max(d[i][j-1],d[i-1][j-m]+s[j]-s[j-m]);
cout<<d[k][n];
}

Link: https://drive.google.com/file/d/10ElcA9Gd_T_EgFrZIzLpLNavoomqMVNR/view?usp=sharing

Link 2: https://drive.google.com/file/d/1dH-SQCwpp1589LO4CH4OiOIL07KO2O1H/view?usp=sharing