oj.uz

Submission #423743

# Submission time Handle Problem Language Result Execution time Memory
423743 2021-06-11T12:15:08 Z humbertoyusta Carnival Tickets (IOI20_tickets) C++14
16 / 100
 723 ms 80632 KB 
#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define pb push_back
#define all(x) x.begin() , x.end()
typedef long long ll;
typedef pair<int,int> ii;

long long find_maximum(int k, std::vector<std::vector<int>> x) {

	int n = x.size();
	int m = x[0].size();

	std::vector<std::vector<int>> answer, fans;
	for (int i = 0; i < n; i++) {
		std::vector<int> row(m);
		for (int j = 0; j < m; j++) {
            row[j] = -1;
		}
		answer.push_back(row);
		fans.pb(row);
	}

	ll res = 0;

	vector<vector<ii>> mat;
	for(int i=0; i<n; i++){
        vector<ii> row(m);
        for(int j=0; j<m; j++){
            row[j] = { x[i][j] , j };
        }
        sort(all(row));
        mat.pb(row);
	}

	for(int i=0; i<n; i++){
        for(int j=0; j<k; j++){
            res -= mat[i][j].f;
            fans[i][j] = j;
        }
	}

	priority_queue<pair<int,ii>> q;

	for(int i=0; i<n; i++){
        q.push({mat[i][k-1].f + mat[i][m-1].f,{i,-1}});
	}

	for(int t=0; t<n*k/2; t++){

        pair<ll,ii> p = q.top();
        res += p.f;

        q.pop();

        fans[p.s.f][m+p.s.s] = fans[p.s.f][k+p.s.s];
        fans[p.s.f][k+p.s.s] = -1;

        if( abs(p.s.s - 1) <= k ){
            p.s.s--;
            q.push({mat[p.s.f][k+p.s.s].f+mat[p.s.f][m+p.s.s].f,{p.s.f,p.s.s}});
        }
	}

	for(int i=0; i<n; i++)
        for(int j=0; j<m; j++){
            answer[i][mat[i][j].s] = fans[i][j];
            //db(fans[i][j])
        }

	allocate_tickets(answer);
	return res;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB There is no ticket of color 1 on day 0
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 28 ms 4288 KB Output is correct
6 Correct 723 ms 80632 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Contestant returned 2 but the tickets gives a total value of 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB There is no ticket of color 1 on day 2
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB There is no ticket of color 1 on day 2
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB There is no ticket of color 1 on day 2
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB There is no ticket of color 1 on day 0
2 Halted 0 ms 0 KB -