Untitled

 avatar
Whido
plain_text
a year ago
1.9 kB
6
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

int calc(vector<vector<int>> &dp,int p,int a,vector<pair<int,int>> &v,int n){
    if((p+a)>=n){return 0;}
    if(dp[p][a]!=-1){return dp[p][a];}
    int ans=INT_MAX;
    if(p<n/2 && p<a){
        ans = min(ans,calc(dp,p+1,a,v,n) + v[p+a].first);
    }
    if(a<n/2){
        ans = min(ans,calc(dp,p,a+1,v,n) + v[p+a].second);
    }

    dp[p][a]=ans;
    return dp[p][a];
}
 
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++){
        int n;
        cin>>n;
        vector<pair<int,int>> v(n);
        for(int x=0;x<n;x++){
            cin>>v[x].first;
            cin>>v[x].second;
        }
        //reverse(all(v));
        vector<vector<int>> dp(5001,vector<int>(5001,-1));
        cout<<calc(dp,0,0,v,n)<<endl;
        
        
        //cout << "Case #" << g << ": ";
        
    }
 
    return 0;
}