Submission #415957

#TimeUsernameProblemLanguageResultExecution timeMemory
4159572548631Potatoes and fertilizers (LMIO19_bulves)C++17
30 / 100
3 ms460 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll,ll> ii; typedef complex<ld> cp; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; typedef vector<cp> vcp; typedef vector<ld> vld; typedef vector<vi> vvi; typedef vector<vll> vvll; typedef vector<vii> vvii; #define fastIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL) #define forw(i,l,r) for( int i = (l) ; i < (r) ; i++ ) #define forb(i,r,l) for( int i = (r) ; i >= (l) ; i-- ) #define log2i(x) (32 - __builtin_clz((x)) - 1) #define log2ll(x) (64 - __builtin_clzll((x)) - 1) #define Pi 3.141592653589793 #define sz(x) (int)x.size() #define mt make_tuple #define mp make_pair #define fi first #define se second #define pb push_back #define pf push_front #define pob pop_back #define pof pop_front #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() const int N = 5e3+7; int n; ll ans=0; int a[N],b[N],diff[N],d[N],dp[N][N]; priority_queue<ll> q; int main() { fastIO; //freopen("test.inp","r",stdin); //freopen("test.out","w",stdout); cin >> n; forw(i,1,n+1) { cin >> a[i] >> b[i]; diff[i]=a[i]-b[i]; d[i]=d[i-1]+diff[i]; } forw(i,1,n+1) { q.push(min(max(d[i],0),d[n])); q.push(min(max(d[i],0),d[n])); if(q.top()>d[i]) ans+=q.top()-d[i]; if(d[n]<d[i]) ans+=d[i]-d[n]; q.pop(); } cout << ans; 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...