oj.uz

Submission #382126

# Submission time Handle Problem Language Result Execution time Memory
382126 2021-03-26T12:41:04 Z mohamedsobhi777 Divide and conquer (IZhO14_divide) C++14
48 / 100
 30 ms 620 KB 
#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();
              for (auto u : qu)
              {
                     if (mv <= get(u))
                     {
                            ans = max(ans, g[i] - (u ? g[u - 1] : 0));
                            break;
                     }
              }
              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);
              }
       }
       cout << ans;
       return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Correct 2 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 2 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 2 ms 364 KB Output is correct
22 Correct 4 ms 364 KB Output is correct
23 Correct 21 ms 492 KB Output is correct
24 Correct 30 ms 512 KB Output is correct

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Correct 2 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 2 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 2 ms 364 KB Output is correct
22 Correct 4 ms 364 KB Output is correct
23 Correct 21 ms 492 KB Output is correct
24 Correct 30 ms 512 KB Output is correct
25 Correct 2 ms 492 KB Output is correct
26 Correct 4 ms 620 KB Output is correct
27 Incorrect 4 ms 620 KB Output isn't correct
28 Halted 0 ms 0 KB -