제출 #728673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
728673		beaconmc	Carnival Tickets (IOI20_tickets)	C++14	0 / 100	6 ms	10196 KiB

tickets

#include "tickets.h"

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

ll dp[755][1501];
ll nextt[755][1501];

long long find_maximum(int k, vector<vector<int>> x) {
	ll n = x.size();
	ll m = x[0].size();
	
	vector<vector<int>> idk;
	vector<vector<ll>> minmax;
	for (auto&i : x){
		ll a = max_element(i.begin(), i.end()) - i.begin();
		ll b = min_element(i.begin(), i.end()) - i.begin();
		minmax.push_back({a,b});
	}
	FOR(i,0,755) FOR(j,0,1500) dp[i][j] = -2000000000000000;
	dp[0][0] = 0;



	FOR(i,0,n/2){
		FOR(j,0,n){

			if (dp[i][j] + x[j][minmax[j][0]] > dp[i+1][j+1] ){
				dp[i+1][j+1] = dp[i][j] + x[j][minmax[j][0]];
				nextt[i+1][j+1] = -1;
			}
			if (dp[i][j] - x[j][minmax[j][1]] > dp[i][j+1]){
				dp[i][j+1] = dp[i][j] - x[j][minmax[j][1]];
				nextt[i][j+1] = 0;
			}
		}
	}


	FOR(i,0,n){
		vector<int> temp;
		FOR(j,0,m){
			temp.push_back(-1);
		}
		idk.push_back(temp);
	}

	ll hal = n/2;
	ll cur = n;
	while (cur != 0){
		ll sus = nextt[hal][cur];
		if (sus==-1){
			idk[cur-1][minmax[cur-1][0]] = 0;
		}else{
			idk[cur-1][minmax[cur-1][1]] = 0;
		}
		hal += sus;
		cur -= 1;
	}

	allocate_tickets(idk);
	

	return dp[n/2][n];



}

• 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