oj.uz

답안 #171822

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171822 2019-12-30T12:55:58 Z gs18103 휴가 (IOI14_holiday) C++14
100 / 100
 304 ms 45184 KB 
#include"holiday.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 101010;
const int INF = INT_MAX >> 1;
const ll LINF = LLONG_MAX >> 1;
const ll mod = 1e9+9;

// ans[i] : i번째 도시를 마지막으로 할 때 최대 방문 개수

struct Node {
    int l = 0, r = 0, c = 0; ll val = 0;
};
Node tree[120*MAX];
vector <ll> num;
int st, d, root[MAX], sz, n;
ll ans;

void expand_tree(int s, int e, int k, int pnd, int cnd) {
    tree[cnd].c = tree[pnd].c + 1;
    tree[cnd].val = tree[pnd].val + num[k];
    if(s == e) return;
    int m = s + e >> 1;
    sz++;
    if(k <= m) {
        tree[cnd].r = tree[pnd].r;
        tree[cnd].l = sz;
        expand_tree(s, m, k, tree[pnd].l, tree[cnd].l);
    }
    else {
        tree[cnd].l = tree[pnd].l;
        tree[cnd].r = sz;
        expand_tree(m+1, e, k, tree[pnd].r, tree[cnd].r);
    }
}

ll cal(int s, int e, int cnt, int pnd, int cnd) {
    if(s == e) return cnt * num[s];
    int m = s + e >> 1, rcnt = tree[tree[cnd].r].c - tree[tree[pnd].r].c;
    ll ret;
    if(rcnt >= cnt) ret = cal(m+1, e, cnt, tree[pnd].r, tree[cnd].r);
    else {
        ll rval = tree[tree[cnd].r].val - tree[tree[pnd].r].val;
        ret = cal(s, m, cnt - rcnt, tree[pnd].l, tree[cnd].l) + rval;
    }
    return ret;
}

void dnc1(int s, int e, int l, int r) {
    if(s > e) return;
    int m = (s + e) >> 1;
    ll tans = -1, temp;
    int idx = l, cnt;
    for(int i = l; i <= r; i++) {
        cnt = d - i + m - min(st - m, i - st);
        cnt = min(cnt, i - m + 1);
        if(cnt < 0) continue;
        temp = cal(0, n-1, cnt, root[m-1], root[i]);
        if(temp > tans) {
            idx = i;
            tans = temp;
        }
    }
    ans = max(ans, tans);
    dnc1(s, m-1, l, idx), dnc1(m+1, e, idx, r);
}

ll findMaxAttraction(int N, int start, int day, int arr[]) {
    st = start + 1, d = day, n = N;
    if(d == 0) return 0;
    for(int i = 0; i < n; i++) {
        num.eb(arr[i]);
    }
    sort(all(num));
    for(int i = 0; i < n; i++) {
        sz++;
        root[i+1] = sz;
        int k = lower_bound(all(num), arr[i]) - num.begin();
        expand_tree(0, n-1, k, root[i], root[i+1]);
    }
    dnc1(1, st, st, n);
    cout << endl;
    return ans;
}

Compilation message

holiday.cpp: In function 'void expand_tree(int, int, int, int, int)':
holiday.cpp:33:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = s + e >> 1;
             ~~^~~
holiday.cpp: In function 'll cal(int, int, int, int, int)':
holiday.cpp:49:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = s + e >> 1, rcnt = tree[tree[cnd].r].c - tree[tree[pnd].r].c;
             ~~^~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 44540 KB Output is correct
2 Correct 62 ms 44524 KB Output is correct
3 Correct 62 ms 44396 KB Output is correct
4 Correct 63 ms 44500 KB Output is correct
5 Correct 82 ms 39880 KB Output is correct
6 Correct 23 ms 11384 KB Output is correct
7 Correct 44 ms 21488 KB Output is correct
8 Correct 53 ms 26144 KB Output is correct
9 Correct 17 ms 8052 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1400 KB Output is correct
2 Correct 4 ms 1400 KB Output is correct
3 Correct 4 ms 1400 KB Output is correct
4 Correct 6 ms 1400 KB Output is correct
5 Correct 4 ms 1144 KB Output is correct
6 Correct 3 ms 636 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 3 ms 632 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 45184 KB Output is correct
2 Correct 84 ms 44392 KB Output is correct
3 Correct 74 ms 19056 KB Output is correct
4 Correct 5 ms 1272 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 304 ms 44448 KB Output is correct
9 Correct 280 ms 44392 KB Output is correct