oj.uz

Submission #431996

# Submission time Handle Problem Language Result Execution time Memory
431996 2021-06-17T18:32:35 Z TryMax Carnival Tickets (IOI20_tickets) C++17
14 / 100
 636 ms 66568 KB 
#include "tickets.h"
#ifdef LOCAL
    #include "grader.cpp"
#endif // LOCAL
#include <bits/stdc++.h>

#define f first
#define s second
#define ll long long
#define pb push_back

using namespace std;

const int N = 2e6 + 10;

int have[N], was[N], cnt[N], pl[N], pr[N];

ll find_maximum(int k, vector<vector<int>> x){
    int n = x.size();
    int m = x[0].size();
    int tans = 0;
    vector<pair<int, int>> t;
    for(int i = 0; i < n; ++i){
        for(int j = m - 1; j >= m - k; --j)
            tans += x[i][j];
//        cout << i << endl;
        for(int j = 0; j < k; ++j)
            t.pb({-x[i][m - k + j] - x[i][j], i});
    }
//    cout << 1 << endl;
    sort(t.begin(), t.end(), greater<pair<int, int>>());
    for(int i = 0; i < n * k / 2; ++i)
        ++cnt[t[i].s], tans += t[i].f;
    vector<int> t1;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < cnt[i]; ++j)
            t1.pb(i);
    vector<vector<int>> ans;
    ans.resize(n);
    for(int i = 0; i < n; ++i){
        ans[i].resize(m);
        for(int j = 0; j < m; ++j)
            ans[i][j] = -1;
    }
    for(int i = 0; i < n; ++i)
        pl[i] = 0, pr[i] = m - 1;
    for(int i = 0; i < k; ++i){
        for(int j = 0; j < n; ++j)
            was[j] = 0;
        for(int j = 0; j < n / 2; ++j)
            was[t1[i + k * j]] = 1, ans[t1[i + k * j]][pl[t1[i + k * j]]++] = i;
        for(int j = 0; j < n; ++j)
            if(was[j] == 0)
                ans[j][pr[j]--] = i;
    }
    allocate_tickets(ans);
    return tans;
}
/*
2 3 2
0 2 5
1 1 3

7
0 -1 1
-1 1 0

4 2 1
5 9
1 4
3 6
2 7

12
-1 0
0 -1
0 -1
-1 0
*/

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 224 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Incorrect 1 ms 332 KB Contestant returned 18919508441 but the tickets gives a total value of 1739639257
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Contestant returned 2727881086 but the tickets gives a total value of -1567086210
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 460 KB Output is correct
5 Correct 25 ms 2680 KB Output is correct
6 Correct 590 ms 60024 KB Output is correct
7 Correct 617 ms 63784 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 6 ms 972 KB Output is correct
13 Correct 20 ms 2508 KB Output is correct
14 Correct 21 ms 2504 KB Output is correct
15 Correct 636 ms 66568 KB Output is correct

Subtask #4
0 / 14.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 Incorrect 1 ms 204 KB Contestant returned 24057831018 but the tickets gives a total value of -1711972758
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 3 ms 460 KB Contestant returned 39376297182 but the tickets gives a total value of 721591518
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 3 ms 460 KB Contestant returned 39376297182 but the tickets gives a total value of 721591518
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 224 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Incorrect 1 ms 332 KB Contestant returned 18919508441 but the tickets gives a total value of 1739639257
5 Halted 0 ms 0 KB -