이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include"holiday.h"
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
#include <utility>
#include <set>
#include <queue>
using namespace std;
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
if (d == 0){
return 0;
}
// if (start == 0){
//
// long long best = attraction[0];
//
// multiset<pair<long long, long long> > best_cities;
// best_cities.insert(attraction[0], 0);
// long long current_sum = attraction[0];
// pair<long long, long long> last_in_sum = make_pair(attraction[0], 0);
//
// for (int r = 1; r < d; r++){
//
// long long can_visit = d - r;
//
// best_cities.insert(make_pair(attraction[r], -r));
//
// if (can_visit >= best_cities.size()){
// current_sum += attraction[r];
// last_in_sum = *(best_cities.begin());
// } else{
// if (can_visit == best_cities.size() - 1){
// current_sum += attraction[r];
// current_sum -= (best_cities.begin()) -> first;
// last_in_sum = *(++best_cities.begin());
// } else {
//
// if (attraction[r] <= last_in_sum.first){
//
// current_sum -= last_in_sum.first;
// last_in_sum = *(++best_cities.lower_bound(last_in_sum));
//
// } else{
//
// current_sum += attraction[r];
// current_sum -= last_in_sum.first;
// last_in_sum = *(++best_cities.lower_bound(last_in_sum));
// current_sum -= last_in_sum.first;
// last_in_sum = *(++best_cities.lower_bound(last_in_sum));
// }
//
// }
// }
//
// best = max(best, current_sum);
// }
//
//
// return best;
// }
long long total = 0;
for (int left = start; left >= 0 && start - left < d; left--){
int can_visit = d - (start - left);
priority_queue<long long> best;
long long best_sum = 0;
for (int i = left; i <= start; i++){
best.push(-attraction[i]);
best_sum += attraction[i];
}
while (best.size() > can_visit){
best_sum -= -best.top();
best.pop();
}
int right = start;
total = max(total, best_sum);
while (can_visit > 2 && right < n - 1){
can_visit -= 2;
right++;
best.push(-attraction[right]);
best_sum += attraction[right];
while (best.size() > can_visit){
best_sum -= -best.top();
best.pop();
}
total = max(total, best_sum);
}
}
for (int right = start; right < n && right - start < d; right++){
int can_visit = d - (right - start);
priority_queue<long long> best;
long long best_sum = 0;
for (int i = start; i <= right; i++){
best.push(-attraction[i]);
best_sum += attraction[i];
}
while (best.size() > can_visit){
best_sum -= -best.top();
best.pop();
}
int left = start;
total = max(total, best_sum);
while (can_visit > 2 && left > 0){
can_visit -= 2;
left--;
best.push(-attraction[left]);
best_sum += attraction[left];
while (best.size() > can_visit){
best_sum -= -best.top();
best.pop();
}
total = max(total, best_sum);
}
}
return total;
}
컴파일 시 표준 에러 (stderr) 메시지
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:82:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (best.size() > can_visit){
~~~~~~~~~~~~^~~~~~~~~~~
holiday.cpp:98:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (best.size() > can_visit){
~~~~~~~~~~~~^~~~~~~~~~~
holiday.cpp:121:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (best.size() > can_visit){
~~~~~~~~~~~~^~~~~~~~~~~
holiday.cpp:137:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (best.size() > can_visit){
~~~~~~~~~~~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |