Submission #1254964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254964		magic_trip	Potatoes and fertilizers (LMIO19_bulves)	C++20	0 / 100	1093 ms	1096 KiB

bulves

#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];
int prv[2][30001*2];
const int OFF = 30000;
int n_mn, n_mx;
inline void get(int i, int j, int k){
    if(prv[i&1][j] == i)dp[i&1][j] = min(dp[i&1][j],k);
    else dp[i&1][j] = k;
    prv[i&1][j] = i;
    n_mn = min(n_mn,j);
    n_mx = max(n_mx,j);
}
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];
    dp[1][OFF] = 0;
    prv[1][OFF] = 1;
    int mn = OFF, mx = OFF;
    for(int i = 1 ; i <= n ; i++){
        n_mn = OFF*2, n_mx = 0;
        for(int j = mn ; j <= mx ; j++)if(prv[i&1][j] == i){
//            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{
                    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]));
                    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);
                }
            }
        }
        mn=n_mn,mx=n_mx;
    }
    cout<<dp[n+1&1][OFF];
}

//#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;
//    srand(time(0));
//    while(1){
//        n = 5;
//        vector<int> A(n+1), B(n+1);
//        ll ans = 0;
//        ll a = 0, b = 0;
//        for(int i = 1 ; i < n ; i++){
//            A[i] = rand()%10, B[i] = rand()%10;
//            a+=A[i],b+=B[i];
//            ans += abs(a-b);
//        }
//        if(a>b)B[n] = a-b;
//        else A[n] = b-a;
//        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);
//                    }
//                }
//            }
//        }
//        if(dp[n+1&1][OFF] != ans){
//            cout<<n<<endl;
//            for(int i = 1 ; i <= n ; i++)cout<<A[i]<<" \n"[i==n];
//            for(int i = 1 ; i <= n ; i++)cout<<B[i]<<" \n"[i==n];
//            cout<<ans<<" "<<dp[n+1&1][OFF]<<endl;
//            return 0;
//        }
//    }
//    cout<<dp[n+1&1][OFF];
//}
/*
 5
 6 8
 4 6
 8 5
 0 8
 9 0
 
 6 4 8 0 9
 8 6 5 8 0
 */

• Subtask 1: 0 / 24
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 36