Hacher Cup, C++ (gcc)

Hacher Cup

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

#define ll long long
#define ull unsigned long long
#define ld long double
#define ui unsigned int
#define f(i,n) for(int i = 0; i < n; i++)
#define ff(i, l, r) for(int i = l; i < (int)r; i++)
#define rf(i, r, l) for(int i = r; i > (int)l; i--)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define vvi vector<vi>
#define vvl vector<vl>
#define si set<int>
#define sl set<ll>
#define sii set<pii>
#define sll set<pll>
#define mii map<int, int>
#define mll map<ll, ll>
#define mipii map<int, pii>
#define mlpii map<int, pll>
#define mipll map<ll, pii>
#define mlpll map<ll, pll>
#define mivi map<int, vi>
#define mlvi map<ll, vi>
#define mlvl map<ll, vl>
#define mci map<char, int>
#define mcvi map<char, vi>
#define mcvl map<char, vl>
#define pb push_back
#define all a.begin(), a.end()
#define sz size()
#define inf INT_MAX
#define llinf LONG_LONG_MAX
#define int ll
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int go(pii arr[], int i, int last) {
    if(i < 0) {
        return 0;
    }
    
    int position = arr[i].F;
    int height = arr[i].S;
    
    int L = position - height;
    int R = position + height;
    
    // Left
    int ans0 = go(arr, i - 1, L);
    if(last == position || last == llinf) {
        ans0 += arr[i].S;
    }
    
    // Right
    int ans1 = go(arr, i - 1, position);
    if(last == R || last == llinf) {
        ans1 += arr[i].S;
    }
    
    // No cut
    int ans2 = go(arr, i - 1, last);
    
    return max(ans0, max(ans1, ans2));
}

void solve(int c) {
    cout << "Case #" << c << ": ";
    int n;
    cin >> n;
    
    pii arr[n + 3];
    for(int i = 0; i < n; i++) {
        int p, h;
        cin >> p >> h;
        arr[i] = {p, h};
    }
    sort(arr, arr + n);
    arr[n] = {arr[n - 1].F, 0};
    arr[n + 1] = {arr[n - 1].F + arr[n - 1].S, 0};
    arr[n + 2] = {llinf, 0};
    
    cout << "\n"<< go(arr, n + 2, llinf) << "\n";
}

signed main() {
    fast;
    int t = 1;
    cin >> t;
    for(int i = 0; i < t; i++) {
        solve(i + 1);
    }
    
    return 0;
}


run \| edit \| history \| help	0