oj.uz

Submission #1081131

# Submission time Handle Problem Language Result Execution time Memory
1081131 2024-08-29T18:41:29 Z serifefedartar Akcija (COCI21_akcija) C++17
30 / 110
 690 ms 604 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 690 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Incorrect 690 ms 600 KB Output isn't correct
28 Halted 0 ms 0 KB -