Untitled
Whido
plain_text
2 years ago
1.9 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 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; }
Editor is loading...