Submission #706309

#	Time	Username	Problem	Language	Result	Execution time	Memory
706309		MinhAnhnd	Cigle (COI21_cigle)	C++14	0 / 100	1 ms	1424 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 201

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 temp;
    long A[sizeofA];
    long Sum[sizeofA] ={};
    int have[sizeofA*sizeofA] = {};
    cin>>A[1];
    N = N-2;
    n = N;
    for (long i = 1;i<=N;i++){
        cin>>A[i];
        Sum[i] = Sum[i-1] + A[i];
        have[Sum[i]] = i;
    }
    long i_val[sizeofA] = {};
    cin>>temp;
    vector<pair<long,long>> to_get[sizeofA];
    long ans = 0;
    vector<pair<long,long>> to_modify[sizeofA+3];

    for (long i = 1;i<=N;i++){
        for (auto k: to_modify[i]){

            long pivot = k.first;
            i_val[pivot] = max(i_val[pivot],k.second);
            modify(pivot,i_val[pivot]);
            //cout<<k.first<<" "<<k.second<<" "<<i<<endl;
        }
        long need = Sum[i]*2;
        long number_up = 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;
                //
                ans = max(current_val,ans);
                //cout<<lower_end<<" "<<pivot<<" "<<current_val<<" "<<upper_end<<" "<<delta<<endl;

                //cout<<lower_end<<" "<<pivot<<" "<<current_val<<" "<<upper_end<<" "<<endl;
                to_modify[upper_end+1].push_back(make_pair(pivot,current_val));

                //modify(pivot,i_val);

                /*for (long i = 1;i<=N*2;i++){
                    cout<<t[i]<<" ";

                }; cout<<endl;*/
            }
        }
    }
    cout<<ans;
}

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