oj.uz

Submission #974558

# Submission time Handle Problem Language Result Execution time Memory
974558 2024-05-03T13:06:51 Z LucaIlie Carnival Tickets (IOI20_tickets) C++17
27 / 100
 521 ms 113572 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;
const long long INF = 1e15;
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], minTake[MAX_N + 1], maxTake[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 ) { 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;
            if ( mins[i].empty() )
                exit( 1 );
            answer[i - 1][mins[i].back() - 1] = pas;
            sum -= x[i][mins[i].back()];
            mins[i].pop_back();
        }
        for ( int i = 1; i <= n; i++ ) {
            if ( !isMax[i] )
                exit( 1 );
        }
    }

    allocate_tickets( answer );
    return sum;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2664 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 2 ms 5980 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 2396 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2624 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 18 ms 10328 KB Output is correct
6 Correct 417 ms 99924 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 18 ms 10764 KB Output is correct
6 Correct 521 ms 107628 KB Output is correct
7 Correct 496 ms 113572 KB Output is correct
8 Incorrect 4 ms 3420 KB There is no ticket of color 90 on day 55
9 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2664 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 5 ms 15964 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2624 KB Output is correct
10 Correct 2 ms 3164 KB Output is correct
11 Correct 18 ms 10328 KB Output is correct
12 Correct 417 ms 99924 KB Output is correct
13 Correct 1 ms 2648 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 2 ms 3164 KB Output is correct
17 Correct 18 ms 10764 KB Output is correct
18 Correct 521 ms 107628 KB Output is correct
19 Correct 496 ms 113572 KB Output is correct
20 Incorrect 4 ms 3420 KB There is no ticket of color 90 on day 55
21 Halted 0 ms 0 KB -