oj.uz

Submission #722140

# Submission time Handle Problem Language Result Execution time Memory
722140 2023-04-11T12:42:46 Z danikoynov Carnival Tickets (IOI20_tickets) C++14
100 / 100
 811 ms 98216 KB 
#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1510;

int N, M, K, used[maxn][maxn], vis[maxn];
ll dp[310][310 * 310];
vector < vector < int > > answer;
vector < int > free_box[maxn];
struct element
{
    ll delta, row;

    bool operator < (const element &e) const
    {
        return delta > e.delta;
    }
};

struct box
{
    int row, col;
    ll val;

    bool operator < (const box &bx) const
    {
        return val < bx.val;
    }

};

bool cmp_box(box b1, box b2)
{
    return b1.row < b2.row;
}

int pt[maxn], type[maxn][maxn];
long long find_maximum(int k, vector < vector < int > > x)
{
    N = x.size();
    M = x[0].size();
    K = k;
    ll max_val = 0;
    for (int i = 0; i < N; i ++)
        for (int j = 0; j < M; j ++)
            max_val = max(max_val, (ll)(x[i][j]));
    answer.resize(N);
    for (int i = 0; i < N; i++)
    {
        answer[i].resize(M, - 1);
    }

    ll max_prize = 0;
    priority_queue < element > pq;
    for (int i = 0; i < N; i ++)
    {
        pt[i] = 0;
        for (int j = M - 1; j >= M - k; j --)
        {
            max_prize += x[i][j];
            type[i][j] = 1;
        }
        element cur;
        cur.row = i;
        cur.delta = x[i][M - k] + x[i][0];
        pq.push(cur);
    }

    for (int step = 0; step < N * k / 2; step ++)
    {
        element cur = pq.top();
        pq.pop();
        max_prize -= cur.delta;
        type[cur.row][M - k + pt[cur.row]] = 0;
        type[cur.row][pt[cur.row]] = -1;

        pt[cur.row] ++;
        if (pt[cur.row] < k)
        {
            cur.delta = x[cur.row][M - k + pt[cur.row]] + x[cur.row][pt[cur.row]];
            pq.push(cur);
        }
    }


        vector < box > small, big;
        for (int i = 0; i < N; i ++)
            for (int j = 0; j < M; j ++)
        {
            if (type[i][j] == 0)
                continue;
            box b;
            b.row = i;
            b.col = j;
            b.val = x[i][j];
            ///cout << i << " " << j << endl;
            if (type[i][j] == -1)
                small.push_back(b);
            else
                big.push_back(b);
        }


        sort(small.begin(), small.end(), cmp_box);
        sort(big.begin(), big.end(), cmp_box);
        int turn = 0;
        for (int i = 0; i < small.size(); i ++)
        {
            box b = small[i];
            answer[b.row][b.col] = turn ++;
            if (turn == k)
                turn = 0;

        }
        for (int i = 0; i < N; i ++)
        {
            for (int j = 0; j < M; j ++)
            {
                if (answer[i][j] == -1)
                    continue;
                vis[answer[i][j]] = 1;
            }

            for (int j = 0; j < k; j ++)
            {
                if (!vis[j])
                    free_box[i].push_back(j);
                vis[j] = 0;
            }
        }
        for (int i = 0; i < big.size(); i ++)
        {
            box b = big[i];
            answer[b.row][b.col] = free_box[b.row].back();
            free_box[b.row].pop_back();


        }
    allocate_tickets(answer);
    return max_prize;
}

Compilation message

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:109:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<box>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         for (int i = 0; i < small.size(); i ++)
      |                         ~~^~~~~~~~~~~~~~
tickets.cpp:133:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<box>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         for (int i = 0; i < big.size(); i ++)
      |                         ~~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 4 ms 6868 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 21 ms 3748 KB Output is correct
