oj.uz

Submission #853797

# Submission time Handle Problem Language Result Execution time Memory
853797 2023-09-25T09:12:13 Z ntkphong Carnival Tickets (IOI20_tickets) C++14
27 / 100
 395 ms 73268 KB 
#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;

long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	
	vector<vector<int>> answer(n, vector<int> (m, -1));
    
    int timer = 0;
    long long sum = 0;
    vector<int> l(n, 0), r(n, 0), rr(n, 0);
    
    for(int i = 0; i < n; i ++) {
        l[i] = 0;
        r[i] = m - 1 - k + 1;
    
        timer += k;
    
        for(int j = 0; j < k; j ++) 
            sum += x[i][m - 1 - j];
    }
    
    for(int i = 0; i < n; i ++) rr[i] = m - 1;
    
    priority_queue<array<int, 2>> pq;
    
    for(int i = 0; i < n; i ++) {
        int L = l[i];
        int R = r[i];
        
        pq.push({- x[i][L] - x[i][R], i});
    }
    
    while(!pq.empty() && timer > k * n / 2) {
        int c = pq.top()[0];
        int i = pq.top()[1];
        pq.pop();
        
        sum += c;
        l[i] ++ ;
        r[i] ++ ;
        timer --;
        
        if(r[i] < m) {
            int L = l[i];
            int R = r[i];
            pq.push({- x[i][L] - x[i][R], i});
        }
    }
    
    for(int j = 0; j < k; j ++) {
        vector<array<int, 3>> p; 
        
        for(int i = 0; i < n; i ++) {
            if(l[i] > 0) p.push_back({x[i][l[i] - 1], i, 0});
            if(rr[i] >= r[i]) p.push_back({x[i][rr[i]], i, 1});
        }
        
        sort(p.begin(), p.end());
        reverse(p.begin(), p.end());
        
        vector<int> mark(n, 0);
        int cnt = 0, _cnt = 0;
        
        for(auto [c, i, type] : p) {
            if(mark[i]) continue ;
            
            if(type == 0 && cnt < n / 2) {
                cnt ++ ;
                mark[i] = true;
                answer[i][l[i] - 1] = j;
                l[i] -- ;
            }
            
            if(type == 1 && _cnt < n / 2) {
                _cnt ++ ;
                mark[i] = true;
                answer[i][rr[i]] = j;
                rr[i] ++ ;
            }
        }
    }
	
	allocate_tickets(answer);	
	return sum;
}

Compilation message

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:67:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |         for(auto [c, i, type] : p) {
      |                  ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 444 KB Output is correct
5 Correct 16 ms 3160 KB Output is correct
6 Correct 395 ms 73268 KB Output is correct

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 444 KB Output is correct
11 Correct 16 ms 3160 KB Output is correct
12 Correct 395 ms 73268 KB Output is correct
13 Incorrect 0 ms 348 KB There is no ticket of color 0 on day 2
14 Halted 0 ms 0 KB -