Submission #974093

#	Time	Username	Problem	Language	Result	Execution time	Memory
974093		LucaIlie	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	257 ms	171604 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 300;
const int MAX_M = 300;
const int MAX_K = 300;
const long long INF = 1e15;
int x[MAX_N + 1][MAX_M + 1];
long long sx[MAX_N + 1][MAX_M + 1];
int tai[MAX_N + 1][MAX_N * MAX_K + 1];
long long dp[MAX_N + 1][MAX_N * MAX_K + 1];
vector<int> mins[MAX_N + 1], maxs[MAX_N + 1];
bool isMax[MAX_N + 1];

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

    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 a = 0; a <= k * i; a++ )
            dp[i][a] = -INF;
        for ( int a = 0; a <= k * (i - 1); a++ ) {
            for ( int b = 0; b <= k; b++ ) {
                if ( dp[i - 1][a] - sx[i][b] + sx[i][m] - sx[i][m - (k - b)] > dp[i][a + b] ) {
                    dp[i][a + b] = dp[i - 1][a] - sx[i][b] + sx[i][m] - sx[i][m - (k - b)];
                    tai[i][a + b] = b;
                }
            }
        }
        //for ( int a = 0; a <= k * i; a++ )
          //  printf( "(%d %d) ", dp[i][a], tai[i][a] );
        //printf( "\n" );
    }

    int a = k * n / 2;
    for ( int i = n; i >= 1; i-- ) {
        int b = tai[i][a];
        for ( int j = b; j >= 1; j-- )
            mins[i].push_back( j );
        for ( int j = m; j > m - (k - b); j-- )
            maxs[i].push_back( j );
        //printf( "ba %d %d\n", i, b );
        a -= b;
    }

    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( { x[i][maxs[i].back()], i } );
        }
        sort( maxx.begin(), maxx.end() );
        for ( int i = 0; i < n / 2; i++ ) {
            isMax[maxx[i].second] = true;
            //printf( "%d\n", maxx[i].second );
            answer[maxx[i].second - 1][maxs[maxx[i].second].back() - 1] = pas;
            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;
            mins[i].pop_back();
        }
    }

    allocate_tickets( answer );
    return dp[n][k * n / 2];
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10