Submission #729113

#	Time	Username	Problem	Language	Result	Execution time	Memory
729113		beaconmc	카니발 티켓 (IOI20_tickets)	C++14	27 / 100	558 ms	69096 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[1501][1501];
ll nextt[1501][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(i,0,n){
		minmax.push_back({0,m-1});
	}
	FOR(i,0,755) FOR(j,0,1500) dp[i][j] = -2000000000000000;
	dp[0][0] = 0;

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

	FOR(p, 0, k){

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


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




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

	allocate_tickets(idk);
	

	return ans;



}

• 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