취미로PS하는사람

https://www.acmicpc.net/problem/17694 JOI spring camp 16/17 문제. 예전에 친구와 R&E 가서 얘기했던 문제다. 최근에 다시 잡고 생각을 하다가 어느 정도 풀만해 보이는 수열 문제로 바꿨는데, 그 이후 진전이 없다가 오늘 그림판에 열심히 그리면서 풀이를 찾아 풀었다. 뭔가 그리디적인 풀이가 있는 것으로 보이나 나는 $dp$ 경로를 최적화하는 방식으로 생각했다. 문제 $N$명의 사람이 각각 $T$초동안 타는 불꽃을 들고 서 있고, $K$번째 사람의 불꽃만이 시간 $0$에 타기 시작한다. 한 사람이 불꽃을 두 번 이상 태울 수는 없다. 0초에 $i$번째 사람은 $X_i$에 서 있고, $X_i \leq X_{i+1}, X_1=0$을 만족한다. 두 사람이 같은 좌표..

https://oj.uz/problems/source/377 1. Two Antennas (두 안테나) 극한의 스위핑 문제... 우선 쿼리에 변화가 없으므로 오프라인으로 쿼리를 처리해야겠다는 생각을 할 수 있다. R이 증가하는 순서대로 쿼리를 정렬하자. 통신을 할 수 있는 조건은 1 P[i]; sumA[i] = sumA[i-1] + A[i]; } for(int i = 1; i > B[i] >> T[i] >> Q[i]; sumB[i] = sumB[i-1] + B[i]; ans += Q[i]; } for(int i = 1; i = 0) po.eb(i, temp, P[i]); } for(int i = 1; i b.y; return a.x < b.x; }); ll rem = 0; for(int i = 0; i ..

https://oj.uz/problems/source/376 중간에 논 시간을 제외하고 대략 5~6시간 정도 풀었다. 총 229점. 1. Examination(시험) 우선 학생들을 두 시험의 합이 큰 순서대로 정렬하자. 그리고 쿼리 또한 C가 큰 순서대로 정렬하면 쿼리를 처리할 때 두 시험의 합이 C 이상인 학생만 고려하면 되기 때문에 스위핑으로 이 조건을 해결할 수 있다. 나머지 A와 B 조건은 평면에서 x>=A이고 y>=B인 구간에서 점의 개수를 세는 것이기 때문에 2D BIT 등을 활용하여 점의 개수를 세줄 수 있다. 2D BIT를 처음으로 짜 봐서 이상하게 짠 것 같은데, 괜찮은 구현을 찾지 못하겠다... 코드 더보기 #include #define fi first #define se second ..