#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
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++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
229 ms |
596 KB |
Output is correct |
| 2 |
Correct |
238 ms |
672 KB |
Output is correct |
| 3 |
Correct |
248 ms |
664 KB |
Output is correct |
| 4 |
Correct |
230 ms |
672 KB |
Output is correct |
| 5 |
Correct |
2 ms |
596 KB |
Output is correct |
| 6 |
Correct |
4 ms |
596 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
8276 KB |
Output is correct |
| 2 |
Correct |
30 ms |
8268 KB |
Output is correct |
| 3 |
Correct |
29 ms |
8276 KB |
Output is correct |
| 4 |
Correct |
37 ms |
8268 KB |
Output is correct |
| 5 |
Correct |
41 ms |
7756 KB |
Output is correct |
| 6 |
Correct |
12 ms |
2748 KB |
Output is correct |
| 7 |
Correct |
22 ms |
4632 KB |
Output is correct |
| 8 |
Correct |
29 ms |
5440 KB |
Output is correct |
| 9 |
Correct |
8 ms |
2132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1107 ms |
980 KB |
Output is correct |
| 2 |
Correct |
604 ms |
956 KB |
Output is correct |
| 3 |
Correct |
514 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1454 ms |
936 KB |
Output is correct |
| 5 |
Correct |
1094 ms |
948 KB |
Output is correct |
| 6 |
Correct |
110 ms |
724 KB |
Output is correct |
| 7 |
Correct |
176 ms |
752 KB |
Output is correct |
| 8 |
Correct |
165 ms |
752 KB |
Output is correct |
| 9 |
Correct |
161 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
