oj.uz

Submission #974569

# Submission time Handle Problem Language Result Execution time Memory
974569 2024-05-03T13:14:47 Z LucaIlie Carnival Tickets (IOI20_tickets) C++17
76 / 100
 852 ms 127196 KB 
#include "tickets.h"
#include <bits/stdc++.h>

using namespace std;

struct cell {
    int i, j, val;
};

const int MAX_N = 1500;
const int MAX_M = 1500;
int x[MAX_N + 1][MAX_M + 1];
long long sx[MAX_N + 1][MAX_M + 1];
vector<int> mins[MAX_N + 1], maxs[MAX_N + 1];
bool isMax[MAX_N + 1];
vector<cell> opt;

long long find_maximum( int k, vector<vector<int>> X ) {
    int n = X.size();
    int m = X[0].size();
    vector<vector<int>> answer( n );
    long long sum = 0;

    for ( int i = 1; i <= n; i++ ) {
        answer[i - 1].resize( m );
        for ( int j = 1; j <= m; j++ ) {
            x[i][j] = X[i - 1][j - 1];
            sx[i][j] = sx[i][j - 1] + x[i][j];
            answer[i - 1][j - 1] = -1;
        }
    }

    for ( int i = 1; i <= n; i++ ) {
        for ( int j = 1; j <= k; j++ ) {
            mins[i].push_back( j );
            opt.push_back( { i, m - (k - j), x[i][j] + x[i][m - (k - j)] } );
        }
    }

    sort( opt.begin(), opt.end(), []( cell a, cell b ) {
        if ( a.val == b.val )
            return a.j > b.j;
        return a.val > b.val;
    } );
    for ( int i = 0; i < n * k / 2; i++ ) {
        mins[opt[i].i].pop_back();
        maxs[opt[i].i].push_back( opt[i].j );
    }

    for ( int i = 1; i <= n; i++ )
        reverse( mins[i].begin(), mins[i].end() );

    for ( int pas = 0; pas < k; pas++ ) {
        for ( int i = 1; i <= n; i++ )
            isMax[i] = false;

        vector<pair<int, int>> maxx;
        for ( int i = 1; i <= n; i++ ) {
            if ( !maxs[i].empty() )
                maxx.push_back( { (mins[i].empty() ? 0 : x[i][maxs[i].back()]), i } );
        }
        sort( maxx.begin(), maxx.end() );
        for ( int i = 0; i < n / 2; i++ ) {
            isMax[maxx[i].second] = true;
            answer[maxx[i].second - 1][maxs[maxx[i].second].back() - 1] = pas;
            sum += x[maxx[i].second][maxs[maxx[i].second].back()];
            maxs[maxx[i].second].pop_back();
        }
        for ( int i = 1; i <= n; i++ ) {
            if ( isMax[i] )
                continue;
            isMax[i] = true;
            answer[i - 1][mins[i].back() - 1] = pas;
            sum -= x[i][mins[i].back()];
            mins[i].pop_back();
        }
    }

    allocate_tickets( answer );
    return sum;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2904 KB Output is correct
5 Correct 1 ms 5724 KB Output is correct
6 Correct 5 ms 15964 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 18 ms 9564 KB Output is correct
6 Correct 411 ms 77904 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 20 ms 10428 KB Output is correct
6 Correct 482 ms 102396 KB Output is correct
7 Correct 513 ms 108008 KB Output is correct
8 Correct 3 ms 3420 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Runtime error 8 ms 10312 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2564 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 3 ms 3164 KB Output is correct
5 Correct 30 ms 11520 KB Output is correct
6 Correct 5 ms 5184 KB Output is correct
7 Correct 10 ms 16476 KB Output is correct
8 Correct 852 ms 127196 KB Output is correct
9 Correct 759 ms 120336 KB Output is correct
10 Correct 730 ms 118468 KB Output is correct
11 Correct 782 ms 125132 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 2 ms 2904 KB Output is correct
4 Correct 2 ms 2904 KB Output is correct
5 Correct 3 ms 3160 KB Output is correct
6 Correct 3 ms 3164 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 2 ms 3164 KB Output is correct
10 Correct 3 ms 3164 KB Output is correct
11 Correct 3 ms 3160 KB Output is correct
12 Correct 2 ms 3160 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 2 ms 2904 KB Output is correct
4 Correct 2 ms 2904 KB Output is correct
5 Correct 3 ms 3160 KB Output is correct
6 Correct 3 ms 3164 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 2 ms 3164 KB Output is correct
10 Correct 3 ms 3164 KB Output is correct
11 Correct 3 ms 3160 KB Output is correct
12 Correct 2 ms 3160 KB Output is correct
13 Correct 21 ms 9560 KB Output is correct
14 Correct 19 ms 9488 KB Output is correct
15 Correct 27 ms 10508 KB Output is correct
16 Correct 32 ms 11516 KB Output is correct
17 Correct 1 ms 4696 KB Output is correct
18 Correct 3 ms 5980 KB Output is correct
19 Correct 2 ms 5812 KB Output is correct
20 Correct 24 ms 10532 KB Output is correct
21 Correct 25 ms 10496 KB Output is correct
22 Correct 31 ms 11380 KB Output is correct
23 Correct 27 ms 11276 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2904 KB Output is correct
5 Correct 1 ms 5724 KB Output is correct
6 Correct 5 ms 15964 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 18 ms 9564 KB Output is correct
12 Correct 411 ms 77904 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 2 ms 3164 KB Output is correct
17 Correct 20 ms 10428 KB Output is correct
18 Correct 482 ms 102396 KB Output is correct
19 Correct 513 ms 108008 KB Output is correct
20 Correct 3 ms 3420 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Runtime error 8 ms 10312 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -