fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3.  
  4. using namespace std;
  5.  
  6. class Route{
  7. private:
  8.     int forward;
  9.     int back;
  10.     int front_cap;
  11.     int back_cap;
  12.     int forward_sum;
  13.     int back_sum;
  14.     vector<int> route;
  15.     int size;
  16.  
  17. public:
  18.     Route(int size){
  19.         //cout<<"Konstruktor"<<endl;
  20.         this->forward = 0;
  21.         this->back = size - 1;
  22.         this->front_cap = forward;
  23.         this->back_cap = back;
  24.         this->forward_sum = 0;
  25.         this->back_sum = 0;
  26.         this->size = size;
  27.     }
  28.  
  29.     void getData(){
  30.         int buf;
  31.         //cout<<"Dane"<<endl;
  32.  
  33.         for(int i=0; i<size; ++i){
  34.             cin>>buf;
  35.             route.push_back(buf);
  36.         }
  37.         /*cout<<"|"<<endl;
  38.         for(int i=0; i<size; ++i){
  39.             cout<<route[i];
  40.         }
  41.         cout<<"|"<<endl;*/
  42.     }
  43.  
  44.     /*void calculate(){
  45.         //cout<<"Oblicz"<<endl;
  46.         long long max_value = -1000000000;
  47.         long long current_value;
  48.  
  49.         for(int i=0; i<=back_cap; ++i){
  50.             current_value = 0;
  51.             for(int j=i; j<=back_cap; ++j){
  52.                 current_value = current_value + route[j];
  53.             }
  54.  
  55.             if(current_value > max_value){
  56.                 max_value = current_value;
  57.                 front_cap = i;
  58.             }
  59.         }
  60.  
  61.         cout<<max_value<<endl;
  62.         cout<<front_cap<<endl;
  63.  
  64.         max_value = route[back_cap];
  65.  
  66.         for(int i=back_cap; i>=front_cap; --i){
  67.             //cout<<"| "<<i<<" |"<<endl;
  68.             current_value = 0;
  69.             for(int j=i; j>=front_cap; --j){
  70.                 current_value = current_value + route[j];
  71.             }
  72.  
  73.             if(current_value > max_value){
  74.                 max_value = current_value;
  75.             }
  76.         }
  77.  
  78.         if(max_value > 0){
  79.             cout<<max_value;
  80.         } else{
  81.             cout<<0;
  82.         }
  83.     }*/
  84.  
  85.     void calculate(){
  86.         //cout<<"Oblicz"<<endl;
  87.         bool again = true;
  88.  
  89.         while(again){
  90.             again = false;
  91.  
  92.             if(forward_sum < back_sum){
  93.                 if(forward <= back_cap){
  94.                     again = true;
  95.                     forward_sum = forward_sum + route[forward];
  96.                     ++forward;
  97.  
  98.                     if(forward_sum < 0){
  99.                         front_cap = forward;
  100.                         forward_sum = 0;
  101.                     }
  102.                 }
  103.             } else{
  104.  
  105.                 if(back >= front_cap){
  106.                     again = true;
  107.                     back_sum = back_sum + route[back];
  108.                     --back;
  109.  
  110.                     if(back_sum < 0){
  111.                         back_cap = back;
  112.                         back_sum = 0;
  113.                     }
  114.                 }
  115.             }
  116.         }
  117.         cout<<getValue();
  118.     }
  119.  
  120.     /*void calculate(){
  121.         //cout<<"Oblicz"<<endl;
  122.         bool again = true;
  123.  
  124.         while(again){
  125.             again = false;
  126.  
  127.             if(forward <= back_cap){
  128.                 again = true;
  129.                 forward_sum = forward_sum + route[forward];
  130.                 ++forward;
  131.  
  132.                 if(forward_sum < 0){
  133.                     front_cap = forward;
  134.                     forward_sum = 0;
  135.                 }
  136.             }
  137.  
  138.             if(back >= front_cap){
  139.                 again = true;
  140.                 back_sum = back_sum + route[back];
  141.                 --back;
  142.  
  143.                 if(back_sum < 0){
  144.                     back_cap = back;
  145.                     back_sum = 0;
  146.                 }
  147.             }
  148.         }
  149.         cout<<getValue();
  150.     }*/
  151.  
  152.     int getValue(){
  153.         int score = 0;
  154.         for(int i=front_cap; i <= back_cap; ++i){
  155.             score = score + route[i];
  156.         }
  157.         return score;
  158.     }
  159. };
  160.  
  161. int main(){
  162.     int quantity;
  163.     cin>>quantity;
  164.  
  165.     Route *route = new Route(quantity);
  166.     route->getData();
  167.     route->calculate();
  168. }
  169.  
  170. /*
  171. 5
  172. 1
  173. -2
  174. 4
  175. 5
  176. -2
  177.  
  178.  
  179. 3
  180. 10 -11 1
  181.  
  182.  
  183. 20
  184. 1
  185. 2
  186. -100
  187. 3
  188. 4
  189. -100
  190. 10
  191. -3
  192. -4
  193. -2
  194. 7
  195. -100
  196. 5
  197. -100
  198. 4
  199. 2
  200. -100
  201. 1
  202. 5
  203. -100
  204. */
  205.  
Success #stdin #stdout 0s 4408KB
comments (?)
stdin
copy 
20
1
2
-100
3
4
-100
10
-3
-4
-2
7
-100
5
-100
4
2
-100
1
5
-100
stdout
copy 
10
https://ideone.com/xYcaJ2
problem FZI_STEF, based on SPOJ submission 22198016 (C++ 4.3.2), 2018-08-22 13:37:54
language:
C++ 4.3.2 (gcc-4.3.2)
created:
5 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!