Submission #1254961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254961		magic_trip	Potatoes and fertilizers (LMIO19_bulves)	C++20	0 / 100	1093 ms	932 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];
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{
                    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);
                }
            }
        }
    }
    cout<<dp[n+1&1][OFF];
}

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