제출 #1072692

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1072692		LCJLY	카니발 티켓 (IOI20_tickets)	C++14	0 / 100	3098 ms	4700 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
//#include "grader.cpp"
using namespace std;
 
#define int long long
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,long long>pii;
typedef pair<long long,pii>pi2;
 
//allocate_tickets(vector<vector<int>>)

vector<pii>maxi;
vector<pii>mini;
int n2;
int memo[1505][3005];
bool visited[1505][3005];
pii pp[1505][3005]; 

int dp(int index, int cur){
	if(index==n2){
		if(cur==0) return 0;
		else return -1e15;
	}
	if(visited[index][cur+n2]){
		return memo[index][cur+n2];
	}
	int ans=-1e15;
	int hold=dp(index+1,cur+1)-mini[index].first;
	if(hold>=ans){
		ans=hold;
		pp[index][cur+n2]={index+1,cur+n2+1};
	}
	hold=dp(index+1,cur-1)+maxi[index].first;
	if(hold>=ans){
		ans=hold;
		pp[index][cur+n2]={index+1,cur+n2-1};
	}
	return memo[index][cur+n2]=ans;
}
 
long long find_maximum(int32_t k, vector<vector<int32_t>>arr){
	int n=arr.size();
	n2=n;
	int m=arr[0].size();
	//k==1
	vector<vector<int32_t>>ans;
	ans.resize(n);
	for(int x=0;x<n;x++){
		ans[x]=vector<int32_t>(m,-1);
		pii hold={-1,-1};
		for(int y=0;y<m;y++){
			hold=max(hold,{arr[x][y],y});
		}
		maxi.push_back(hold);
		hold={1e15,1e15};
		for(int y=0;y<m;y++){
			hold=min(hold,{arr[x][y],y});
		}
		mini.push_back(hold);
	}
	pii cur={0,n2};
	int take=dp(0,0);
	for(int x=0;x<n;x++){
		pii nxt=pp[cur.first][cur.second];
		//cout << nxt.first << " " << nxt.second << endl;
		if(nxt.second>cur.second) ans[x][mini[x].second]=0;
		else ans[x][maxi[x].second]=0;
		cur=nxt;
	}
	allocate_tickets(ans);
	return take;
}

• 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