#include <bits/stdc++.h> using namespace std; long long pref[3*100*1000+6]; int main(){ int n, k, q; cin >> n>>k>>q; pref[0]=0; for (int i=0; i<n;i++){ long long tmp; cin >> tmp; pref[i+1]=pref[i]+tmp; } vector <vector <long long> > f; f.resize(n); for (int i=0; i<n;i++){ f[i].resize(n,0); } for (int a=0;a<n;a++){ if (a+k-1<n){ f[a][a+k-1]=max((long long)0,pref[a+k]-pref[a]); } } /*for (int i=0;i<n;i++){ if (i+k-1<n){ cout << f[i][i+k-1]<<" "; } } cout << endl;*/ for (int k2=k+1;k2<=n;k2++){ for (int a=0; a<n;a++){ int b=a+k2-1; if (b<n){ for (int i=0;i+1<k2;i++){ if (a+i+1<n){ f[a][b]=max(f[a][b],f[a][a+i]+f[a+i+1][b]); //cout << a<<" "<<a+i<<" "<<f[a][a+i]<<" "<<b<<" "<<a+i+1<<" "<<f[a+i+1][b]<<endl; } } } } } /*for (int i=0;i<n;i++){ cout << i<<": "; for (int j=k;j<=n;j++){ if (i+j-1<n){ cout <<"f["<<i<<"]["<<i+j-1<<"]="<< f[i][i+j-1]<<" "; } } cout <<endl; }*/ for (int q2=0;q2<q;q2++){ int l,r; cin >> l >> r; cout << f[l-1][r-1]<<endl; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | #include <bits/stdc++.h> using namespace std; long long pref[3*100*1000+6]; int main(){ int n, k, q; cin >> n>>k>>q; pref[0]=0; for (int i=0; i<n;i++){ long long tmp; cin >> tmp; pref[i+1]=pref[i]+tmp; } vector <vector <long long> > f; f.resize(n); for (int i=0; i<n;i++){ f[i].resize(n,0); } for (int a=0;a<n;a++){ if (a+k-1<n){ f[a][a+k-1]=max((long long)0,pref[a+k]-pref[a]); } } /*for (int i=0;i<n;i++){ if (i+k-1<n){ cout << f[i][i+k-1]<<" "; } } cout << endl;*/ for (int k2=k+1;k2<=n;k2++){ for (int a=0; a<n;a++){ int b=a+k2-1; if (b<n){ for (int i=0;i+1<k2;i++){ if (a+i+1<n){ f[a][b]=max(f[a][b],f[a][a+i]+f[a+i+1][b]); //cout << a<<" "<<a+i<<" "<<f[a][a+i]<<" "<<b<<" "<<a+i+1<<" "<<f[a+i+1][b]<<endl; } } } } } /*for (int i=0;i<n;i++){ cout << i<<": "; for (int j=k;j<=n;j++){ if (i+j-1<n){ cout <<"f["<<i<<"]["<<i+j-1<<"]="<< f[i][i+j-1]<<" "; } } cout <<endl; }*/ for (int q2=0;q2<q;q2++){ int l,r; cin >> l >> r; cout << f[l-1][r-1]<<endl; } } |