Submission #514830

#	Time	Username	Problem	Language	Result	Execution time	Memory
514830		Be_dos	Divide and conquer (IZhO14_divide)	C++17	48 / 100	1012 ms	2572 KiB

divide

#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>

struct Point {
    int32_t x;
    int32_t gold, energy;
};
int main() {
    int32_t n;
    std::cin >> n;

    Point* points = new Point[n];
    for(int32_t i = 0; i < n; i++)
        std::cin >> points[i].x >> points[i].gold >> points[i].energy;

    int64_t* pref_sum = new int64_t[n + 1];
    pref_sum[0] = 0;
    for(int32_t i = 1; i <= n; i++)
        pref_sum[i] = pref_sum[i - 1] + points[i - 1].energy;

    int64_t* gold_pref_sum = new int64_t[n + 1];
    gold_pref_sum[0] = 0;
    for(int32_t i = 1; i <= n; i++)
        gold_pref_sum[i] = gold_pref_sum[i - 1] + points[i - 1].gold;

    int64_t ans = 0;
    for(int32_t i = 0; i < n; i++) {
        int64_t val = points[i].x - pref_sum[i + 1];
        for(int32_t j = 0; j <= i; j++)
            if(points[j].x - pref_sum[j] >= val)
                ans = std::max(ans, gold_pref_sum[i + 1] - gold_pref_sum[j]);
    }
    std::cout << ans;
    return 0;
}

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