Submission #384664

#	Time	Username	Problem	Language	Result	Execution time	Memory
384664		zoooma13	Divide and conquer (IZhO14_divide)	C++14	0 / 100	1 ms	364 KiB

divide

#include <bits/stdc++.h>
using namespace std;

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

divide.cpp: In function 'int main()':
divide.cpp:10: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=]
   10 |         scanf("%lld%lld%lld",&x[0],&x[1],&x[2]);
      |                ~~~^
      |                   |
      |                   long long int*
      |                %ld
divide.cpp:10: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=]
   10 |         scanf("%lld%lld%lld",&x[0],&x[1],&x[2]);
      |                    ~~~^
      |                       |
      |                       long long int*
      |                    %ld
divide.cpp:10: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=]
   10 |         scanf("%lld%lld%lld",&x[0],&x[1],&x[2]);
      |                        ~~~^
      |                           |
      |                           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:10:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 |         scanf("%lld%lld%lld",&x[0],&x[1],&x[2]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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