## Bài 1: Queens

### Hint:
- Dễ dàng nhận thấy, giới hạn của $n$ và $k$ là rất nhỏ, nên ta có thể làm theo tư tưởng đệ quy

### Subtask 1: $(k = 1)$
- Bây giờ chỉ cần đặt một con hậu, mà cần đặt sao cho tổng trọng số của các ô có quân hậu đặt là lớn nhất, suy ra ta tham lam, đặt con hậu ở vị trí có trọng số lớn nhất

int mx = INT_MIN;
for (int i = 1; i <= n; i++){
    for (int j = 1; j <= n; j++){
        mx = max(mx, a[i][j]);
    }
}

### Subtask 2: $(k \leq 3)$
- Nhận thấy số lượng ô tối đa của bảng là $8 \times 8 = 64$ mà $64 ^ 3 \approx 2 \times 10 ^ 5$
- Vì vậy, ta có thể thử mọi cách xếp các con hậu vào bảng

int mx = INT_MIN;
pair <int, int> vt[3];
void dequy(int x, int y, int tong, int sl){
    if (sl > 3) return ;
    if (x == n && y == n + 1){
        if (sl == 3){
            //Check xem các con hậu có trùng nhau không?
            //Các con hậu ở vị trí vt[0], vt[1], vt[2]
            //Nếu không trùng thì mx = max(mx, tong);
        }
        return ;
    }
    int newx = x, newy = y;
    if (newy == n + 1) newx++, newy = 1;
    dequy(newx, newy, tong, sl);
    vt[sl].fi = x, vt[sl].se = y;
    dequy(newx, newy, tong + a[x][y], sl + 1);
}
//Gọi hàm dequy(1, 1, 0, 0);

### Subtask 3: $(k \leq 8)$
- Thay vì sinh xong rồi kiểm tra, thì chúng ta có thể vừa sinh vừa kiểm tra
- Ta có đường chéo từ trái sang phải, từ trên xuống dưới, gọi tắt là $cheo1$ và đường chéo từ phải sang trái. từ trên xuống dưới, gọi tắt là $cheo2$. Bây giờ chỉ còn việc từ ô $x, y$, xem ô đó sẽ là loại đường chéo nào ở $cheo1$ và $cheo2$
- Về $cheo1$, lấy ví dụ các ô cùng đường $cheo1$ thì ta có $(1, 1), (2, 2), (3, 3)$ hoặc $(1, 2), (2, 3), (3, 4)$. Nhận thấy rằng từ ô $(x, y)$, ta có thể cộng cả hai $x, y$ với $1$ để tạo ra các ô có cùng đường $cheo1$. Có thể nối dài thêm các ô và ta có thể mã hoá các loại đường $cheo1$ là giá trị $y$ ở hàng thứ $1$, hay là mã hoá thành $y - (x - 1)$
- Về $cheo2$, lấy ví dụ các ô cùng đường $cheo2$ thì ta có $(1, 3), (2, 2), (3, 1)$ hoặc $(2, 4), (3, 3), (4, 2)$. Nhận thấy rằng từ ô $(x, y)$, ta có thể đồng thời cộng $x$ và trừ $y$ với $1$ để tạo ra các ô có cùng đường $cheo2$. Có thể nối dài thêm các ô và ta có thể mã hoá các loại đường $cheo2$ là giá trị $y$ ở hàng thứ $1$, hay là mã hoá thành $y + (x - 1)$
- Vấn đề là các loại đường $cheo1$, có thể là số âm, nên ta có thể dùng $map$ hoặc cộng thêm một biến $bonus$
- Tạo mảng $hang[x]$, $cot[x]$, $cheo1[x]$, $cheo2[x]$ để kiểm tra xem hàng $x$, cột $x$, $cheo1$ và $cheo2$ có quân hậu nào không, nhưng ta có thể tối ưu bằng nhận xét rằng, mỗi con hậu sẽ ở những hàng riêng biệt, vì vậy nên ta không cần lưu mảng $hang[x]$

int bonus = 100, mx = INT_MIN;
bool cot[10], cheo1[1003], cheo2[1003];
int tinh1(int x, int y){
    return (y - (x - 1) + bonus);
}
int tinh2(int x, int y){
    return (y + (x - 1) + bonus);
}
void dequy(int i, int tong, int dem){
    //cout << i << " " << tong << " " << dem << "\n";
    if (i == n + 1){
        //cout << dem << "\n";
        if (dem == k) mx = max(mx, tong);
        return ;
    }
    dequy(i + 1, tong, dem);
    for (int j = 1; j <= n; j++){
        if (!cot[j] && !cheo1[tinh1(i, j)] && !cheo2[tinh2(i, j)]){
            cot[j] = true, cheo1[tinh1(i, j)] = true, cheo2[tinh2(i, j)] = true;
            dequy(i + 1, tong + a[i][j], dem + 1);
            cot[j] = false, cheo1[tinh1(i, j)] = false, cheo2[tinh2(i, j)] = false;
        }
    }
}
//dequy(1, 0, 0);
//Code của tknhatbm trong thi :)

