Submission #831445

#	Time	Username	Problem	Language	Result	Execution time	Memory
831445		Dremix10	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	461 ms	81892 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
const int N = 3e5+5;
const int MOD = 1e9+7;
const ll INF = 1e18+5;
#ifdef dremix
    #define p2(x,y) cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<endl;
    #define ppv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v.F<<"-"<<v.S<<", ";cerr<<"}"<<endl;
#else
    #define p2(x,y) {}
    #define ppv(x) {}
#endif



long long find_maximum(int k, vector<vector<int> > x) {
	int n = x.size();
	int m = x[0].size();
	
    vector<pi> arr;
    int i,j;
    pi idx[n];

	for (i = 0; i < n; i++) {
		int mini = MOD,maxi = -MOD;
        for(j=0;j<m;j++){
            if(x[i][j] < mini){
                mini = x[i][j];
                idx[i].F = j;
            }
            if(x[i][j] > maxi){
                maxi = x[i][j];
                idx[i].S = j;
            }
        }
        arr.push_back({mini,maxi});
	}
    //sort(all(arr));

    vector<vector<ll> > dp(n+1,vector<ll>(n/2+1,-INF));
    /// dp[i][j] , at color i, took j minimums up to now
    dp[0][0] = 0;

    for(i=1;i<=n;i++){
        /// take maximum only
        dp[i][0] = dp[i-1][0] + arr[i-1].S;

        for(j=1;j<=n/2;j++){
            dp[i][j] = max(dp[i][j],dp[i-1][j] + arr[i-1].S);
            dp[i][j] = max(dp[i][j],dp[i-1][j-1] - arr[i-1].F);
        }
    }

    vector<vector<int> > answer(n,vector<int>(m,-1));
    ll sum = dp[n][n/2];

    i = n;
    j = n/2;

    while(i > 0){
        if(dp[i][j] - arr[i-1].S == dp[i-1][j]){
            answer[i-1][idx[i-1].S] = 0;
            i--;
        }
        else{
            assert(dp[i][j] + arr[i-1].F == dp[i-1][j-1]);
            answer[i-1][idx[i-1].F] = 0;
            i--;
            j--;
        }
    }
    
	allocate_tickets(answer);
	return sum;
}

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