oj.uz

답안 #779206

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
779206 2023-07-11T08:57:23 Z PoonYaPat 휴가 (IOI14_holiday) C++14
100 / 100
 1785 ms 18304 KB 
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;

int n,st,d,p[100001];
ll dpL[250005][3],dpR[250005][3],val[100001];
bool visL[250005][3],visR[250005][3];
vector<pii> v;

struct Node {
    ll sum;
    int cnt;
} s[1<<18];

Node merge(Node a, Node b) {return {a.sum+b.sum,a.cnt+b.cnt};}

void update(int l, int r, int idx, int x, int val) {
    if (x>r || x<l) return;
    if (l==r) {
        if (val!=-1) s[idx]={val,1};
        else s[idx]={0,0};
    } else {
        int mid=(l+r)/2;
        update(l,mid,2*idx,x,val);
        update(mid+1,r,2*idx+1,x,val);
        s[idx]=merge(s[2*idx],s[2*idx+1]);
    }
}

ll query(int l, int r, int idx, int want) {
    if (want==0) return 0;
    if (l==r) return s[idx].sum;
    int mid=(l+r)/2;
    if (s[2*idx].cnt<=want) return s[2*idx].sum+query(mid+1,r,2*idx+1,want-s[2*idx].cnt);
    else return query(l,mid,2*idx,want);
}

struct NN {
    int ld,rd,l,r,w;
};

int now;

void fL(int Ld, int Rd, int L, int R, int W) {
    now=st;
    for (int i=0; i<n; ++i) update(0,n-1,1,i,-1);

    queue<NN> q;
    q.push({Ld,Rd,L,R,W});

    while (!q.empty()) {
        int ld=q.front().ld, rd=q.front().rd, l=q.front().l, r=q.front().r, w=q.front().w;
        q.pop();

        int day=(ld+rd)/2;

        //consider in range l to r
        if (now<r) {
            for (int i=0; i<n; ++i) update(0,n-1,1,i,-1);
            for (int i=st-1; i>r; --i) update(0,n-1,1,p[i],val[i]);
        }

        int best=st;
        for (int i=r; i>=l; --i) {
            int tour=day-(st-i)*w;
            if (i!=st) update(0,n-1,1,p[i],val[i]);
            if (tour<=0) continue;

            ll h=query(0,n-1,1,tour);
            if (h>dpL[day][w]) {
                dpL[day][w]=h;
                best=i;
            }
        }

        if (ld<=rd) {
            q.push({ld,day-1,best,r,w});
            q.push({day+1,rd,l,best,w});
        }
        now=l;
    }
}

void fR(int Ld, int Rd, int L, int R, int W) {
    now=st;
    for (int i=0; i<n; ++i) update(0,n-1,1,i,-1);

    queue<NN> q;
    q.push({Ld,Rd,L,R,W});

    while (!q.empty()) {
        int ld=q.front().ld, rd=q.front().rd, l=q.front().l, r=q.front().r, w=q.front().w;
        q.pop();

        int day=(ld+rd)/2;

        //consider in range l to r
        if (now>l){
            for (int i=0; i<n; ++i) update(0,n-1,1,i,-1);
            for (int i=st+1; i<l; ++i) update(0,n-1,1,p[i],val[i]);
        }

        int best=st;
        for (int i=l; i<=r; ++i) {
            int tour=day-(i-st)*w;
            if (i!=st) update(0,n-1,1,p[i],val[i]);
            if (tour<=0) continue;

            ll h=query(0,n-1,1,tour);
            if (h>dpR[day][w]) {
                dpR[day][w]=h;
                best=i;
            }
        }

        if (ld<=rd) {
            q.push({ld,day-1,l,best,w});
            q.push({day+1,rd,best,r,w});
        }
        now=r;
    }
}

ll findMaxAttraction(int N, int start, int D, int att[]) {
    n=N; st=start; d=D;
    for (int i=0; i<n; ++i) val[i]=att[i], v.push_back(pii(att[i],i));
    sort(v.begin(),v.end(),greater<pii>());
    for (int i=0; i<n; ++i) p[v[i].second]=i;

    fR(0,d,st+1,n-1,1);
    fR(0,d,st+1,n-1,2);
    fL(0,d,0,st-1,1);
    fL(0,d,0,st-1,2);

    ll ans=0;
    for (int i=0; i<=d; ++i) { //go right for i days

        //go right first
        ans=max(ans,dpR[i][2]+dpL[d-i][1]);
        if (i!=d) ans=max(ans,dpR[i][2]+dpL[d-i-1][1]+val[st]);

        //go left first
        ans=max(ans,dpL[d-i][2]+dpR[i][1]);
        if (i!=d) ans=max(ans,dpL[d-i-1][2]+dpR[i][1]+val[st]);
        
    }

    return ans;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 0 ms 724 KB Output is correct
5 Correct 0 ms 724 KB Output is correct
6 Correct 0 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1373 ms 15056 KB Output is correct
2 Correct 1249 ms 10392 KB Output is correct
3 Correct 1361 ms 15080 KB Output is correct
4 Correct 1219 ms 10496 KB Output is correct
5 Correct 1283 ms 13004 KB Output is correct
6 Correct 479 ms 9676 KB Output is correct
7 Correct 693 ms 7784 KB Output is correct
8 Correct 889 ms 8088 KB Output is correct
9 Correct 416 ms 12344 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 1236 KB Output is correct
2 Correct 25 ms 1260 KB Output is correct
3 Correct 25 ms 1264 KB Output is correct
4 Correct 30 ms 1100 KB Output is correct
5 Correct 27 ms 1092 KB Output is correct
6 Correct 8 ms 852 KB Output is correct
7 Correct 7 ms 724 KB Output is correct
8 Correct 7 ms 724 KB Output is correct
9 Correct 7 ms 828 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1464 ms 18300 KB Output is correct
2 Correct 1443 ms 18304 KB Output is correct
3 Correct 600 ms 4628 KB Output is correct
4 Correct 24 ms 1020 KB Output is correct
5 Correct 8 ms 824 KB Output is correct
6 Correct 7 ms 724 KB Output is correct
7 Correct 7 ms 804 KB Output is correct
8 Correct 1706 ms 10580 KB Output is correct
9 Correct 1785 ms 10588 KB Output is correct