Submission #989740

#TimeUsernameProblemLanguageResultExecution timeMemory
989740samek08Potatoes and fertilizers (LMIO19_bulves)C++14
64 / 100
125 ms262144 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define rep(a,b) for(int a = 0; a < (b); ++a) #define all(t) t.begin(), t.end() #define pb push_back const int MAXN = 5e5+5, INF = 1e9+50; const ll INF_L = (ll)1e18+(ll)50000; int n; int A[MAXN]; int B[MAXN]; int C[MAXN]; ll S[MAXN]; vector<ll> stan; vector<vector<ll>> dp; void solve() { cin >> n; rep(i,n) cin >> A[i] >> B[i]; rep(i,n) C[i] = A[i]-B[i]; //rep(i,n) cin >> C[i]; S[0] = C[0]; for(int i = 1; i < n; ++i) S[i] = S[i-1] + C[i]; set<ll> fg; rep(i,n) { if(S[i] >= 0 and S[i] <= S[n-1]) fg.insert(S[i]); } fg.insert(0); for(auto it = fg.begin(); it != fg.end(); ++it) stan.pb(*it); dp.assign(n,{}); rep(i,n) dp[i].assign((int)stan.size(),INF_L); //rep(i,n) cout << S[i] << ' '; //cout << '\n'; rep(i,n) { ll mn = INF_L; rep(j,(int)stan.size()) { if(i > 0) mn = min(mn,dp[i-1][j]); dp[i][j] = abs(S[i]-stan[j]); if(i > 0) { if(mn == INF_L) dp[i][j] = INF_L; else dp[i][j] += mn; } } } /*rep(i,n) { rep(j,(int)stan.size()) cout << dp[i][j] << ' '; cout << '\n'; } */ ll mn = INF_L; rep(i,(int)stan.size()) mn = min(mn,dp[n-1][i]); cout << mn << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T = 1; //cin >> T; while(T--) solve(); return 0; }
#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...