Submission #1280036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280036		andrei_iorgulescu	Teams (IOI15_teams)	C++20	21 / 100	4093 ms	27748 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"

using namespace std;

using integer = int;
#define int long long

struct DS
{
    int n;
    vector<pair<int, int>> a;

    void init(int N, vector<pair<int, int>> A)
    {
        a = A;
        n = N;
    }

    int query_kth(int l, int r, int k)
    {
        vector<int> rs;
        for (auto it : a)
        {
            if (it.first >= l and it.first <= r)
                rs.push_back(it.second);
        }
        if (rs.size() < k)
            return n + 1;
        sort(rs.begin(), rs.end());
        return rs[k - 1];
    }

    int cate_incl(int l, int r)
    {
        int ct = 0;
        for (auto it : a)
        {
            if (it.first >= l and it.second <= r)
                ct++;
        }
        return ct;
    }
};

DS wavelet;///eu cand nu dau overkill
int n;

void init(integer N, integer A[], integer B[])
{
    n = N;
    vector<pair<int, int>> a;
    for (int i = 0; i < N; i++)
        a.push_back({A[i], B[i]});
    wavelet.init(n, a);
}

integer can(integer M, integer K[])
{
    int m = M, sm = 0;
    map<int, int> mp;
    for (int i = 0; i < m; i++)
    {
        mp[K[i]] += K[i], sm += K[i];
    }
    if (sm > n)
        return 0;
	vector<pair<int, int>> a;
	for (auto it : mp)
        a.push_back(it);
    a.push_back({0, 0});
    sort(a.begin(), a.end());///probabil era deja sortat dar idk
    set<int> s;
    vector<int> dp(a.size());
    dp[0] = 0;
    s.insert(0);
    set<pair<int, int>> bang;
    int ans = wavelet.cate_incl(1, n);
    vector<int> tranz(a.size() + 1);
    for (int i = 1; i < a.size(); i++)
    {
        /*while (!bang.empty())
        {
            pair<int, int> it = *bang.begin();
            if (it.first >= a[i].first)
                break;
            bang.erase(it);
            int xx = *s.upper_bound(it.second);
            int zz = it.second;
            s.erase(xx);
            if (s.upper_bound(it.second) != s.end())
            {
                int yy = *s.upper_bound(it.second);
                bang.erase({wavelet.query_kth(a[xx].first + 1, a[yy].first - 1, dp[yy] - dp[xx]), xx});
                bang.insert({wavelet.query_kth(a[zz].first + 1, a[yy].first - 1, dp[yy] - dp[zz]), zz});
            }
        }
        int cn = *s.rbegin();
        dp[i] = a[i].second + dp[cn] + wavelet.cate_incl(a[cn].first + 1, a[i].first - 1);
        bang.insert({wavelet.query_kth(a[cn].first + 1, a[i].first - 1, dp[i] - dp[cn]), cn});*/
        for (int j = 0; j < i; j++)
        {

            int cr = max(dp[i], dp[j] + a[i].second + wavelet.cate_incl(a[j].first + 1, a[i].first - 1));
            if (cr > dp[i])
                dp[i] = cr, tranz[i] = j;
        }
        ans = max(ans, dp[i] + wavelet.cate_incl(a[i].first + 1, n));
    }
    for (int i = 1; i < a.size(); i++)
    {
        for (int j = i + 1; j < a.size(); j++)
        {
            if (tranz[i] < tranz[j] and tranz[j] < i)
                assert(false);
        }
    }
    if (ans > n)
        return 0;
    else
        return 1;
}

• Subtask 1: 21 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23