2109

처음에 문제 이해못해가지고 왜 이런걸 틀리지 싶었는데 내가 틀렸다 ㅡㅡ

QnA에서 문제를 제대로 이해하고 다시 풀어서 맞았다.

이 문제의 핵심은 d 기간 내에는 어떤 날짜에 강연을 해도 상관 없다는거다

그래서 3 1 1 10 2 10 2 라는 인풋이 들어오면

정답으로 20을 출력해야한다.

어떤 강연을 할 지 말지 결정하는 과정은 다음과 같다.

기간내에 강연 할 수 있는 빈 시간이 있다면

강연을 하고

이미 강연이 다 차있다면 차있는 강연들 중에서 가장 돈을 조금 주는 강연과 비교 한 다음

하려고 하는 강연이 더 돈을 많이 주면 가장 돈을 조금 주는 강연과 바꾸면 된다.

생각 과정은 그리 어렵지 않은데 자료 구조를 어떤걸 쓸 것인지가 고민이었다.

최대 10000개의 강연이 있기 때문에 생각하기 쉬운 자료구조(n*n)을 사용하면 

시간초과가 뜬다.

1. 그래서 나는 먼저 강연들을 기간으로 오름차순 정렬한 다음

2. 그 기간내에 강연이 몇개 있는 지는 BIT를 이용해서 구했고(사실 이거는 안해도 되는디)

3. 그 기간내의 강연 중 돈을 가장 조금 주는 강연은 priority queue를 통해서 구현했다.

오름차순으로 정렬했기 때문에 기본적으로 dp로 차근차근 증가시켜 나가면 된다.

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

const int SUM_MAX = 100000001;

int size_tree[11111];

struct Node{

int d, p;

};

bool compare(Node a, Node b)

{

return a.d < b.d;

}

int read(int idx)

{

int sum = 0;

while(idx > 0)

{

sum += size_tree[idx];

idx -= idx&-idx;

}

return sum;

}

void update(int idx, int val)

{

while(idx <= 11111)

{

size_tree[idx] += val;

idx += idx&-idx;

}

}

Node coll[11111];

int d[11111];

int main()

{

int n, piv= 0;

scanf("%d", &n);

priority_queue<int> pq;

for(int i = 1; i <= n; i++)

{

scanf("%d %d", &coll[i].p, &coll[i].d);

}

sort(coll+1, coll+n+1, compare);

for(int i=1;i<=n;i++)

{

if(read(coll[i].d) < coll[i].d)

{

piv++;

update(piv, 1);

d[piv] += coll[i].p + d[piv-1];

pq.push(-coll[i].p);

}

else

{

if(abs(pq.top()) < coll[i].p)

{

d[piv] -= abs(pq.top());

d[piv] += coll[i].p;

pq.pop();

pq.push(-coll[i].p);

}

}

}

printf("%d\n", d[piv]);

return 0;

}