제출 #854996

#제출 시각아이디문제언어결과실행 시간메모리
854996fanwen휴가 (IOI14_holiday)C++17
47 / 100
5050 ms1492 KiB
#include <bits/stdc++.h> using namespace std; #define MASK(x) (1LL << (x)) #define BIT(x, i) (((x) >> (i)) & 1) #define ALL(x) (x).begin(), (x).end() #define REP(i, n) for (int i = 0, _n = n; i < _n; ++i) #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i) #define FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i) #define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } template <class A, class B> bool minimize(A &a, B b) { if (a > b) { a = b; return true; } return false; } template <class A, class B> bool maximize(A &a, B b) { if (a < b) { a = b; return true; } return false; } const int MAXN = 1e5 + 5; const long long INF = 1e18; long long findMaxAttraction(int n, int start, int d, int A[]) { auto sub2 = [&] () -> long long { long long ans = 0, sum = 0; priority_queue <int, vector <int>, greater <int>> q; for (int i = 0; i < n; ++i) { q.push(A[i]); sum += A[i]; while((int) q.size() > max(0, d - i)) { sum -= q.top(); q.pop(); } maximize(ans, sum); } return ans; }; auto sub3 = [&]() -> long long { long long ans = 0; for (int i = start; i < n; ++i) { priority_queue <int, vector <int>, greater <int>> q; long long sum = 0; for (int j = start; j <= i; ++j) { q.push(A[j]); sum += A[j]; while((int) q.size() > max(0, d - 2 * (j - start))) { sum -= q.top(); q.pop(); } } for(int j = start - 1; j >= 0; --j) { q.push(A[j]); sum += A[j]; while((int) q.size() > max(0, d - 2 * (i - start) - (start - j))) { sum -= q.top(); q.pop(); } maximize(ans, sum); } } for (int i = start; i >= 0; --i) { priority_queue <int, vector <int>, greater <int>> q; long long sum = 0; for (int j = start; j >= i; --j) { q.push(A[j]); sum += A[j]; while((int) q.size() > max(0, d - 2 * (start - j))) { sum -= q.top(); q.pop(); } } for (int j = start + 1; j < n; ++j) { q.push(A[j]); sum += A[j]; while((int) q.size() > max(0, d - 2 * (start - i) - (j - start))) { sum -= q.top(); q.pop(); } maximize(ans, sum); } } return ans; }; if(start == 0) return sub2(); if(n <= 3000) return sub3(); } #ifdef LOCAL #include<cstdio> int main() { freopen("TASK.inp", "r", stdin); freopen("TASK.out", "w", stdout); int n, start, d; int attraction[100000]; int i, n_s; n_s = scanf("%d %d %d", &n, &start, &d); for (i = 0 ; i < n; ++i) { n_s = scanf("%d", &attraction[i]); } printf("%lld\n", findMaxAttraction(n, start, d, attraction)); return 0; } #endif // LOCAL // Dream it. Wish it. Do it.

컴파일 시 표준 에러 (stderr) 메시지

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:80:1: warning: control reaches end of non-void function [-Wreturn-type]
   80 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...