# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
582289 |
2022-06-23T15:38:30 Z |
Josia |
Holiday (IOI14_holiday) |
C++14 |
|
4869 ms |
1236 KB |
#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;
long long int findFromZero(int n, int start, int d, int attraction[], int walkingFactor) {
assert(start == 0);
map<int, int> bestAttractions;
long long int res = 0;
long long int sum = 0;
int inUse = 0;
for (int i = 0; i<min(d, n); i++) {
sum += attraction[i]; bestAttractions[attraction[i]]++; inUse++;
while (i*walkingFactor + inUse > d) {
if (bestAttractions.empty()) return res;
sum -= (*bestAttractions.begin()).first; bestAttractions[(*bestAttractions.begin()).first]--; inUse--;
if (bestAttractions[(*bestAttractions.begin()).first] == 0) bestAttractions.erase((*bestAttractions.begin()).first);
}
// cerr << i << " " << inUse << "\n";
res = max(sum, res);
}
return res;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
if (n > 3000) {
return findFromZero(n, start, d, attraction, 1);
}
vector<int> left;
vector<int> right;
for (int i = 0; i<n; i++) {
if (i<=start) left.push_back(attraction[i]);
if (i>start) right.push_back(attraction[i]);
}
reverse(left.begin(), left.end());
int attL[left.size()];
int attR[right.size()];
for (int i = 0; i<left.size(); i++) attL[i] = left[i];
for (int i = 0; i<right.size(); i++) attR[i] = right[i];
long long int res = 0;
for (int i = 0; i<=d; i++) {
long long int tmp = 0;
tmp += findFromZero(left.size(), 0, i, attL, 1);
tmp += findFromZero(right.size(), 0, d-i-2, attR, 2);
res = max(res, tmp);
tmp = 0;
tmp += findFromZero(left.size(), 0, i, attL, 2);
tmp += findFromZero(right.size(), 0, d-i-1, attR, 1);
res = max(res, tmp);
}
return res;
}
Compilation message
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i = 0; i<left.size(); i++) attL[i] = left[i];
| ~^~~~~~~~~~~~
holiday.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for (int i = 0; i<right.size(); i++) attR[i] = right[i];
| ~^~~~~~~~~~~~~
# |
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 |
692 KB |
Output is correct |
5 |
Correct |
1 ms |
608 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 |
8 ms |
684 KB |
Output is correct |
2 |
Correct |
7 ms |
596 KB |
Output is correct |
3 |
Correct |
8 ms |
596 KB |
Output is correct |
4 |
Correct |
9 ms |
688 KB |
Output is correct |
5 |
Correct |
11 ms |
684 KB |
Output is correct |
6 |
Correct |
3 ms |
596 KB |
Output is correct |
7 |
Correct |
6 ms |
596 KB |
Output is correct |
8 |
Correct |
8 ms |
596 KB |
Output is correct |
9 |
Correct |
3 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4869 ms |
1064 KB |
Output is correct |
2 |
Correct |
191 ms |
740 KB |
Output is correct |
3 |
Correct |
3135 ms |
996 KB |
Output is correct |
4 |
Correct |
1839 ms |
844 KB |
Output is correct |
5 |
Correct |
1602 ms |
1024 KB |
Output is correct |
6 |
Correct |
88 ms |
704 KB |
Output is correct |
7 |
Correct |
39 ms |
596 KB |
Output is correct |
8 |
Correct |
43 ms |
596 KB |
Output is correct |
9 |
Correct |
28 ms |
700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
11 ms |
1236 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |