oj.uz

Submission #106269

# Submission time Handle Problem Language Result Execution time Memory
106269 2019-04-17T17:53:04 Z Frankenween Divide and conquer (IZhO14_divide) C++17
17 / 100
 49 ms 5668 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 356 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 392 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Incorrect 3 ms 400 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 4 ms 768 KB Output is correct
3 Correct 6 ms 768 KB Output is correct
4 Correct 20 ms 2560 KB Output is correct
5 Correct 24 ms 2808 KB Output is correct
6 Correct 37 ms 5668 KB Output is correct
7 Correct 29 ms 4480 KB Output is correct
8 Correct 38 ms 4696 KB Output is correct
9 Correct 35 ms 4444 KB Output is correct
10 Incorrect 49 ms 4472 KB Output isn't correct
11 Halted 0 ms 0 KB -