Submission #106269

#	Time	Username	Problem	Language	Result	Execution time	Memory
106269		Frankenween	Divide and conquer (IZhO14_divide)	C++17	17 / 100	49 ms	5668 KiB

divide

#include <bits/stdc++.h>


//#define _FORTIFY_SOURCE 0
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ull unsigned long long
#define pii pair<ll, ll>
#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define deb(x) cout << #x << " = " << x << endl
#define all(x) x.begin(), x.end()
#define vi vector<ll>

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e18;
const long double e = 2.718281828459;
const long double pi = atan2l(0, -1);


using namespace std;


template <class T>
istream& operator>>(istream &in, vector<T> &arr) {
    for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
};


struct mine {
    ll x, gold, en;
};


void solve() {
    ll n;
    cin >> n;
    vector<mine> line(n);
    for (int i = 0; i < n; i++) {
        cin >> line[i].x >> line[i].gold >> line[i].en;
    }
    ll ans = 0;
    ll cnt_gold = 0, cnt_en = 0;
    ll l = 0, r = -1;
    while (r < n - 1) {
        if (line[r + 1].x - line[l].x <= cnt_en + line[r + 1].en) {
            cnt_gold += line[r + 1].gold;
            cnt_en += line[r + 1].en;
            r++;
        } else {
            cnt_gold -= line[l].gold;
            cnt_en -= line[l].en;
            l++;
        }
        ans = max(ans, cnt_gold);
    }
    cout << ans;
}


int main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#else
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cout.precision(30);
    srand(time(0));
    cout.setf(ios::fixed);
    solve();
    return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 31
• Subtask 3: 0 / 52