| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1042435 | lyis | 휴가 (IOI14_holiday) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <holiday.h>
//#include <ext/pb_ds/assoc_container.shpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define mp make_pair
#define ii pair <int, int>
#define li pair <long long, int>
using namespace std;
//using namespace __gnu_pbds;
//mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef unsigned long long ull;
typedef long double db;
typedef __int128 i128;
const ll mod = 1e9 + 7;
const ll MOD = 998245353;
const db esp = 1e-10;
const int dx[] = {0, 1, 0, -1, -1, 1, 1, -1};
const int dy[] = {1, 0, -1, 0, -1, -1, 1, 1};
//const int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Moves
//const int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Moves
const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int maxn = 1e5 + 10;
const int maxm = 1e6 + 10;
const int maxk = 5e5 + 10;
const int LOG = 20;
const int base = 311;
const int root = 1e9;
const int Block = 600;
template <class an, class lyis>
bool minimize(an &x, const lyis y){
if(x > y){
x = y;
return true;
} else return false;
}
template <class an, class lyis>
bool maximize(an &x, const lyis y){
if(x < y){
x = y;
return true;
} else return false;
}
#define int ll
int n, s, d;
int a[maxn];
int res;
bool del[maxn];
int solve() {
int ans = 0, cur = 0;
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> q;
for (int i = s; i <= n; i++) {
q.push({a[i], -i}), cur += a[i];
while (q.size() > 0 && i - s + q.size() > d) {
cur -= q.top().first;
q.pop();
}
ans = max(cur, ans);
}
while (q.size() > 0) q.pop();
cur = 0;
priority_queue <int> pos;
memset(del, 0, sizeof(del));
for (int i = s; i <= n; i++) {
q.push({a[i], -i}), pos.push(i), cur += a[i];
while (q.size() > 0 && i - s + q.size() > d) {
pair <int, int> x = q.top();
q.pop();
cur -= x.first;
del[-x.second] = 1;
}
if (cur == ans) break;
}
while (pos.size() > 0) {
int x = pos.top();
if (del[x]) pos.pop(), del[x] = 0;
else break;
}
for (int i = s - 1, j = d - 1; i >= 1 && j >= 1; --i, --j) {
q.push({a[i], -i}), pos.push(i), cur += a[i];
while (q.size() > 0 && pos.top() - i + q.size() > j) {
pair <int, int> x = q.top();
q.pop();
cur -= x.first;
del[-x.second] = 1;
while (pos.size() > 0) {
int x = pos.top();
if (del[x]) pos.pop(), del[x] = 0;
else break;
}
}
ans = max(cur, ans);
}
maximize(res, ans);
}
void init() {
cin >> n >> s >> d;
++s;
for (int i = 1; i <= n; i++) cin >> a[i];
}
int findMaxAttraction(int n, int s, int d, int attraction[]) {
for (int i = 1; i <= n; i++) a[i] = attraction[i - 1];
solve();
reverse(a + 1, a + n + 1);
s = n - s + 1;
solve();
return res;
}