제출 #204853

#제출 시각아이디문제언어결과실행 시간메모리
204853awlintqaa휴가 (IOI14_holiday)C++14
7 / 100
22 ms2936 KiB
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #include <bits/stdc++.h> using namespace std; #define sqr 200 #define mid (l+r)/2 #define pb push_back #define ppb pop_back #define fi first #define se second #define lb lower_bound #define ub upper_bound #define ins insert #define era erase #define C continue #define mem(dp,i) memset(dp,i,sizeof(dp)) #define mset multiset typedef long long ll; typedef short int si; typedef long double ld; typedef pair<int,int> pi; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll; const ll mod=1e9+7; const ll inf= 4e18; const ld pai=acos(-1); #include"holiday.h" map<ll,ll>id12,id21; struct NODE{ ll sum,num; NODE *left,*right; NODE(){ sum=num=0; left=right=NULL; } }*version[3009]; void build(NODE *node,ll l,ll r){ if(l==r)return ; node->left=new NODE; node->right=new NODE; build(node->left,l,mid); build(node->right,mid+1,r); } void upd(NODE *pre,NODE *node,ll l,ll r,ll id,ll val){ if(l==r){ node->sum+=val; node->num++; return ; } if(id<=mid){ node->left=new NODE; node->right=pre->right; upd(pre->left,node->left,l,mid,id,val); } else{ node->left=pre->left; node->right=new NODE; upd(pre->right,node->right,mid+1,r,id,val); } node->num = node->left->num + node->right->num; node->sum = node->left->sum + node->right->sum; } ll query(NODE *L,NODE *R,ll l,ll r,ll k,ll ans){ if(l==r)return ans+id21[l]*min(k,R->num-L->num); ll NUM= R->right->num - L->right->num ; ll SUM= R->right->sum - L->right->sum ; if(NUM<=k)return query(L->left,R->left,l,mid,k-NUM,ans+SUM); return query(L->right , R->right,mid+1,r,k,ans); } ll findMaxAttraction(int n, int start, int d, int a[]) { ll N =0; set<ll>s; for(ll i=0;i<n;i++)s.ins(a[i]); for(auto u:s)id12[u]=N,id21[N]=u,N++; version[0]=new NODE; build(version[0],0,N); for(ll i=0;i<n;i++){ version[i+1]=new NODE; upd(version[i],version[i+1],0,N,id12[a[i]] , a[i] ); } ll mx=0; for(ll i=0;i<n;i++){ for(ll j=i;j<n;j++){ if(i<=start && j>=start){ ll D=d - (j-i) - min( abs(start-i) , abs(start-j) ); D = min ( D , j-i+1); if(D>0)mx=max(mx, query(version[i],version[j+1],0,N,D,0) ) ; } } } return mx; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...