oj.uz

답안 #30957

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
30957 2017-08-02T02:55:37 Z kajebiii 휴가 (IOI14_holiday) C++14
24 / 100
 73 ms 65536 KB 
#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;
    NODE *lp, *rp;
    NODE() : sum(0ll), cnt(0), lp(NULL), rp(NULL) {}
    NODE(int a, int b) : sum(0ll), cnt(0), lp(NULL), rp(NULL) {
        if(a == b) return;
        int m = (a+b) >> 1;
        lp = new NODE(a, m);
        rp = new NODE(m+1, b);
    }
    NODE *add(int l, int r, int v, int k, int nr[]) {
        int m = (l+r) >> 1;
        if(r < v || v < l) return this;
        NODE *res = new NODE();
        test++;
        if(l != r) {
            res->lp = lp->add(l, m, v, k, nr);
            res->rp = rp->add(m+1, r, v, k, nr);
        }
        res->cnt = cnt + k;
        res->sum = sum + nr[v] * k;
        return res;
    }
    ll getMaxSum(int l, int r, int k) {
        int m = (l+r) >> 1;
        if(k <= 0) return 0ll;
        if(l == r) return sum;
        if(rp->cnt >= k) return rp->getMaxSum(m+1, r, k);
        return lp->getMaxSum(l, m, k - rp->cnt) + rp->sum;
    }
    ~NODE() {
        if(lp != NULL) delete lp;
        if(rp != NULL) delete rp;
    }
};
NODE *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 = root[x]->getMaxSum(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] = NULL;
    root[St] = new NODE(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] = root[i-dir]->add(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;
}

Compilation message

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;
            ^

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 7936 KB Output is correct
2 Correct 0 ms 7940 KB Output is correct
3 Correct 0 ms 7932 KB Output is correct
4 Correct 0 ms 7936 KB Output is correct
5 Correct 0 ms 7940 KB Output is correct
6 Correct 0 ms 7932 KB Output is correct
7 Correct 0 ms 7936 KB Output is correct

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 69 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 10060 KB Output is correct
2 Correct 9 ms 10056 KB Output is correct
3 Correct 9 ms 10056 KB Output is correct
4 Correct 9 ms 9920 KB Output is correct
5 Correct 9 ms 9664 KB Output is correct
6 Correct 0 ms 8592 KB Output is correct
7 Correct 0 ms 8592 KB Output is correct
8 Correct 0 ms 8596 KB Output is correct
9 Correct 3 ms 8592 KB Output is correct

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 73 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -