oj.uz

Submission #974465

# Submission time Handle Problem Language Result Execution time Memory
974465 2024-05-03T11:15:36 Z LucaIlie Carnival Tickets (IOI20_tickets) C++17
27 / 100
 490 ms 113332 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 );
        //printf( "%d %d\n", opt[i].i, opt[i].j );
    }


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

        /*for ( int j: mins[i] )
            printf( "%d ", j );
        printf( "    " );
        for ( int j: maxs[i] )
            printf( "%d ", j );
        printf( "\n" );*/
    }
    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;
            if ( mins[i].empty() )
                exit( 1 );
            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 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 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 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 18 ms 10332 KB Output is correct
6 Correct 414 ms 99852 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 21 ms 11012 KB Output is correct
6 Correct 456 ms 107832 KB Output is correct
7 Correct 490 ms 113332 KB Output is correct
8 Incorrect 3 ms 3416 KB There is no ticket of color 90 on day 1
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 0
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 5980 KB Output is correct
6 Correct 5 ms 15964 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 2 ms 3164 KB Output is correct
11 Correct 18 ms 10332 KB Output is correct
12 Correct 414 ms 99852 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 2 ms 3164 KB Output is correct
17 Correct 21 ms 11012 KB Output is correct
18 Correct 456 ms 107832 KB Output is correct
19 Correct 490 ms 113332 KB Output is correct
20 Incorrect 3 ms 3416 KB There is no ticket of color 90 on day 1
21 Halted 0 ms 0 KB -