Submission #694974

#	Time	Username	Problem	Language	Result	Execution time	Memory
694974		yogesh_sane	Holiday (IOI14_holiday)	C++17	30 / 100	246 ms	6596 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()*2);
        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;
            tree[v].visited = 1;
        }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].attractions = combine_attractions(tree[lc].attractions,tree[rc].attractions);
        tree[v].visited = combine_visited(tree[lc].visited,tree[rc].visited);
    }
    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 unvisit(int v, int tl, int tr, int pos){
        if(tl==tr){
            tree[v].visited = 0;
            tree[v].attractions = 0;
        }else{
            int tm = (tl+tr)>>1;
            if(pos <= tm)
                unvisit(lc,tl,tm,pos);
            else
                unvisit(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[]){
    int p = ceil(log2(n));
    vector<city> cities(1<<p);
    for(int i = 0; i < 1<<p; i++){
        cities[i].idx = i;
        if(i < n)
            cities[i].attractions = arrraction[i];
    }
    sort(cities.begin(), cities.end(),sort_by_attractions);
    for(int i = 0; i < 1<<p; i++)
        cities[i].sorted_idx = i;
    stree st = stree(cities);
    for(int i = 0; i < (1<<p); i++){
        if(cities[i].idx >= min(d-1,n))
            st.unvisit(1,0,(1<<p)-1,i);
    }
    sort(cities.begin(), cities.end(), sort_by_idx);
    long long ans = 0;
    for(int r = min(d,n)-1; r >=0 ; r--){
        int max_visits = min(r+1,d-r);
        ans = max(ans,st.query(1,max_visits));
        st.unvisit(1,0,(1<<p)-1,cities[r].sorted_idx);
    }
    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