제출 #422104

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
422104		idk321	카니발 티켓 (IOI20_tickets)	C++17	100 / 100	1285 ms	77028 KiB

tickets

#include "tickets.h"
#include <vector>

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

const ll INF = 1000000000000000000LL;

struct Comp
{
    bool operator() (const array<int, 4>& ar1, const array<int, 4>& ar2) const
    {
        return ar1[3] < ar2[3];
    }
};

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	vector<vector<int>> answer;
    answer.resize(n, vector<int>(m, -1));



    priority_queue<array<int, 4>, vector<array<int, 4>>, Comp> pq;
    vector<vector<int>> type(n, vector<int>(m));
    ll res = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < k; j++)
        {
            res -= x[i][j];
            type[i][j] = -1;
        }
        ll sum = 0;

        pq.push({k - 1, m - 1, i, x[i][k - 1] + x[i][m - 1]});
    }

    for (int i = 0; i < n * k / 2; i++)
    {
        auto cur = pq.top();
        pq.pop();
        res += cur[3];
        type[cur[2]][cur[0]] = 0;
        type[cur[2]][cur[1]] = 1;
        if (cur[0] != 0 && type[cur[2]][cur[0] - 1] == -1)
        {
            pq.push({cur[0] - 1, cur[1] - 1, cur[2], x[cur[2]][cur[1] - 1] + x[cur[2]][cur[0] - 1]});
        }
    }

    vector<vector<int>> small(n);
    vector<vector<int>> big(n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (type[i][j] == -1) small[i].push_back(j);
            if (type[i][j] == 1) big[i].push_back(j);
        }
    }


    ll sumSmall = 0;
    ll sumBig =0;
    for (int i = 0; i < n; i++)
    {
        sumSmall += small[i].size();
        sumBig += big[i].size();
    }


    for (int a = 0; a < k; a++)
    {
        vector<array<int, 3>> byFreq;
        for (int i = 0; i < n; i++)
        {
            byFreq.push_back({small[i].size(), big[i].size(), i});
        }
        sort(byFreq.rbegin(), byFreq.rend());
        for (int i = 0; i < n / 2; i++)
        {
            int y = byFreq[i][2];
            answer[y][small[y].back()] = a;
            small[y].pop_back();
        }
        for (int i = n / 2; i < n; i++)
        {
            int y = byFreq[i][2];

            answer[y][big[y].back()] = a;
            big[y].pop_back();
        }
    }

    allocate_tickets(answer);
	return res;
}

/*
5 3 1
1 8 1000
1 3 4
3 5 6
2 5 7
1 5 10
*/

컴파일 시 표준 에러 (stderr) 메시지

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:36:12: warning: unused variable 'sum' [-Wunused-variable]
   36 |         ll sum = 0;
      |            ^~~
tickets.cpp:80:44: warning: narrowing conversion of '(& small.std::vector<std::vector<int> >::operator[](((std::vector<std::vector<int> >::size_type)i)))->std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   80 |             byFreq.push_back({small[i].size(), big[i].size(), i});
      |                               ~~~~~~~~~~~~~^~
tickets.cpp:80:59: warning: narrowing conversion of '(& big.std::vector<std::vector<int> >::operator[](((std::vector<std::vector<int> >::size_type)i)))->std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   80 |             byFreq.push_back({small[i].size(), big[i].size(), i});
      |                                                ~~~~~~~~~~~^~

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 10 / 10