Submission #706217

#	Time	Username	Problem	Language	Result	Execution time	Memory
706217		MinhAnhnd	Cigle (COI21_cigle)	C++14	0 / 100	50 ms	98388 KiB

cigle

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#define ll unsigned long long

using namespace __gnu_pbds;

#define modu 1000003233

struct point{
    long index,outdegree;
};
//hyper_adj[a] -> b then (a before b)

bool ss(point a, point b){
    return a.outdegree>b.outdegree;
}

bool iss(point a, point b){
    return a.index>b.index;
}
ll multiply(ll a,ll b){
    return ((a%modu)*(b%modu))%modu;
}

ll sum(ll a,ll b){
    return ((a%modu)+(b%modu))%modu;
}

#define sizeofA 5001

long long  N;

//hyper_adj[a] -> b then (a before b)

const long long  Nsize = sizeofA*2;  // limit for array size
long long  n;  // array size
long long  t[2 * Nsize] = {};

void build() {  // build the tree
  //for (long long  i = n - 1; i > 0; --i) t[i] = t[i<<1] + t[i<<1|1];
  //for (long long  i = n - 1; i > 0; --i) t[i] = t[i<<1] + t[i<<1|1];
  for (long long  i = n - 1; i > 0; --i) t[i] = max(t[i<<1],t[i<<1|1]);
}

void modify(long long  p, long long  value) {  // set value at position p
  //for (t[p += n] += value; p > 1; p >>= 1) t[p>>1] = t[p] + t[p^1];
  for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = max(t[p], t[p^1]);
}

long long  query(long long  l, long long  r) {  // sum on long long erval [l, r)
  long long  res = 0;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l&1) res = max(res,t[l++]) ;
    if (r&1) res = max(res,t[--r]) ;
  }
  return res;
}

int main(){
    ios_base::sync_with_stdio(0);
	cin.tie(0);
    cin>>N;
    long A[sizeofA];
    long Sum[sizeofA] ={};
    int have[sizeofA*sizeofA] = {};
    cin>>A[1];
    N = N-2;
    for (long i = 1;i<=N;i++){
        cin>>A[i];
        Sum[i] = Sum[i-1] + A[i];
        have[Sum[i]] = i;
    }
    vector<pair<long,long>> to_get[sizeofA];
    long ans = 0;

    for (long i = 1;i<=N;i++){
        long need = Sum[i]*2;
        long number_up = 0;
        long i_val = 0;
        for(long j = i-1;j>=0;j--){
            int delta = need - Sum[j];
            if (have[delta]>0){
                number_up++;
                //to_get[i].push_back(make_pair((long)j+1,(long)have[delta]));
                long lower_end = j+1;
                long pivot = i;
                long upper_end = have[delta];
                long current_val = query(0,lower_end-1) + number_up;
                i_val = max(i_val, current_val);
                ans = max(i_val,ans);
                modify(pivot,i_val);
            }
        }
    }
    cout<<ans;
}

Compilation message (stderr)

cigle.cpp: In function 'int main()':
cigle.cpp:91:22: warning: unused variable 'upper_end' [-Wunused-variable]
   91 |                 long upper_end = have[delta];
      |                      ^~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 52