Submission #1043846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043846		vjudge1	Divide and conquer (IZhO14_divide)	C++17	100 / 100	50 ms	13392 KiB

divide

#include <bits/stdc++.h>
#define fi(i, a, b) for( int i = a; i <= b; i++ )
#define fid(i, a, b) for( int i = a; i >= b; i-- )
#define getbit(x, i) ((x>>i)&1)
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define st first
#define nd second
#define mp make_pair
#define HTManh ""
#define maxn 100009
#define endl '\n'
using namespace std;

int n;
ll x[100009], g[100009], d[100009];

ll gt[100009];
map<ll, int> dich;

ll bit[100009];

void update(int vt, ll gt)
{
    while(vt <= n)
    {
        bit[vt] = min(bit[vt], gt);
        vt += (vt & -vt);
    }
}

ll get(int vt)
{
    ll s = 1e18;
    while (vt > 0)
    {
        s = min(s, bit[vt]);
        vt -= (vt & -vt);
    }
    return s;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	if (fopen(HTManh".inp", "r"))
    {
        freopen(HTManh".inp", "r", stdin);
        freopen(HTManh".out", "w", stdout);
    }

    cin >> n;
    fi(i,1,n) cin >> x[i] >> g[i] >> d[i];
    fi(i,1,n) g[i] += g[i-1];
    fi(i,1,n) d[i] += d[i-1];
    fi(i,1,n) gt[i] = d[i-1] - x[i];
    sort(gt+1,gt+n+1);
    fi(i,1,n) dich[gt[i]] = i;
    fi(i,1,n) bit[i] = 1e18;
    ll res = 0;
    fi(i,1,n)
    {
        update(dich[d[i-1]-x[i]], g[i-1]);
        int dau = 1, cuoi = n;
        while(dau <= cuoi)
        {
            int giua = (dau+cuoi)/2;
            if (gt[giua] > d[i] - x[i]) cuoi = giua - 1;
            else dau = giua + 1;
        }
        //cout << g[i] - get(cuoi) << endl;
        res = max(res, g[i] - get(cuoi));
    }
    cout << res << endl;
}

Compilation message (stderr)

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

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