# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
582345 |
2022-06-23T16:41:31 Z |
jasmin |
Holiday (IOI14_holiday) |
C++14 |
|
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";
}*/
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
- |