Untitled

 avatar
Whido
plain_text
a year ago
2.1 kB
9
Indexable
Never
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h> 
#include <complex>
#include <queue>
#include <set>
#include <unordered_set>
#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <fstream>
 
using namespace std;
 
typedef unsigned long long ull;
typedef long long ll;
 
const ll mod  = 1e9+7;
const ll inf  = 5e18 ;
const ll minf = -inf ;
 
#define forn(i,e) for(ll i = 0; i < e; i++)
#define forsn(i,s,e) for(ll i = s; i < e; i++)
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define endl "\n"
#define ya cout<<"YES"<<endl
#define na cout<<"NO"<<endl

ll calc(vector<vector<ll>> &dp,ll idx,ll p,vector<pair<ll,ll>> &v){
    if(idx>=sz(v)){return 0;}
    if(dp[idx][p]!=-1){return dp[idx][p];}

    if(p==sz(v)/2){
        dp[idx][p]=v[idx].second + calc(dp,idx+1,p,v);
    }
    else if(((idx-p)==sz(v)/2)||(p==(idx - p))){
        dp[idx][p]=v[idx].first + calc(dp,idx+1,p+1,v);
    }
    else{
        ll ans1=1e8,ans2=1e8;
        ans1=v[idx].first + calc(dp,idx+1,p+1,v);
        ans2=v[idx].second + calc(dp,idx+1,p,v);
        dp[idx][p]=min(ans1,ans2);
    }
    return dp[idx][p];
}
 
int main()
{
    //facto();
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    ll t;
    t=1;
    for(ll g=1;g<=t;g++){
        ll n;
        cin>>n;
        vector<pair<ll,ll>> v(n);
        for(ll x=0;x<n;x++){
            cin>>v[x].first;
            cin>>v[x].second;
        }
        reverse(all(v));
        vector<vector<ll>> dp(n+2,vector<ll>((n/2) + 2,-1));
        cout<<calc(dp,0,0,v)<<endl;
        
        
        //cout << "Case #" << g << ": ";
        
    }
 
    return 0;
}