#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define COMP(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define MOD2 998244353
#define sz(x) (ll)x.size()
typedef __int128_t lll;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ll, pll> PP;
const ll Lnf = 2e18;
ll n;
int dp[2][30001*2];
const int OFF = 30000;
inline void get(int i, int j, int k){
if(~dp[i&1][j])dp[i&1][j] = min(dp[i&1][j],k);
else dp[i&1][j] = k;
}
int main(){
fast;
cin>>n;
vector<int> A(n+1), B(n+1);
for(int i = 1 ; i <= n ; i++)cin>>A[i]>>B[i];
memset(dp,-1,sizeof dp);
dp[1][OFF] = 0;
for(int i = 1 ; i <= n ; i++){
memset(dp[~i&1],-1, sizeof dp[~i&1]);
for(int j = 0 ; j <= OFF*2 ; j++)if(~dp[i&1][j]){
// cout<<i<<" "<<j-OFF<<" "<<dp[i][j]<<endl;
if(j<OFF){
if(A[i] <= B[i])get(i+1,j+A[i]-B[i],dp[i&1][j]+abs(OFF-j-A[i]+B[i]));
else{
for(int k = 0 ; k <= j-OFF+A[i]-B[i] ; k++)get(i+1,k+OFF,dp[i&1][j]+k);
}
}
else{
if(A[i] <= B[i]){
if(j+A[i]-B[i]<OFF)get(i+1,j+A[i]-B[i],dp[i&1][j]+abs(OFF-j-A[i]+B[i]));
else for(int k = 0 ; k <= j-OFF+A[i]-B[i] ; k++)get(i+1,k+OFF,dp[i&1][j]+k);
}
else{
for(int k = j-OFF ; k <= j-OFF+A[i]-B[i] ; k++)get(i+1,k+OFF,dp[i&1][j]+k);
}
}
}
}
cout<<dp[n+1&1][OFF];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |