Submission #1081131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081131		serifefedartar	Akcija (COCI21_akcija)	C++17	30 / 110	690 ms	604 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 2100;

#define int long long
vector<pair<int,int>> v;
int sg[4*MAXN], lazy[4*MAXN];
void init(int k, int a, int b) {
    if (a == b) {
        sg[k] = a;
        lazy[k] = 0;
        return ;
    }
    init(2*k, a, (a+b)/2);
    init(2*k+1, (a+b)/2+1, b);
    sg[k] = min(sg[2*k], sg[2*k+1]);
    lazy[k] = 0;
}

void push(int k, int a, int b) {
    if (lazy[k]) {
        sg[k] += lazy[k];
        if (a != b) {
            lazy[2*k] += lazy[k];
            lazy[2*k+1] += lazy[k];
        }
        lazy[k] = 0;
    }
}

void update(int k, int a, int b, int q_l, int q_r, int val) {
    push(k, a, b);
    if (b < q_l || a > q_r)
        return ;
    if (q_l <= a && b <= q_r) {
        lazy[k] += val;
        push(k, a, b);
        return ;
    }
    update(2*k, a, (a+b)/2, q_l, q_r, val);
    update(2*k+1, (a+b)/2+1, b, q_l, q_r, val);
    sg[k] = min(sg[2*k], sg[2*k+1]);
}

int query(int k, int a, int b, int q_l, int q_r) {
    if (b < q_l || a > q_r)
        return 1e9;
    push(k, a, b);
    if (q_l <= a && b <= q_r)
        return sg[k];
    return min(query(2*k, a, (a+b)/2, q_l, q_r), query(2*k+1, (a+b)/2+1, b, q_l, q_r));
}

struct Partition {
    int n = 2100;
    vector<int> ban, here;
    int cnt = 0, cost = 0;
    Partition(vector<int> _ban) : ban(_ban) {
        n = ban.size();
        cnt = cost = 0;
        init(1, 1, n);
        for (int i = 0; i < n; i++) {
            if (ban[i] != -1 && (ban[i] == 1 || query(1, 1, n, v[i].s, n) == 0))
                continue;
            cnt++;
            cost += v[i].f;
            if (ban[i] != -1)
                here.push_back(i);
            update(1, 1, n, v[i].s, n, -1);
        }
    }
};

bool operator <(Partition A, Partition B) {
    return make_pair(A.cnt, -A.cost) < make_pair(B.cnt, -B.cost);
}

signed main() {
    fast;
    int n, k;
    cin >> n >> k;

    v = vector<pair<int,int>>(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].f >> v[i].s;
    sort(v.begin(), v.end());

    set<Partition> pq;
    vector<int> Q(n, 0);
    pq.insert(Partition(Q));
    while (!pq.empty()) {
        Partition Q = *pq.begin();
        pq.erase(pq.begin());

        cout << Q.cnt << " " << Q.cost << "\n";
        k--;
        if (k == 0)
            exit(0);

        vector<int> ban_here = Q.ban;
        for (auto u : Q.here) {
            ban_here[u] = 1;
            pq.insert(Partition(ban_here));
            while(pq.size() > k)
                pq.erase(prev(pq.end()));
            ban_here[u] = -1;
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:111:29: warning: comparison of integer expressions of different signedness: 'std::set<Partition>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  111 |             while(pq.size() > k)
      |                   ~~~~~~~~~~^~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 30
• Subtask 6: 0 / 20