| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 344980 | mehrdad_sohrabi | 휴가 (IOI14_holiday) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
/// 500 485 462 A4
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=3e5+100;
ll seg[2][N*4];
ll ja[N];
ll a[N];
ll c[N];
ll dp[4][N];
ll n;
void upd(ll nod,ll l,ll r,ll id,ll di,ll val){
if (r-l==1){
seg[di][nod]+=val;
if (di==0) if (seg[di][nod]<0 || seg[di][nod]>1) cout << "KOS" << endl;
return ;
}
ll mid=(r+l)/2;
if (mid>id) upd(nod*2,l,mid,id,di,val);
else upd(nod*2+1,mid,r,id,di,val);
seg[di][nod]=seg[di][nod*2]+seg[di][nod*2+1];
}
ll get(ll nod,ll l,ll r,ll L,ll R,ll id){
if (l>=R || L>=r) return 0;
if (l>=L && r<=R) return seg[id][nod];
ll mid=(r+l)/2;
return get(nod*2,l,mid,L,R,id)+get(nod*2+1,mid,r,L,R,id);
}
ll where(ll nod,ll l,ll r,ll k){
if (r-l==1) return l;
ll mid=(r+l)/2;
if (seg[0][nod*2+1]>=k) return where(nod*2+1,mid,r,k);
else return where(nod*2,l,mid,k-seg[0][nod*2+1]);
}
void solve(ll l,ll r,ll L,ll R,ll id){
if (r<l) return ;
ll mid=(r+l)/2;
ll best=L,o=-1;
for (int i=L;i<=min(mid,R);i++){
upd(1,1,n+1,ja[i],0,1);
upd(1,1,n+1,ja[i],1,a[i]);
ll z=where(1,1,n+1,mid-i+1);
ll h=get(1,1,n+1,z,n+1,0);
// if (h!=mid-i+1){
// cout << h << " " << "KIR" << " " << mid-i+1 << endl;
//}
ll jav=get(1,1,n+1,z,n+1,1);
if (jav>o){
o=jav;
best=i;
}
}
for (int i=L;i<=min(mid,R);i++){
upd(1,1,n+1,ja[i],0,-1);
upd(1,1,n+1,ja[i],1,-a[i]);
}
if (o==-1) cout << "KIR" << endl;
dp[id][mid]=o;
solve(l,mid-1,L,best,id);
for (int i=L;i<best;i++){
upd(1,1,n+1,ja[i],0,1);
upd(1,1,n+1,ja[i],1,a[i]);
}
solve(mid+1,r,best,R,id);
for (int i=L;i<best;i++){
upd(1,1,n+1,ja[i],0,-1);
upd(1,1,n+1,ja[i],1,-a[i]);
}
}
void devide(ll l,ll r,ll L,ll R,ll id){
if (r<l) return ;
ll mid=(r+l)/2;
ll best=L,o=-1;
for (int i=L;i<=min(mid,R);i++){
upd(1,1,n+1,ja[i],0,1);
upd(1,1,n+1,ja[i],1,a[i]);
if (mid-i-i+2<=0) continue;
ll z=where(1,1,n+1,mid-i-i+2);
ll jav=get(1,1,n+1,z,n+1,1);
if (jav>o){
o=jav;
best=i;
}
}
for (int i=L;i<=min(mid,R);i++){
upd(1,1,n+1,ja[i],0,-1);
upd(1,1,n+1,ja[i],1,-a[i]);
}
dp[id][mid]=o;
devide(l,mid-1,L,best,id);
for (int i=L;i<best;i++){
upd(1,1,n+1,ja[i],0,1);
upd(1,1,n+1,ja[i],1,a[i]);
}
devide(mid+1,r,best,R,id);
for (int i=L;i<best;i++){
upd(1,1,n+1,ja[i],0,-1);
upd(1,1,n+1,ja[i],1,-a[i]);
}
}
ll findMaxAttraction(int nn,int start,int d,int y[]){
vector <pii> b;
start++;
for (int i=1;i<=nn;i++){
c[i]=y[i-1];
}
for (int i=1;i<=start;i++){
a[i]=c[i];
}
reverse(a+1,a+start+1);
for (int i=1;i<=start;i++){
b.pb({a[i],i});
}
sort(b.begin(),b.end());
for (int i=1;i<=b.size();i++){
ja[b[i-1].S]=i;
}
n=start;
solve(1,d,1,start,0);
// cout << " eih3 4w" << endl;
memset(seg,0,sizeof seg);
devide(1,d,1,start,1);
memset(seg,0,sizeof seg);
b.clear();
for (int i=start+1;i<=nn;i++){
a[i-start]=c[i];
}
n=nn-start;
for (int i=1;i<=n;i++){
b.pb({a[i],i});
}
sort(b.begin(),b.end());
for (int i=0;i<b.size();i++){
ja[b[i].S]=i+1;
}
// cout << 1 << " " << d << " " << 1 << " " << nn << " " << start << endl;
// return 0;
if (n>0){
solve(1,d,1,n,2);
memset(seg,0,sizeof seg);
devide(1,d,1,n,3);
}
ll ans=(dp[0][d]);
// cout << ans << endl;
for (int i=0;i<=d-2;i++){
ans=max(ans,dp[0][i]+dp[3][d-i-2]);
// cout << dp[0][i]+dp[3][d-i-2] << endl;
}
for (int i=0;i<=d-1;i++){
ans=max(ans,dp[1][i]+dp[2][d-i-1]);
// cout << i << " " << dp[1][i] << " " << dp[2][d-i-1] << endl;
}
return ans;
}
int cc[12];
int32_t main(){
for (int i=0;i<12;i++) cin >> cc[i];
cout << findMaxAttraction(12,4,9,cc) << endl;
}
/*
5
10 2 20 30 1
3 7
*/
///443000133 429885113 57256993 867868565 49902574 245497810 795048239 746594416 782837708 578814954 59738156 922971954