Submission #1185849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185849		hmms127	Divide and conquer (IZhO14_divide)	C++20	17 / 100	0 ms	328 KiB

divide

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename key>
// for ordered set or indexed set
using ordered_set= tree<key, null_type, less<key>, rb_tree_tag, tree_order_statistics_node_update>; // less_equal
#define f1(n) for(int i=0;i<n;i++)
#define e '\n'
#define f2(m,n,q) for(int i=m;i<n;i+=q)
#define f3(n) for(int j=0;j<n;j++)
#define f4(m,n,q) for(int j=m;j<n;j+=q)
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int long long
#define pb push_back
//f^=1 == if(f==0)f=1 else f=0
typedef long long ll;
const int N=15000001;
const int mod=1e9+7;
const int inf=1e9,sqr=448;
int32_t main()
{
     speed;
     int tt=1;//cin>>tt;
     while(tt--){
        //freopen("herding.in","r",stdin);
        //freopen("herding.out","w",stdout);
        int n;cin>>n;
        array<int,3>a[n];f1(n)cin>>a[i][0]>>a[i][1]>>a[i][2];
        array<int,3>pref[n];
        pref[0][0]=a[0][0],pref[0][1]=a[0][1],pref[0][2]=a[0][2];
        f2(1,n,1){
          pref[i][0]=pref[i-1][0]+a[i][0];
          pref[i][1]=pref[i-1][1]+a[i][1];
          pref[i][2]=pref[i-1][2]+a[i][2];
        }
        int ans=0;
        f1(n){
          int l=i,r=n-1;
          while(l<=r){
            int mid=(l+r)/2;
            int calc=(pref[mid][2]-(i>0 ? pref[i-1][2]:0))-(a[mid][0]-a[i][0]);
            if(calc>=0)ans=max(ans,pref[mid][1]-(i>0 ? pref[i-1][1]:0)),l=mid+1;
            else r=mid-1;
          }
        }
        cout<<ans;

     }
}

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