fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int forw[3005], backw[3005];
  5.  
  6. int gamecom(vector<int> a, int k){
  7.     int n = a.size(); // n stores the size of the vector
  8.     k--; // so that index is matched correctly(starting from zero)
  9.  
  10.     if(k!=n-1){ // if k is the last element, forward[i] should be zero
  11.         if(a[k+1]>forw[k+1]){
  12.             forw[k+1] = a[k+1]; // assigning the first value in forward[i]
  13.         }
  14.     }
  15.     backw[0] = a[0]; // assigning the first value in backward[i]
  16.     for(int i=1; i<=k; i++){ // assigning values from 1 to k in backward[i]
  17.         if(backw[i]<backw[i-1]+a[i]){
  18.             backw[i] = backw[i-1]+a[i];
  19.         }
  20.         else{
  21.             backw[i] = backw[i-1];
  22.         }
  23.     }
  24.  
  25.     for(int i=k+1; i<n; i++){ //assigning values from k+1 to n in forward[i]
  26.         if(forw[i-1]+a[i]>forw[i-1]){
  27.             forw[i] = a[i]+forw[i-1];
  28.         }
  29.         else{
  30.             forw[i] = forw[i-1];
  31.         }
  32.         if(i==n-1){ // last element should not be counted in backward[i]
  33.             backw[i] = backw[i-1];
  34.         }
  35.         else if(backw[i-1]+a[i]>backw[i-1]){ // assigning values in backward[i]
  36.             backw[i] = backw[i-1]+a[i];
  37.         }
  38.         else{
  39.             backw[i] = backw[i-1];
  40.         }
  41.  
  42.     }
  43.     int ans  =INT_MIN; // calculating the maximum of forward[i]+backward[i]
  44.  
  45.     for(int i=0; i<n; i++){
  46.         ans = max(ans, forw[i]+backw[i]);
  47.     }
  48.     return ans;
  49. }
  50.  
  51. int main(){
  52.     int n, k;
  53.     cin >> n >> k;
  54.     vector<int> a;
  55.     for(int i=0; i<n; i++){
  56.         int x;
  57.         cin >> x;
  58.         a.push_back(x);
  59.     }
  60.     cout << gamecom(a, k);
  61. }
  62.  
Success #stdin #stdout 0s 2900KB
comments (?)
stdin
copy 
5 2
5 3 -2 1 1
stdout
copy 
11
https://ideone.com/CiUDKO
language:
C++ 4.3.2 (gcc-4.3.2)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!