oj.uz

Submission #1040326

# Submission time Handle Problem Language Result Execution time Memory
1040326 2024-08-01T01:11:59 Z vjudge1 Divide and conquer (IZhO14_divide) C++17
100 / 100
 19 ms 6504 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(a)              a.begin(), a.end()
#define Base                311
#define endl                '\n'
#define fi                  first
#define fii(i, a, b)        for(int i = a; i <= b; i++)
#define fid(i, a, b)        for(int i = a; i >= b; i--)
#define fill(a,n)           memset(a, n, sizeof(a));
#define getbit(i, j)        ((i >> j) & 1)
#define minimize(x, y)      x = (x > y ? y : x)
#define maximize(x, y)      x = (x < y ? y : x)
#define ins                 insert
// #define int                 long long
#define ll                  long long
#define maxn                1000006 
#define MOD                 1000000007
#define name                "file"
#define pb                  push_back
#define pii                 pair< int, int >
#define pll                 pair< long long , long long >
#define re                  return
#define sz(x)               int(x.size())
#define se                  second
#define ull                 unsigned long long

void ctime () { 
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock () / CLOCKS_PER_SEC << "ms\n" ;        
}

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

ll x[maxn], g[maxn], e[maxn];
ll mx[maxn];

int main(){
    iof();
    int n;
    cin >> n;
    fii(i, 1, n)
    {
        cin >> x[i] >> g[i] >> e[i];
        e[i] += e[i - 1];
        g[i] += g[i - 1];
        mx[i] = -1e13;
    }
    mx[n + 1] = -1e13;
    fid(i, n, 1) mx[i] = max(mx[i + 1], e[i] - x[i]);
    ll ans = 0;
    fii(i, 1, n)
    {
        int l = 1, r = n;
        int res = 0;
        while(l <= r) 
        {
            int mid = (l + r) / 2;
            if (mx[mid] >= e[i - 1] - x[i])
            {
                res = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        ans = max(ans, g[res] - g[i - 1]);
    }
    cout << ans;
    ctime();
    re 0;
}

Compilation message

divide.cpp: In function 'void iof()':
divide.cpp:35:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen ( name ".inp" , "r" , stdin );
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
divide.cpp:36:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen ( name ".out" , "w", stdout );
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Correct 0 ms 480 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 0 ms 360 KB Output is correct
9 Correct 0 ms 360 KB Output is correct
10 Correct 0 ms 360 KB Output is correct
11 Correct 0 ms 360 KB Output is correct
12 Correct 1 ms 360 KB Output is correct
13 Correct 0 ms 360 KB Output is correct
14 Correct 0 ms 476 KB Output is correct
15 Correct 0 ms 360 KB Output is correct
16 Correct 0 ms 360 KB Output is correct
17 Correct 1 ms 544 KB Output is correct
18 Correct 0 ms 360 KB Output is correct
19 Correct 1 ms 616 KB Output is correct
20 Correct 0 ms 360 KB Output is correct
21 Correct 1 ms 360 KB Output is correct
22 Correct 1 ms 360 KB Output is correct
23 Correct 1 ms 616 KB Output is correct
24 Correct 2 ms 616 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Correct 0 ms 480 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 0 ms 360 KB Output is correct
9 Correct 0 ms 360 KB Output is correct
10 Correct 0 ms 360 KB Output is correct
11 Correct 0 ms 360 KB Output is correct
12 Correct 1 ms 360 KB Output is correct
13 Correct 0 ms 360 KB Output is correct
14 Correct 0 ms 476 KB Output is correct
15 Correct 0 ms 360 KB Output is correct
16 Correct 0 ms 360 KB Output is correct
17 Correct 1 ms 544 KB Output is correct
18 Correct 0 ms 360 KB Output is correct
19 Correct 1 ms 616 KB Output is correct
20 Correct 0 ms 360 KB Output is correct
21 Correct 1 ms 360 KB Output is correct
22 Correct 1 ms 360 KB Output is correct
23 Correct 1 ms 616 KB Output is correct
24 Correct 2 ms 616 KB Output is correct
25 Correct 1 ms 616 KB Output is correct
26 Correct 2 ms 872 KB Output is correct
27 Correct 2 ms 872 KB Output is correct
28 Correct 10 ms 2904 KB Output is correct
29 Correct 10 ms 3380 KB Output is correct
30 Correct 19 ms 6504 KB Output is correct
31 Correct 15 ms 5372 KB Output is correct
32 Correct 15 ms 5384 KB Output is correct
33 Correct 18 ms 5224 KB Output is correct
34 Correct 16 ms 5224 KB Output is correct
35 Correct 19 ms 5736 KB Output is correct
36 Correct 19 ms 5748 KB Output is correct