Submission #382125

#	Time	Username	Problem	Language	Result	Execution time	Memory
382125		mohamedsobhi777	Divide and conquer (IZhO14_divide)	C++14	48 / 100	1052 ms	2284 KiB

divide

#include <bits/stdc++.h>

using namespace std;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define lb lower_bound
#define ub upper_bound

using ll = long long;
using ld = long double;

const int N = 1e5 + 7;
const ll mod = 1e9 + 7;

int n;
ll g[N], e[N];
ll x[N];

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
       cin >> n;
       ll ans = 0;
       for (int i = 0; i < n; ++i)
       {
              cin >> x[i] >> g[i] >> e[i];
              ans = max(ans, g[i]);
       }
       for (int i = 1; i < n; ++i)
       {
              g[i] += g[i - 1];
              e[i] += e[i - 1];
       }

       vector<int> qu;

       qu.pb(0);

       auto get = [&](int a) -> int {
              return x[a] - (a ? e[a - 1] : 0);
       };
       for (int i = 1; i < n; ++i)
       {
              ll mv = get(i) - e[i] + e[i - 1];
              int my_cover = partition_point(all(qu), [&](int j) {
                                    return get(j) < mv;
                             }) -
                             qu.begin();
              if (my_cover < sz(qu))
              {
                     ans = max(ans, g[i] - (my_cover ? g[qu[my_cover - 1]] : 0));
              }
              if (get(i) > get(qu.back()))
              {
                     qu.push_back(i);
              }
       }
       ans = 0 ; 
       for(int i = 0 ;i < n;++ i){
              for(int j = i ; j< n; ++ j){
                     if(x[j] - x[i] <= e[j] - (i ? e[i - 1] : 0)){
                            ans = max(ans, g[j] - (i ? g[i - 1] : 0)) ;
                     }
              }
       }
       cout << ans;
       return 0;
}

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