oj.uz

Submission #384666

# Submission time Handle Problem Language Result Execution time Memory
384666 2021-04-02T03:55:33 Z zoooma13 Divide and conquer (IZhO14_divide) C++14
0 / 100
 2 ms 364 KB 
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    scanf("%d",&n);
    vector <array<int64_t ,3>> a(n);
    int64_t ans = 0;
    for(auto&x : a)
        scanf("%lld%lld%lld",&x[0],&x[1],&x[2]) ,ans = max(ans ,x[1]);
    set <pair<int ,int>> ss;
    a.insert(a.begin() ,{0,0,0});
    for(int i=1; i<=n; i++){
        a[i][1] += a[i-1][1];
        a[i][2] += a[i-1][2];

        auto it = ss.upper_bound({a[i][2] - a[i][0] ,0});
        if(it != ss.begin()){
            it = prev(it);
            ans = max(ans ,a[i][1] - it->second);
        }

        it = ss.insert({a[i-1][2] + a[i][0] ,a[i-1][1]}).first;
        if(it == ss.begin() || prev(it)->second > it->second){
            while(next(it) != ss.end() && next(it)->second >= it->second)
                ss.erase(next(it));
        }else{
            ss.erase(it);
        }
        ///a[i][2] - a[i][0] >= a[j][2] + a[j][0]
    }
    printf("%lld\n",ans);
}

Compilation message

divide.cpp: In function 'int main()':
divide.cpp:11:19: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'std::array<long int, 3>::value_type*' {aka 'long int*'} [-Wformat=]
   11 |         scanf("%lld%lld%lld",&x[0],&x[1],&x[2]) ,ans = max(ans ,x[1]);
      |                ~~~^
      |                   |
      |                   long long int*
      |                %ld
divide.cpp:11:23: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type 'std::array<long int, 3>::value_type*' {aka 'long int*'} [-Wformat=]
   11 |         scanf("%lld%lld%lld",&x[0],&x[1],&x[2]) ,ans = max(ans ,x[1]);
      |                    ~~~^
      |                       |
      |                       long long int*
      |                    %ld
divide.cpp:11:27: warning: format '%lld' expects argument of type 'long long int*', but argument 4 has type 'std::array<long int, 3>::value_type*' {aka 'long int*'} [-Wformat=]
   11 |         scanf("%lld%lld%lld",&x[0],&x[1],&x[2]) ,ans = max(ans ,x[1]);
      |                        ~~~^
      |                           |
      |                           long long int*
      |                        %ld
divide.cpp:33:16: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int64_t' {aka 'long int'} [-Wformat=]
   33 |     printf("%lld\n",ans);
      |             ~~~^    ~~~
      |                |    |
      |                |    int64_t {aka long int}
      |                long long int
      |             %ld
divide.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    7 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
divide.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 |         scanf("%lld%lld%lld",&x[0],&x[1],&x[2]) ,ans = max(ans ,x[1]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -