oj.uz

답안 #582345

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
582345 2022-06-23T16:41:31 Z jasmin 휴가 (IOI14_holiday) C++14
47 / 100
 5000 ms 10156 KB 
#include<bits/stdc++.h>
#include<holiday.h>
using namespace std;
#define int long long

struct segtree{
    vector<pair<int,int> > tree;

    segtree(int n){
        tree.resize(n*4);
    }

    pair<int,int> merge(pair<int,int> a, pair<int,int> b){
        return {a.first+b.first, a.second+b.second};
    }

    pair<int,int> update(int l, int r, int v, int x, int val, bool add){
        if(x<l || r<=x) return tree[v];
        if(l+1==r){
            return tree[v]={add, val};
        }
        int m=l+(r-l)/2;
        return tree[v]=merge(update(l, m, v*2+1, x, val, add), update(m, r, v*2+2, x, val, add));
    }
    pair<int,int> query(int l, int r, int v, int ql, int qr){
        if(qr<=l || r<=ql) return {0, 0};
        if(ql<=l && r<=qr) return tree[v];
        int m=l+(r-l)/2;
        return merge(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
    }
};

int bestk(int d, segtree& seg, int n){
    if(d<=0) return 0;

    int l=0; int r=n;
    int ans=0;
    while(l<=r){
        int m=l+(r-l)/2;
        auto val=seg.query(0, n, 0, 0, m);
        if(val.first<=d){
            ans=val.second;
            l=m+1;
        }
        else{
            r=m-1;
        }
    }
    return ans;
}

long long findMaxAttraction(int32_t n, int32_t start, int32_t d, int32_t attraction[]) {
    vector<int> ind(n);
    vector<pair<int,int> > sorted(n);
    for(int i=0; i<n; i++){
        sorted[i]={attraction[i], i};
    }
    sort(sorted.begin(), sorted.end());
    reverse(sorted.begin(), sorted.end());
    for(int i=0; i<n; i++){
        ind[sorted[i].second]=i;
    }

    int ans=0;
    segtree seg(n);
    for(int l=start; l>=0; l--){
        seg.update(0, n, 0, ind[l], attraction[l], true);
        for(int r=start; r<n; r++){
            if(r!=start){
                seg.update(0, n, 0, ind[r], attraction[r], true);
            }

            int days=d-(r-l+min(r-start, start-l));
            if(0<days){
                ans=max(ans, bestk(days, seg, n));
            }
        }
        for(int r=start+1; r<n; r++){
            seg.update(0, n, 0, ind[r], 0, false);
        }
    }
    return ans;
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int32_t n, start, d;
    cin >> n >> start >> d;
    int32_t a[n];
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    cout << findMaxAttraction(n, start, d, a) << "\n";
}*/

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 9292 KB Output is correct
2 Correct 139 ms 9300 KB Output is correct
3 Correct 133 ms 9292 KB Output is correct
4 Correct 137 ms 9292 KB Output is correct
5 Correct 152 ms 8564 KB Output is correct
6 Correct 39 ms 3116 KB Output is correct
7 Correct 72 ms 5076 KB Output is correct
8 Correct 88 ms 6004 KB Output is correct
9 Correct 27 ms 2388 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 1087 ms 852 KB Output is correct
5 Correct 768 ms 852 KB Output is correct
6 Correct 15 ms 736 KB Output is correct
7 Correct 69 ms 748 KB Output is correct
8 Correct 76 ms 752 KB Output is correct
9 Correct 74 ms 752 KB Output is correct

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 9300 KB Output is correct
2 Correct 132 ms 10156 KB Output is correct
3 Execution timed out 5043 ms 4948 KB Time limit exceeded
4 Halted 0 ms 0 KB -