#include <stdio.h>
int main(void)
{
    int myCuteCount;
    for(myCuteCount = 1;myCuteCount <= 500;myCuteCount++)
        printf("I will not forget to append '\n'.");
    return 0;
}

I'm soory, but '\n' doesn't work!

Nice try :3

In problem A, we're asked only the smallest 100 combinations in the worst case, so we can keep track of the smallest k combinations we've seen so far in an array, and whenever the array exceeds k (after sorting) we remove elements from the back.

• Initially, put all v_1, i into the ans array.
• Then process piece types one by one. To process piece type i, for all current values x from the ans array and all values v_i, j we push value x + v_i, j to ans. After adding all new values, we must delete the old ones (we can do it with one array by swapping new elements with old ones or have two arrays and swap them at each piece type). When we're done removing old elements, we sort the ans array and remove elements from the back until size is  ≤ k.
• Finally, print the contains of the ans array.
• We do m² operations to process each type and _logm² for sorting the ans array, and there are m piece types, so in total we do m³ + m * _logm² operations. Total complexity: O(m³).

PS: The technique used in this problem is known as Beam Search, and is widely used in optimization problems.

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define f(i,a,b) for(int i = (a); i <= (b); i++)
#define pb push_back
#define SZ(x) ((int)x.size())

using namespace std;

int N, K, T;
vector<int> Ans, V[105];

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d %d", &N, &K);
        f(i,1,N)
        {
            int k;
            scanf("%d", &k);
            V[i].clear();
            f(j,1,k)
            {
                int x;
                scanf("%d", &x);
                V[i].pb(x);
            }
        }

        Ans.clear();
        for(int x : V[1]) Ans.pb(x);

        f(i,2,N)
        {
            int curr_sz = SZ(Ans);
            f(j,0,curr_sz-1) for(int x : V[i]) Ans.pb(Ans[j]+x);
            int new_sz = SZ(Ans);
            f(j,0,curr_sz-1)
            {
                swap(Ans[new_sz-j-1],Ans[j]);
                Ans.pop_back();
            }
            sort(all(Ans));
            while(SZ(Ans) > K) Ans.pop_back();
        }

        for(int x : Ans) printf("%d ", x);
        printf("\n");
    }
}

H: Let's compute the area of the polygon using pseudoscalar product (not sure if this is the right term in English, in 2D it is equal to x_1y2 - x_2y1). To do that, we just sum up all the oriented areas of triangles (a_i, a_i + 1, (0, 0)). Note that if we reverse the order, the area will be exactly the opposite. That is why, we can conclude the answer from the sign of the area computed this way.

H: For any point X in the polygon, the sum of the signed angles P_iXP_i + 1 is either 2π, or  - 2π, depending on the polygon's orientation. From outside the polygon, the sum is 0.

So all we need to do is find a point in the polygon. I took the midpoint of a non-vertical edge, perturbed it by a small amount upwards and downwards, and computed the sum for these two points.

J: First sort all points by x-coordinate. Now brute force over all combinations of the minimum and maximum y for the rectangle. For each min-max pair, we can find all rectangles containing n/2+1 points using a two-pointer approach, where the pointers mark the left and right boundaries of the rectangle. When we march the left pointer forwards, we lose some points, so we must march the right pointer forwards as well. Total time is O(n³).

for each 2 X's --> for each Y --> do binary search

the idea is : you need 2 points( upper-left , lower-right )( 2 X's , 2 Y's )

the 2 X's may be the same and the 2 Y's may be the same

the bruteforce solution is O(n^4) ( bad )

to reduce the complexity a little bit you can try :

every 2 X's and 1 Y : binary search the other Y

this solution is O(n^3 logn) ( good enough to pass )

hhhh

You don't need lazy propagation at all. You're dealing with range updates and point queries.

You don't need to trade duplicates immediately.

Here

Edit :I thought its Ep-03 'B'