oj.uz

Submission #305849

# Submission time Handle Problem Language Result Execution time Memory
305849 2020-09-24T02:46:22 Z Dormi Carnival Tickets (IOI20_tickets) C++14
76 / 100
 3000 ms 215248 KB 
#include "bits/stdc++.h"
#include "tickets.h"
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
int sz(const T &a){return int(a.size());}
set<int> used[1501][2];
ll find_maximum(int k, vector<vector<int>> x){
    int n=sz(x),m=sz(x[0]);
    ll ans=0;
    priority_queue<pair<ll,pair<int,pii>>> q;
    vector<int> order;
    for(int i=0;i<n;i++){
        order.push_back(i);
        for(int j=1;j<=k;j++){
            ans+=x[i][m-j];
            used[i][0].insert(m-j);
            q.push({-x[i][j-1]-x[i][m-k+j-1],{i,{-(j-1),-(m-k+j-1)}}});
        }
    }
    for(int i=0;i<n*k/2;i++){
        auto cur=q.top();
        q.pop();
        used[cur.second.first][0].erase(used[cur.second.first][0].find(-cur.second.second.second));
        used[cur.second.first][1].insert(-cur.second.second.first);
        ans+=cur.first;
    }
    vector<vector<int>> ret(n,vector<int>(m,-1));
    for(int i=0;i<k;i++){
        sort(order.begin(),order.end(),[&](auto &lhs, auto &rhs){
            return sz(used[rhs][0])<sz(used[lhs][0]);
        });
        for(int j=0;j<n;j++){
            int loc=(j>=n/2);
            ret[order[j]][*used[order[j]][loc].begin()]=i;
            used[order[j]][loc].erase(used[order[j]][loc].begin());
        }
    }
    allocate_tickets(ret);
    return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 2 ms 896 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 32 ms 2560 KB Output is correct
6 Correct 757 ms 51628 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 416 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 40 ms 4788 KB Output is correct
6 Correct 1255 ms 116692 KB Output is correct
7 Correct 1510 ms 132964 KB Output is correct
8 Correct 7 ms 1340 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 13 ms 1724 KB Output is correct
13 Correct 40 ms 4916 KB Output is correct
14 Correct 42 ms 5556 KB Output is correct
15 Correct 1678 ms 154004 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 112 ms 7844 KB Output is correct
6 Correct 12 ms 1724 KB Output is correct
7 Correct 12 ms 1852 KB Output is correct
8 Execution timed out 3081 ms 215248 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 4 ms 768 KB Output is correct
11 Correct 4 ms 896 KB Output is correct
12 Correct 5 ms 896 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 4 ms 768 KB Output is correct
11 Correct 4 ms 896 KB Output is correct
12 Correct 5 ms 896 KB Output is correct
13 Correct 32 ms 2552 KB Output is correct
14 Correct 32 ms 2592 KB Output is correct
15 Correct 56 ms 4780 KB Output is correct
16 Correct 88 ms 7844 KB Output is correct
17 Correct 1 ms 512 KB Output is correct
18 Correct 3 ms 768 KB Output is correct
19 Correct 2 ms 640 KB Output is correct
20 Correct 62 ms 5672 KB Output is correct
21 Correct 59 ms 5672 KB Output is correct
22 Correct 71 ms 7460 KB Output is correct
23 Correct 78 ms 7296 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 2 ms 896 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 32 ms 2560 KB Output is correct
12 Correct 757 ms 51628 KB Output is correct
13 Correct 1 ms 512 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 1 ms 416 KB Output is correct
16 Correct 3 ms 768 KB Output is correct
17 Correct 40 ms 4788 KB Output is correct
18 Correct 1255 ms 116692 KB Output is correct
19 Correct 1510 ms 132964 KB Output is correct
20 Correct 7 ms 1340 KB Output is correct
21 Correct 1 ms 512 KB Output is correct
22 Correct 1 ms 512 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 13 ms 1724 KB Output is correct
25 Correct 40 ms 4916 KB Output is correct
26 Correct 42 ms 5556 KB Output is correct
27 Correct 1678 ms 154004 KB Output is correct
28 Correct 1 ms 512 KB Output is correct
29 Correct 0 ms 512 KB Output is correct
30 Correct 1 ms 512 KB Output is correct
31 Correct 5 ms 1024 KB Output is correct
32 Correct 112 ms 7844 KB Output is correct
33 Correct 12 ms 1724 KB Output is correct
34 Correct 12 ms 1852 KB Output is correct
35 Execution timed out 3081 ms 215248 KB Time limit exceeded
36 Halted 0 ms 0 KB -