Submission #943923

#TimeUsernameProblemLanguageResultExecution timeMemory
943923penguin133Potatoes and fertilizers (LMIO19_bulves)C++17
100 / 100
116 ms21280 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pi pair<int, int> #define pii pair<int, pi> #define fi first #define se second #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #endif mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); int dp[2][30005]; int n, A[500005], B[500005]; void solve(){ cin >> n; for(int i = 1; i <= n; i++)cin >> A[i] >> B[i], A[i] -= B[i], A[i] += A[i - 1]; /* for(int i = 1; i <= n; i++){ for(int j = 0; j <= 30000; j++){ if(j)dp[i & 1][j] = min(dp[i & 1][j - 1], dp[(i - 1) & 1][j] + abs(A[i] - j)); else dp[i & 1][j] = dp[(i - 1) & 1][j] + abs(A[i] - j); } } */ int ans = 0; priority_queue <int> pq; for(int i = 1; i <= n; i++){ pq.push(A[i]); pq.push(A[i]); ans += abs(max(0ll, min(A[n], pq.top())) - A[i]); pq.pop(); } //while(!pq.empty() && pq.top() > A[n])ans -= (pq.top() - A[n]), pq.pop(); cout << ans; //cout << dp[n & 1][A[n]]; } main(){ ios::sync_with_stdio(0);cin.tie(0); int tc = 1; //cin >> tc; for(int tc1=1;tc1<=tc;tc1++){ // cout << "Case #" << tc1 << ": "; solve(); } }

Compilation message (stderr)

bulves.cpp:41:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   41 | main(){
      | ^~~~
#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...