본문 바로가기
카테고리 없음

유산

Sumin Lim 2018. 3. 8. 01:42
반응형

  • 시간

    8개 테스트케이스를 합쳐서 C/C++의 경우 24초 / Java의 경우 48초 / Python의 경우 48초

        메모리

    힙, 정적 메모리 합쳐서 1024MB 이내, 스택 메모리 1MB 이내


     

    장씨 할아버지는 어마어마한 유산을 두 명의 자식에게 물려주기로 했다. 유산은 N개의 땅문서이다. 어마어마하게 넓은 땅부자였던 것이다.


    두 명의 자식, 호석이와 다혜는 땅에 대한 관점이 서로 다르다. 다혜는 땅은 넓이가 중요하다고 생각하고, 호석이는 땅은 가치가 중요하다고 생각한다.


    따라서 다혜는 물려받은 총 땅 넓이의 합이 호석이가 받은 총 땅 넓이의 합과 D 이하로 차이 나면 만족한다. 


    호석이는 받은 땅의 총 가치가 다혜가 받은 땅의 총 가치보다 높아지고 싶어 한다.


    장씨 할아버지는 두 자식이 각각 어떤 것을 원하는지 알고 있다.


    각 땅문서는 둘 중 한 명에게 주거나 기부할 수 있다.


    각 땅문서마다 차지하는 땅의 넓이와 가치가 주어져 있을 때, 다혜가 만족하는 선 안에서 (호석이의 땅문서 총 가치) – (다혜의 땅문서 총 가치)의 최대값을 구하여라.



    [입력]


    첫 번째 줄에 테스트 케이스의 수 T가 주어진다.


    각 테스트 케이스의 첫 번째 줄에는 땅문서의 개수 N(1 ≤ N ≤ 30)과 정수 D(0 ≤ D ≤ 1015)가 주어진다. 


    두 번째 줄부터 N개의 줄에 걸쳐서 각 땅의 정보가 주어진다. 


    각 땅 문서마다 넓이와 가치가 주어지는데 모두 정수이며 0 이상 1015 이하이다.


     

    [출력]


    각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,


    각 테스트 케이스마다 다혜가 만족하는 선 안에서 유산을 물려줄 때, (호석이의 땅 문서 총 가치) – (다혜의 땅 문서 총 가치)의 최대값을 구하여라.



    입력 예제

     

    2

    5 0

    1 100

    2 200

    4 400

    8 500

    16 1600

    6 15

    70 700

    30 200

    60 100

    40 100

    80 600

    50 900

    // 테스트 케이스 개수

    // 첫 번째 테스트 케이스, N = 5, D = 0

     

     

     

     

     

    // 두 번째 테스트 케이스, N = 6, D = 15

     

     

     

     

     

     


    출력 예제

     

    #1 0

    #2 1200

    // 첫 번째 테스트 케이스 결과

    // 두 번째 테스트 케이스 결과



