제출 #1254961

#제출 시각아이디문제언어결과실행 시간메모리
1254961magic_tripPotatoes and fertilizers (LMIO19_bulves)C++20
0 / 100
1093 ms932 KiB
#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]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...