Submission #1118073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118073		kevinyang	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	387 ms	112968 KiB

bulves

#include <bits/stdc++.h>
using namespace std;
#define int long long

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

struct Slope{
    int val; // val at x = 0
    int slope; // slope at x = 0
    multiset<int>s;
    Slope(int val, int slope, vector<int>vals) : val(val), slope(slope){
        for(int nxt: vals){
            s.insert(nxt);
        }
    }
    Slope(){

    }
    vector<int> getSlopes(){
        vector<int>ans;
        for(int nxt: s){
            ans.push_back(nxt);
        }
        return ans;
    }
};

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int>a(n+1);
    int ans = 0;
    for(int i = 1; i<=n; i++){
        int x,y;
        cin >> x >> y;
        a[i] = x-y;
        a[i] += a[i-1];
    }
    for(int i = 1; i<=n; i++){
        if(a[i] < 0){
            ans -= a[i];
            a[i] = 0;
        }
    }
    int pt = a[n];
    vector<Slope>s(n+1);
    for(int i = 1; i<=n; i++){
        s[i] = Slope(a[i],-1,{a[i],a[i]});
    }
    Slope t = s[1];
   // cerr << t.s.size() << '\n';
    t.s.erase(--t.s.end());
   // cerr << "hi\n";
    for(int i = 2; i<=n; i++){
        t.val += s[i].val;
        t.slope--;
        for(int nxt: s[i].s){
            t.s.insert(nxt);
        }
        t.s.erase(--t.s.end());
    }
   // cerr << "hi\n";
    int cur = 0;
    int val = t.val;
    int slope = t.slope;
    for(int nxt: t.s){
        if(nxt > pt){
            break;
        }
        val+= slope*(nxt-cur);
        cur = nxt;
        slope++;
    }
    val += slope * (pt - cur);
    cout << val + ans << '\n';
    return 0;
}

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