## Bài 2: Akseq

### Hint:
- Dễ dàng nhận thấy nếu thoả mãn ở vị trí $i$ thì cũng sẽ thoả mãn ở vị trí $j$ nếu $j = i + xn$ với $x$ là số thoả mãn $i + x \times n + d - 1 \leq n \times k$ hoặc từ vị trí $i$ nếu thoả mãn thì sẽ có $\lfloor (n \times k + 1 - d - i) \div x \rfloor + 1$ vị trí như vậy (tính cả $i$)

### Subtask 1: $(n * k \leq 3 * 10 ^ 3)$
- Ta có thể tạo mảng $A^k$ rồi sau đó duyệt từng đoạn có độ dài $d$, và kiểm tra điều kiện

// Tự tạo mảng A ^ k nhé :)
ll m = n * k, dem = 0;
for (int i = 1; i + d - 1 <= m; i++){
    ll tong = 0, mn = LLONG_MAX;
    for (int j = i; j <= i + d - 1; j++) tong += a[j], mn = min(mn, a[j]);
    if (2 * mn * d > tong) dem++;
}

### Subtask 2: $(n * k \leq 4 * 10 ^ 5)$
- Với tổng của dãy thì ta có thể dùng kĩ thuật **sliding window**, còn về min thì ta có thể xử lý bài toán con **Tìm Max/Min trong đoạn tịnh tiến**, dùng **Deque, Multiset, Segment Tree, Sparse Table, ...**
- https://wiki.vnoi.info/algo/data-structures/deque-min-max

ll m = n * k, dem = 0;
for (int i = 1; i + d - 1 <= m; i++){
    ll tong = S[i + d - 1] - S[i - 1], mn = get(i, i + d - 1);
    if (2 * mn * d > tong) dem++;
}

### Subtask 3: $(n * k \leq 5 * 10 ^ 7)$
- Giống **Subtask 2**, nhưng hãy lưu ý rằng có thể bị quá thời gian do dùng cấu trúc dữ liệu quá chậm như **Multiset**, khuyên nên dùng **Deque**

ll m = n * k, dem = 0;
for (int i = 1; i + d - 1 <= m; i++){
    ll tong = S[i + d - 1] - S[i - 1], mn = get(i, i + d - 1);
    if (2 * mn * d > tong) dem++;
}

### Subtask 4: $(n * k \leq 5 * 10 ^ {10})$
- Áp dụng gợi ý, ta chỉ cần duyệt các vị trí $i$ trong khoảng $1 \rightarrow n$, nếu thoả thì $dem$ tăng lên số vị trí như vậy
- Với mỗi đoạn từ $i \rightarrow i + d - 1$ thì ta xét hai trường hợp
- Nếu $i + d - 1 \leq n$ thì ta xét như **Subtask 2, 3**
- Nếu $i + d - 1 > n$ thì ta sẽ đặt $kt = i + d - 1$ và chia đoạn ra như sau
- Nhận thấy giờ với mỗi đoạn, ta có thể tính dễ dàng

m = n * k;
for (int i = 1; i <= n; i++){
    int bd = i, kt = i + d - 1;
    if (kt > m) continue;
    if (kt <= n){
        ll vt = 2 * get(bd, kt) * d;
        ll vp = S[kt] - S[bd - 1];
        bool check = (vt > vp);
        dem += check * k;
        continue;
    }
    ll u = 1, v = kt % n, tong = 0, mn = LLONG_MAX;
    if (v == 0) v = n;
    tong += S[n] - S[bd - 1];
    tong += S[v] - S[u - 1];
    mn = min(get(bd, n), get(u, v));
    ll oL = n + 1, oR = kt - v;
    if (oL <= oR){
        ll sd = (oR - oL + 1) / n;
        tong += sd * S[n];
        mn = get(1, n);
    }
    ll vt = 2 * mn * d;
    ll vp = tong;
    bool check = (vt > vp);
    dem += check * ((m + 1 - d - i) / n + 1);
}
//Code của tknhatbm trong thi :)