Untitled
Whido
plain_text
2 years ago
2.1 kB
10
Indexable
#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; }
Editor is loading...