Submission #696107

#	Time	Username	Problem	Language	Result	Execution time	Memory
696107		yogesh_sane	Holiday (IOI14_holiday)	C++17	47 / 100	1454 ms	8276 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 solve(vector<city> &cities, int d){
    sort(cities.begin(), cities.end(),sort_by_attractions);
    for(int i = 0; i < cities.size(); 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 < cities.size(); r++){
        int max_visits = d-r;                                   
        st.visit(1,0,cities.size()-1,cities[r].sorted_idx);
        ans = max(ans,st.query(1,max_visits));
    }
    return ans;
}
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];
    }
    return solve(cities,d);
}
long long subtask3(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];
    }
    long long ans = 0;
    for(int i = 0; i <= start; i++){
        vector<city> cts(cities.begin()+i,cities.end());
        ans = max(ans,solve(cts,d-(start-i)));
    }
    for(int i = start; i < n; i++){
        vector<city> cts(cities.rbegin()+(n-i-1),cities.rend());
        for(int j = 0; j < cts.size(); j++)
            cts[j].idx = j;
        ans = max(ans,solve(cts,d-(i-start)));
    }
    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);
    }else if( n <= 3000)
        return subtask3(n,start,d,attraction);
    return 0;
}
 

Compilation message (stderr)

holiday.cpp: In function 'long long int solve(std::vector<city>&, int)':
holiday.cpp:109:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<city>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int i = 0; i < cities.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~
holiday.cpp:114:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<city>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(int r = 0; r < cities.size(); r++){
      |                    ~~^~~~~~~~~~~~~~~
holiday.cpp: In function 'long long int subtask3(int, int, int, int*)':
holiday.cpp:142:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<city>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |         for(int j = 0; j < cts.size(); j++)
      |                        ~~^~~~~~~~~~~~

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