Submission #1249240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249240		nqknht	Divide and conquer (IZhO14_divide)	C++20	100 / 100	20 ms	6728 KiB

divide

#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second
#define len(s) (int)s.size()
#define LS(x) (1 << x)

const int I = 2e5 + 9;

using namespace std;

ll n, pfD[I], pfG[I], minD[I][3], rs = 0;

struct mix
{
    ll x, g, d;
} a[I];

int main()
{
#define TN "divide"
    if (fopen(TN ".in", "r"))
    {
        freopen(TN ".in", "r", stdin);
        freopen(TN ".out", "w", stdout);
    }
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].x >> a[i].g >> a[i].d;
        pfD[i] = pfD[i - 1] + a[i].d;
        pfG[i] = pfG[i - 1] + a[i].g;
        ll D = pfD[i - 1] - a[i].x;
        if (i == 1)
        {
            minD[i][0] = D;
            minD[i][1] = i;
        }
        else if (minD[i - 1][0] > D)
        {
            minD[i][0] = D;
            minD[i][1] = i;
        }
        else
        {
            minD[i][0] = minD[i - 1][0];
            minD[i][1] = minD[i - 1][1];
        }
        int l_ = 1, r_ = i, tg, sav = -1;
        // if(i == 3) cout << D << "\n";
        while (l_ <= r_)
        {
            tg = (l_ + r_) / 2;
            if (minD[tg][0] <= pfD[i] - a[i].x)
            {
                sav = tg;
                r_ = tg - 1;
            }
            else
                l_ = tg + 1;
        }
        rs = max(rs, pfG[i] - pfG[sav - 1]);
    }
    cout << rs;
    return 0;
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen(TN ".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
divide.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen(TN ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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