6 Correct 465 ms 57660 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 21 ms 4540 KB Output is correct
6 Correct 512 ms 74172 KB Output is correct
7 Correct 576 ms 81096 KB Output is correct
8 Correct 3 ms 1236 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 1 ms 352 KB Output is correct
12 Correct 6 ms 2004 KB Output is correct
13 Correct 29 ms 5144 KB Output is correct
14 Correct 21 ms 3920 KB Output is correct
15 Correct 608 ms 87948 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 980 KB Output is correct
5 Correct 33 ms 5624 KB Output is correct
6 Correct 7 ms 1164 KB Output is correct
7 Correct 9 ms 7380 KB Output is correct
8 Correct 811 ms 95056 KB Output is correct
9 Correct 790 ms 88968 KB Output is correct
10 Correct 734 ms 87912 KB Output is correct
11 Correct 770 ms 94108 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 876 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 3 ms 932 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 740 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 2 ms 980 KB Output is correct
12 Correct 3 ms 980 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 876 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 3 ms 932 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 740 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 2 ms 980 KB Output is correct
12 Correct 3 ms 980 KB Output is correct
13 Correct 21 ms 4796 KB Output is correct
14 Correct 20 ms 4908 KB Output is correct
15 Correct 25 ms 5400 KB Output is correct
16 Correct 35 ms 6292 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 3 ms 1876 KB Output is correct
19 Correct 2 ms 1644 KB Output is correct
20 Correct 24 ms 5088 KB Output is correct
21 Correct 27 ms 5432 KB Output is correct
22 Correct 28 ms 5572 KB Output is correct
23 Correct 28 ms 5948 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 4 ms 6868 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 21 ms 3748 KB Output is correct
12 Correct 465 ms 57660 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 852 KB Output is correct
17 Correct 21 ms 4540 KB Output is correct
18 Correct 512 ms 74172 KB Output is correct
19 Correct 576 ms 81096 KB Output is correct
20 Correct 3 ms 1236 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 352 KB Output is correct
23 Correct 1 ms 352 KB Output is correct
24 Correct 6 ms 2004 KB Output is correct
25 Correct 29 ms 5144 KB Output is correct
26 Correct 21 ms 3920 KB Output is correct
27 Correct 608 ms 87948 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 3 ms 980 KB Output is correct
32 Correct 33 ms 5624 KB Output is correct
33 Correct 7 ms 1164 KB Output is correct
34 Correct 9 ms 7380 KB Output is correct
35 Correct 811 ms 95056 KB Output is correct
36 Correct 790 ms 88968 KB Output is correct
37 Correct 734 ms 87912 KB Output is correct
38 Correct 770 ms 94108 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 3 ms 876 KB Output is correct
41 Correct 3 ms 852 KB Output is correct
42 Correct 3 ms 932 KB Output is correct
43 Correct 3 ms 980 KB Output is correct
44 Correct 3 ms 980 KB Output is correct
45 Correct 1 ms 340 KB Output is correct
46 Correct 1 ms 740 KB Output is correct
47 Correct 3 ms 852 KB Output is correct
48 Correct 3 ms 980 KB Output is correct
49 Correct 2 ms 980 KB Output is correct
50 Correct 3 ms 980 KB Output is correct
51 Correct 21 ms 4796 KB Output is correct
52 Correct 20 ms 4908 KB Output is correct
53 Correct 25 ms 5400 KB Output is correct
54 Correct 35 ms 6292 KB Output is correct
55 Correct 1 ms 468 KB Output is correct
56 Correct 3 ms 1876 KB Output is correct
57 Correct 2 ms 1644 KB Output is correct
58 Correct 24 ms 5088 KB Output is correct
59 Correct 27 ms 5432 KB Output is correct
60 Correct 28 ms 5572 KB Output is correct
61 Correct 28 ms 5948 KB Output is correct
62 Correct 60 ms 11208 KB Output is correct
63 Correct 57 ms 11560 KB Output is correct
64 Correct 89 ms 15280 KB Output is correct
65 Correct 315 ms 44832 KB Output is correct
66 Correct 343 ms 53716 KB Output is correct
67 Correct 9 ms 7440 KB Output is correct
68 Correct 6 ms 1128 KB Output is correct
69 Correct 506 ms 60764 KB Output is correct
70 Correct 662 ms 76860 KB Output is correct
71 Correct 787 ms 97524 KB Output is correct
72 Correct 696 ms 98216 KB Output is correct
73 Correct 751 ms 91116 KB Output is correct
74 Correct 563 ms 81928 KB Output is correct
75 Correct 625 ms 75244 KB Output is correct