이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;
const int MAX_N = 1e5 + 100, MAX_D = MAX_N * 2.6;
ll test = 0;
struct NODE{
ll sum; int cnt;
int lp, rp;
NODE() : sum(0ll), cnt(0), lp(-1), rp(-1) {}
NODE(ll s, int c, int l, int r) : sum(s), cnt(c), lp(l), rp(r) {}
};
NODE nd[MAX_N * 22]; int all;
int init(int a, int b) {
ll sum = 0ll; int cnt = 0, lp = -1, rp = -1;
if(a != b) {
int m = (a+b) >> 1;
lp = init(a, m);
rp = init(m+1, b);
}
nd[++all] = NODE(sum, cnt, lp, rp);
return all;
}
int add(int now, int l, int r, int v, int k, int nr[]) {
int m = (l+r) >> 1;
if(r < v || v < l) return now;
int lp = -1, rp = -1;
test++;
if(l != r) {
lp = add(nd[now].lp, l, m, v, k, nr);
rp = add(nd[now].rp, m+1, r, v, k, nr);
}
int cnt = nd[now].cnt + k;
ll sum = nd[now].sum + nr[v] * k;
nd[++all] = NODE(sum, cnt, lp, rp);
return all;
}
ll getMaxSum(int now, int l, int r, int k) {
int lp = nd[now].lp, rp = nd[now].rp; ll sum = nd[now].sum;
int m = (l+r) >> 1;
if(k <= 0) return 0ll;
if(l == r) return sum;
if(nd[rp].cnt >= k) return getMaxSum(rp, m+1, r, k);
return getMaxSum(lp, l, m, k - nd[rp].cnt) + nd[rp].sum;
}
int root[MAX_N];
int N, St, D, sortIx[MAX_N], sortV[MAX_N];
ll Dy[2][MAX_D];
void calc(int dir, int wei, int s, int e, int p, int q, ll dy[]) {
if(s > e) return;
// printf("%d %d %d %d\n", s, e, p, q);
int m = (s+e) >> 1, k = -1;
dy[m] = -LINF;
for(int l=p, x=St+l*dir; l<=q && x>=0 && x<N; l++, x+=dir) {
int rest = m - l*wei;
if(rest < 0) continue;
ll val = getMaxSum(root[x], 0, N-1, rest);
// printf("in %d -> getMaxSum(%d) = %lld\n", x, rest, val);
if(dy[m] < val) dy[m] = val, k = l;
}
calc(dir, wei, s, m-1, p, k, dy);
calc(dir, wei, m+1, e, k, q, dy);
}
ll findMaxAttraction(int n_, int st_, int d_, int att_[]) {
N = n_; St = st_; D = d_;
vector<pi> v_ix;
for(int i=0; i<N; i++) v_ix.push_back(pi(att_[i], i));
sort(ALL(v_ix));
for(int i=0; i<N; i++) {
sortV[i] = v_ix[i].one;
sortIx[v_ix[i].two] = i;
}
for(int i=0; i<N; i++) root[i] = -1;
root[St] = init(0, N-1);
for(int d=0; d<2; d++) {
int dir = d*2 - 1;
for(int i=St+dir; i>=0 && i<N; i+=dir)
root[i] = add(root[i-dir], 0, N-1, sortIx[i], 1, sortV);
}
ll ans = -LINF;
calc(-1, 1, 0, D, 0, N, Dy[0]);
calc(+1, 2, 0, D, 0, N, Dy[1]);
for(int d=0; d<=D; d++) {
ans = max(ans, Dy[0][d] + Dy[1][D-d]);
if(d) {
ans = max(ans, att_[St] + Dy[0][d-1] + Dy[1][D-d]);
}
}
calc(+1, 1, 0, D, 0, N, Dy[0]);
calc(-1, 2, 0, D, 0, N, Dy[1]);
for(int d=0; d<=D; d++) {
ans = max(ans, Dy[0][d] + Dy[1][D-d]);
if(d) {
ans = max(ans, att_[St] + Dy[0][d-1] + Dy[1][D-d]);
}
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
int i, n_s;
^
# | 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... |