Submission #415339

#	Time	Username	Problem	Language	Result	Execution time	Memory
415339		gmyu	Potatoes and fertilizers (LMIO19_bulves)	C++14	100 / 100	249 ms	22924 KiB

bulves

/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/LMIO19_bulves
*/
#include <iostream>  //cin , couta
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <string.h>
#include <set>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define ff  first
#define ss  second
#define pb  push_back
#define sz(x)   (int)(x).size()

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 500007
#define MAXE 100007


bool debug;

int N;
ll a[MAXV], b[MAXV], ps[MAXV];

int main() {
    debug = false;
    ios_base::sync_with_stdio(false); cin.tie(0);

    ll ans = 0LL;
    priority_queue<ll> pq;

    cin >> N;
    for(int i=1;i<N;i++) {
        cin >> a[i] >> b[i];
        ps[i] = (a[i]-b[i]) + ps[i-1];
        if(ps[i] >= 0) {
            ans += ps[i];   /// move downstream
            pq.push(ps[i]); /// option of not moving to next node; move it back from upstream
            pq.push(ps[i]); /// option of not even move anything from 1 .. i
            pq.pop();
        } else {    // do not have extra to move downstream
            ans += -ps[i]; /// borrow those from downstream
            pq.push(0); /// nothing to move to next node
            pq.push(0); /// nothing to cancel
            pq.pop();
        }
    }

    cin >> a[N] >> b[N];
    ps[N] = a[N] - b[N] + ps[N-1];
    for(int i=1; i<=N && !pq.empty(); i++) {
        ans -= min(pq.top(), ps[N]);    /// max you can move from upstream
        pq.pop();
    }

    cout << ans << endl;

    if(debug) cout << endl << "EOL" << endl;

}
/**
6
1 2
0 0
2 0
0 0
0 0
0 1

7
2 0
2 0
2 0
0 5
2 0
2 0
2 0

*/

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