#include <stdio.h>
#define ll long long
#define N (14348908)
struct Node{
    ll s, v;
    Node(){s=v=0;}
    Node(ll a, ll b):s(a),v(b){}
    void set(ll a, ll b){s=a;v=b;}
    bool operator < (Node& x){return this->s < x.s;}
};
int n,ed,test,sz,sz2;
ll v[30],s[30],D,A,B,C,ans;
Node f[N],g[N],dq[N];
ll max(ll a, ll b){return a>b?a:b;}
void go(int idx, Node* dest, Node* from, int sz){
    if(idx == ed)return;
    register int a=0,b=0,c=0,cnt=0;
    from[sz]=Node(1e18,1e18);
    while(c<sz){
        A=from[a].s-s[idx],B=from[b].s,C=from[c].s+s[idx];
        if(A<B){
            if(C<A)dest[cnt++]=Node(C,from[c++].v+v[idx]);
            else dest[cnt++]=Node(A,from[a++].v-v[idx]);
        }
        else{
            if(C<B)dest[cnt++]=Node(C,from[c++].v+v[idx]);
            else dest[cnt++]=from[b++];
        }
    }
    go(idx+1,from,dest,sz*3);
    return;
}
int main(){
    scanf("%d", &test);
    for(int tc=1; tc<=test; tc++){
        ans = 0;
        sz=sz2=1;
        scanf("%d %lld", &n, &D);
        for(int i=0; i<n; i++)scanf("%lld %lld", s+i, v+i);
        for(int i=0; i<n/2; i++)sz*=3;
        ed=n/2;
        dq[0] = f[0] = Node(0,0);
        if((n/2)&1)go(0,f,dq,1);
        else go(0,dq,f,1);
        for(int i=n/2; i<n; i++)sz2*=3;
        ed = n;
        dq[0] = g[0] = Node(0,0);
        if((n-(n/2))&1)go(n/2,g,dq,1);
        else go(n/2,dq,g,1);
        register int r=sz-1, hd=0, tl=0;
        for(int i=0; i<sz2; i++){
            Node A = g[i];
            while(r >= 0 && f[r].s >= -A.s - D ){
                while(hd < tl && dq[tl-1].v <= f[r].v)tl--;
                dq[tl++] = f[r--];
            }
            while(hd < tl && -A.s + D < dq[hd].s)hd++;
            if(hd != tl)ans = max(ans, A.v + dq[hd].v);
        }
        printf("#%d %lld\n", tc, ans);
    }
    return 0;
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<stdio.h>
typedef long long ll;
 
class Node
{
public:
    ll area, value;
 
    bool operator < (const Node &n) const
    {
        return area == n.area ? value < n.value : area > n.area;
    }
};
Node w[31], tmp[31];
ll ans, n, d;
ll Abs(ll a) { return a < 0 ? -a : a; }
void merge(int l, int m, int r)
{
    int s1 = l, s2=l, s3 = m+1;
 
    while (s1 <= m && s3 <= r)
    {
        if (w[s1] < w[s3]) tmp[s2++] = w[s1++];
        else tmp[s2++] = w[s3++];
    }
    while (s1 <= m)tmp[s2++] = w[s1++];
    while (s3 <= r)tmp[s2++] = w[s3++];
    for (int i = l; i <= r; i++) w[i] = tmp[i];
}
void sort(int l, int r)
{
    if (l < r)
    {
        int m = (l + r) / 2;
        sort(l, m);
        sort(m + 1, r);
        merge(l, m, r);
    }
}
void dfs(ll hoa, ll hov, ll daa, ll dav, int idx)
{
    if (idx == n)
    {
        if (Abs(hoa - daa) > d || hov < dav) return;
        ans = ans < hov - dav ? hov - dav : ans;
        return;
    }
    ll cmpv = 0, cmpa = 0;
    for (int i = idx; i < n; i++)
    {
        cmpv += w[i].value;
        cmpa += w[i].area;
    }
 
    if (hov + cmpv < dav || Abs(hoa-daa) > cmpa+d || ans > cmpv+hov-dav)
        return;
    dfs(hoa + w[idx].area, hov + w[idx].value, daa, dav, idx + 1);
    dfs(hoa, hov, daa + w[idx].area, dav + w[idx].value, idx + 1);
    dfs(hoa, hov, daa, dav, idx + 1);
}
int main()
{
    int T;
 
    scanf("%d", &T);
 
    for (int tc = 1; tc <= T; tc++)
    {
        scanf("%lld %lld", &n, &d);
        for (int i = 0; i < n; i++)
            scanf("%lld %lld", &w[i].area, &w[i].value);
 
        sort(0, n - 1);
        ans = 0;
        dfs(0, 0, 0, 0, 0);
        printf("#%d %lld\n", tc, ans);
    }
}


반응형
저작자표시 (새창열림)

티스토리툴바