oj.uz

Submission #443748

# Submission time Handle Problem Language Result Execution time Memory
443748 2021-07-12T02:13:09 Z fivefourthreeone Carnival Tickets (IOI20_tickets) C++17
27 / 100
 669 ms 79340 KB 
#include "tickets.h"
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 3;
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 1501;
int type[mxN][mxN];
int lev[mxN];
ll find_maximum(int k, vector<vector<int>> arr) {
    int n = arr.size();
    int m = arr[0].size();
    vector<vector<int>> s(n, vector<int>(m, -1));
    ll res = 0;
    priority_queue<ttgl, vector<ttgl>, greater<ttgl>> pq;
    owo(i, 0, n) {
        sort(arr[i].begin(), arr[i].end());
        pq.push({arr[i][0] + arr[i][m-k], i});
        lev[i] = 0;
        owo(j, 0, k) {
            res += arr[i][m-j-1];
            type[i][m-j-1] = 1;
        }
    }
    owo(_, 0, n*k/2) {
        auto p = pq.top();
        pq.pop();
        res -= p.first;
        type[p.second][m-k+lev[p.second]] = 0;
        type[p.second][lev[p.second]] = -1;
        lev[p.second]++;
        if(lev[p.second] < k)  pq.push({arr[p.second][lev[p.second]] + arr[p.second][m-k+lev[p.second]], p.second});
    }
    vector<vector<int>> pos(n);
    vector<vector<int>> neg(n);
    owo(i, 0, n) {
        owo(j, 0, m) {
            if(type[i][j]==1)pos[i].senpai(j);
            else if(type[i][j]==-1)neg[i].senpai(j);
        }
    }
    owo(col, 0, k) {
        int cntr = 0;
        owo(i, 0, n) {
            if(pos[i].size() > neg[i].size()) {
                s[i][pos[i].back()] = col;
                pos[i].pop_back();
            }else if(neg[i].size() > pos[i].size()) {
                s[i][neg[i].back()] = col;
                neg[i].pop_back();
            }else {
                if(cntr&1) {
                    s[i][pos[i].back()] = col;
                    pos[i].pop_back();
                }else {
                    s[i][neg[i].back()] = col;
                    neg[i].pop_back();
                }
                cntr++;
            }
        }
    }
  	allocate_tickets(s);
    return res;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 2 ms 1612 KB Output is correct
6 Correct 5 ms 6860 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 28 ms 4568 KB Output is correct
6 Correct 669 ms 79340 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Contestant returned 4 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 Contestant returned 11 but the tickets gives a total value of 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 2 ms 1612 KB Output is correct
6 Correct 5 ms 6860 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 3 ms 844 KB Output is correct
11 Correct 28 ms 4568 KB Output is correct
12 Correct 669 ms 79340 KB Output is correct
13 Incorrect 1 ms 204 KB Contestant returned 4 but the tickets gives a total value of 6
14 Halted 0 ms 0 KB -