oj.uz

Submission #706217

# Submission time Handle Problem Language Result Execution time Memory
706217 2023-03-06T05:42:36 Z MinhAnhnd Cigle (COI21_cigle) C++14
0 / 100
 50 ms 98388 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 98340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 98340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 98388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 98340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 98340 KB Output isn't correct
2 Halted 0 ms 0 KB -