fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long dp[5100];						//storing solution for each addition of 2 new pilots.(2*i) & (2*i)+1. 
  4. long long capt[10200],asis[10200];		//salary for captain and assistant for each i.
  5. int parr[10200];						//storing partners for each i.
  6. int main(){
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(0);
  9.     cout.tie(0);
  10.     int n,f,f1;
  11.     cin>>n;
  12.     long long x,y;
  13.     for(int i=0;i<n;i++)
  14.         cin>>capt[i]>>asis[i];
  15.     dp[0]=capt[1]+asis[0];				//solution for first pair
  16.     parr[0]=1;							//1st pilot paired with 2nd and vice versa.
  17.     parr[1]=0;
  18.     for(int i=1;i<(n/2);i++){
  19.         x=dp[i-1]+asis[2*i]+capt[(2*i)+1];		//if the 2 new added pilots are paired with each other
  20.         f=2*i;									//f stores the partner of (2*i)+1
  21.         f1=(2*i)+1;								//f1 stores the partner of (2*i)
  22.         for(int j=0;j<(2*i);j++){
  23.             if(parr[j]<j){						//if j's partner is less than j
  24.                 y=dp[i-1]-capt[j]+capt[2*i]+capt[(2*i)+1]+asis[j];	
  25.                 if(y<x){				
  26.                     f=j;
  27.                     f1=parr[j];
  28.                     x=y;
  29.                 }
  30.             }
  31.             else if(parr[j]>j){					//if j's partner is greater than j
  32.                 y=dp[i-1]-capt[parr[j]]+capt[2*i]+capt[(2*i)+1]+asis[parr[j]];
  33.                 if(y<x){
  34.                     f=parr[j];
  35.                     f1=j;
  36.                     x=y;
  37.                 }
  38.             }
  39.         }
  40.         parr[(2*i)+1]=f;
  41.         parr[2*i]=f1;
  42.         dp[i]=x;
  43.     }
  44.     cout<<dp[(n/2)-1]<<"\n";
  45.     return 0;
  46. }
  47.  
Success #stdin #stdout 0s 3644KB
comments (?)
stdin
copy 
6 
10000 7000 
9000 3000 
6000 4000 
5000 1000 
9000 3000 
8000 6000
stdout
copy 
32000
https://ideone.com/QJtb9E
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!