제출 #695345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
695345		yogesh_sane	휴가 (IOI14_holiday)	C++17	30 / 100	264 ms	8316 KiB

holiday

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int const MAXN = 1e5;

long long subtask1(int n, int start, int d, int arrraction[]){
    long long ans = 0;
    for(int mask = 1; mask < (1<<n); mask++){
        vector<int> cities;
        for(int bit = 0; bit < n; bit++){
            if(mask&(1<<bit)){
                cities.push_back(bit);
            }
        }
        int curr_city = start;
        int tour_days = 0;
        long long ans_curr = 0;
        for(auto city : cities){
            tour_days += abs(curr_city-city)+1;
            ans_curr += arrraction[city];
            curr_city = city;
        }
        if(tour_days <= d)
            ans = max(ans, ans_curr);
        reverse(cities.begin(), cities.end());
        curr_city = start;
        tour_days = 0;
        ans_curr = 0;
        for(auto city : cities){
            tour_days += abs(curr_city-city)+1;
            ans_curr += arrraction[city];
            curr_city = city;
        }
        if(tour_days <= d)
            ans = max(ans, ans_curr);
    }
    return ans;
}
struct city{
    int attractions;
    int idx;
    int sorted_idx;
};
struct stree_node{
    int visited;
    long long attractions;
};
#define lc v<<1
#define rc (v<<1)+1
struct stree{
    vector<stree_node>tree;
    stree(vector<city> &cities){
        tree = vector<stree_node>(cities.size()*4);
        build(1,0,cities.size()-1,cities);
    }
    void build(int v, int tl, int tr, vector<city> &cities){
        if(tl == tr){
            tree[v].attractions = cities[tl].attractions;
        }else{
            int tm = (tl+tr)>>1;
            build(lc,tl,tm,cities);
            build(rc,tm+1,tr,cities);
            pushup(v);
        }
    }
    void pushup(int v){
        tree[v].visited = combine_visited(tree[lc].visited,tree[rc].visited);
        tree[v].attractions = combine_attractions(tree[lc].visited ? tree[lc].attractions : 0,
                                                  tree[rc].visited ? tree[rc].attractions : 0);
    }
    long long combine_attractions(long long left_val, long long right_val){
        return left_val+right_val;
    }
    int combine_visited(int left_val, int right_val){
        return left_val+right_val;
    }
    void visit(int v, int tl, int tr, int pos){
        if(tl==tr){
            tree[v].visited = 1;
        }else{
            int tm = (tl+tr)>>1;
            if(pos <= tm)
                visit(lc,tl,tm,pos);
            else
                visit(rc,tm+1,tr,pos);
            pushup(v);
        }
    }
    long long query(int v, int visits){
        if(visits <= 0)
            return 0;
        if(tree[v].visited <= visits)
            return tree[v].attractions;
        else{
            return query(lc,visits) + query(rc,visits-tree[lc].visited);
        }
    }
};
bool sort_by_idx(city const &a, city const &b){
    return a.idx < b.idx;
}
bool sort_by_attractions(city const &a, city const &b){
    return a.attractions > b.attractions;
}
long long subtask2(int n, int start, int d, int arrraction[]){
    vector<city> cities(n);
    for(int i = 0; i < n; i++){
        cities[i].idx = i;
        cities[i].attractions = arrraction[i];
    }
    sort(cities.begin(), cities.end(),sort_by_attractions);
    for(int i = 0; i < n; i++)
        cities[i].sorted_idx = i;
    stree st = stree(cities);
    sort(cities.begin(), cities.end(), sort_by_idx);
    long long ans = 0;
    for(int r = 0; r < n; r++){
        int max_visits = d-r;                                   //min(r+1,d-r);
        st.visit(1,0,n-1,cities[r].sorted_idx);
        ans = max(ans,st.query(1,max_visits));
    }
    return ans;
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    if(n <= 20){
        return subtask1(n,start,d,attraction);
    }else if(start == 0){
        return subtask2(n,start,d,attraction);
    }
    return 0;
}
 

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53