Submission #731780

#	Time	Username	Problem	Language	Result	Execution time	Memory
731780		thienhx	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	195 ms	14992 KiB

bulves

#include "bits/stdc++.h"
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
 
using ll = long long;   
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using str = string;
using ld = long double;
using db = double;
//--------------------
#define           F   first
#define           S   second
#define          pb   push_back
#define       sz(x)   (int)((x).size())
#define      all(x)   (x).begin(), (x).end()
#define     rall(x)   (x).rbegin(), (x).rend()
#define    mem(f,x)   memset(f , x , sizeof(f))
#define __lcm(x, y)   (1LL * ((x) / __gcd((x), (y))) * (y))

template<class T> bool maximize(T &a,const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a,const T &b){ return (a > b ? a = b, 1 : 0); }
//--------------------
#define PROBLEM "test"

const int MOD = 1e9 + 7; // 998244353;
const ll INF = 1e18;
const db PI = acos(-1);
const int dx[4]{0, 1, 0, -1}, dy[4]{1, 0, -1, 0}; // U R D L
const int ddx[4]{-1, 1, 1, -1}, ddy[4]{1, 1, -1, -1}; // UR DR DL UL
const int kx[8]{1, 1, 2, 2, -1, -1, -2, -2}, ky[8]{-2, 2, -1, 1, -2, 2, -1, 1};

//-----------------[PROBLEM SOLUTION]-----------------//

void solve() {
    ll n, res = 0, pref = 0;
    cin >> n;

    ll x, y;
    priority_queue<ll> pq;
    for (int i = 0; i < n; i++) pq.push(0);
    for (int i = 0; i < n - 1; i++) {
        cin >> x >> y;

        pref += x - y;

        pq.push(pref);

        if (pref < pq.top()) {
            res += pq.top() - pref; 
            pq.pop(); pq.push(pref);
        }
    }

    cin >> x >> y;
    pref += x - y;
    while(pq.size() && pref < pq.top())
        res += pq.top() - pref, pq.pop();

    cout << res << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (fopen(PROBLEM".inp", "r")){
        freopen(PROBLEM".inp", "r", stdin);
        freopen(PROBLEM".out", "w", stdout);
    }

    constexpr bool MULTI_TEST = 0;
    int t = 1;
    if(MULTI_TEST) cin >> t;
    while(t--)
        solve();
}

Compilation message (stderr)

bulves.cpp: In function 'int main()':
bulves.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen(PROBLEM".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bulves.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(PROBLEM".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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