Problem - A - Curriculum Vitae

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 50, M = 5050, mod = 9901, MAX_N = 1e3 + 50, INF = 0x3f3f3f3f;
#define int long long
#define ld long double
#define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)

int n, A[M], dp[M], ans = 0;

signed main () {
    IOS;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (A[i] >= A[j]) {
                dp[i] = max (dp[i], dp[j] + 1);
            }
        }
        ans = max (ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}

Problem - B - Math Show

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 50, M = 5050, mod = 9901, MAX_N = 1e3 + 50, INF = 0x3f3f3f3f;
#define int long long
//#define ld long double
#define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)

int n, k, m, a[M];
int ans, s, t, cnt, sum;

void init () {
    cin >> n >> k >> m;
    for (int i = 1; i <= k; i++) {
        cin >> a[i];
        s += a[i];
    }
}

signed main () {
    IOS;
    init ();
    sort (a + 1, a + k + 1);
    for (int i = 0; i <= n; i++) {
        t = s * i;
        if (t > m) break;
        sum = t, cnt = (k + 1) * i;
        for (int j = 1; j <= k; j++) {
            for (int r = i + 1; r <= n; r++) {
                cnt++;
                sum += a[j];
                if (sum > m) {
                    cnt--;
                    j = k + 1;
                    break;
                }
            }
        }
        ans = max (ans, cnt);
    }
    cout << ans << endl;
    return 0;
}

Problem - C - Four Segments

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 50, M = 5050, mod = 9901, MAX_N = 1e3 + 50, INF = 0x3f3f3f3f;
#define int long long
//#define ld long double
#define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
int num[N], s[N];

int sum (int l, int r) {
    return s[r] - s[l];
}

int n, a, k, pos, b, c, ans, cnt;

void init () {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
        s[i] = s[i - 1] + num[i];
    }
}

signed main () {
    IOS;
    init ();
    ans = -INF;
    for (int i = 0; i <= n; i++) {
        k = s[i];
        pos = i;
        for (int j = i; j <= n; j++) {
            if (s[j] < k) {
                pos = j;
                k = s[j];
            }
            cnt = sum (0, i) - sum (i, pos) + sum (pos, j) - sum (j, n);
//            cout << cnt << endl;
            if (cnt >= ans) {
                a = i, b = pos, c = j;
                ans = cnt;
            }
        }
    }
    cout << a << " " << b << " " << c << endl;

    return 0;
}

Problem - D - Monitor

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 50, M = 600, mod = 9901, MAX_N = 1e3 + 50, INF = 0x3f3f3f3f;
//#define int long long
//#define ld long double
#define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)

int n, m, k, q, s[M][M];
long long a[M][M], x, y;

void init () {
    cin >> n >> m >> k >> q;
    for (int i = 0; i < q; i++) {
        cin >> x >> y >> a[x][y];
        a[x][y]++;
    }
}

bool check (int mid) {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i][j] && a[i][j] <= mid) s[i][j] = 1;
            else s[i][j] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    for (int i = k; i <= n; ++i)
        for (int j = k; j <= m; ++j) {
            int t = s[i][j] - s[i - k][j] - s[i][j - k] + s[i - k][j - k];
            if (t == k * k)
                return 1;
        }
    return 0;
}

signed main () {
    IOS;
    init ();
    int l = 0, r = 1e9 + 10;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check (mid)) r = mid;
        else l = mid + 1;
    }
    if (check (r)) cout << r - 1 << endl;
    else cout << -1 << endl;
    return 0;
}

Problem - F - Random Query

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 50, M = 600, mod = 9901, MAX_N = 1e3 + 50, INF = 0x3f3f3f3f;
#define int long long
#define ld long double
#define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)

int n, a[N], k[N], ans;

signed main () {
    IOS;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = n; i >= 1; i--) {
        if (k[a[i]] == 0) {
            ans += i * (n - i + 1);
        } else
            ans += i * (k[a[i]] - i);
        k[a[i]] = i;
    }
    cout << fixed << setprecision (6) << (ld) (ans * 2 - n) / (n * n);
    return 0;
}