oj.uz

답안 #706280

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
706280 2023-03-06T08:41:09 Z MinhAnhnd Cigle (COI21_cigle) C++14
0 / 100
 56 ms 99328 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 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];

    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]);
        }
        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];
                //cout<<lower_end-1<<" "<<pivot<<endl;
                long current_val = query(0,lower_end-1) + number_up;
                ans = max(current_val,ans);
                to_modify[upper_end].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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 98536 KB Output is correct
2 Correct 54 ms 98488 KB Output is correct
3 Correct 46 ms 98488 KB Output is correct
4 Correct 47 ms 98508 KB Output is correct
5 Incorrect 47 ms 98536 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 98536 KB Output is correct
2 Correct 54 ms 98488 KB Output is correct
3 Correct 46 ms 98488 KB Output is correct
4 Correct 47 ms 98508 KB Output is correct
5 Incorrect 47 ms 98536 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 99328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 98536 KB Output is correct
2 Correct 54 ms 98488 KB Output is correct
3 Correct 46 ms 98488 KB Output is correct
4 Correct 47 ms 98508 KB Output is correct
5 Incorrect 47 ms 98536 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 98536 KB Output is correct
2 Correct 54 ms 98488 KB Output is correct
3 Correct 46 ms 98488 KB Output is correct
4 Correct 47 ms 98508 KB Output is correct
5 Incorrect 47 ms 98536 KB Output isn't correct
6 Halted 0 ms 0 KB -