제출 #1279094

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279094		PieArmy	The Kingdom of JOIOI (JOI17_joioi)	C++20	60 / 100	4014 ms	209788 KiB

joioi

#include<bits/stdc++.h>
typedef long long ll;
#define fr first
#define sc second
#define endl '\n'
using namespace std;

int n,m,k;
ll arr[2023][2023];
int id[2023][2023][4];
pair<int,int>art[4]={{1,1},{1,-1},{-1,-1},{-1,1}};
int app[4000023][4];
int p[4];
ll mx[4];
pair<short,short>per[4][4000023];

int main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>arr[i][j];
			for(int l=0;l<4;l++){
				per[l][k]={i,j};
			}
			k++;
		}
	}
	for(int i=0;i<=n+1;i++){
		for(int j=0;j<=m+1;j++){
			for(int l=0;l<4;l++){
				id[i][j][l]=-1;
			}
		}
	}
	for(int i=0;i<4;i++){
		p[i]=k-1;
		sort(per[i],per[i]+k,[&](const pair<int,int> &x,const pair<int,int> &y){
			if(arr[x.fr][x.sc]==arr[y.fr][y.sc]){
				if(x.fr==y.fr){
					return x.sc*art[i].sc>y.sc*art[i].sc;
				}
				return x.fr*art[i].fr>y.fr*art[i].fr;
			}
			return arr[x.fr][x.sc]<arr[y.fr][y.sc];
		});
	}
	for(int j=0;j<4;j++){
		for(int i=0;i<k;i++){
			id[per[j][i].fr][per[j][i].sc][j]=i;
		}
	}
	ll ans=arr[per[0][k-1].fr][per[0][k-1].sc]*4ll;
	for(int i=0;i<k-1;i++){
		for(int j=0;j<4;j++){
			if(mx[j]==-1)continue;
			int a=per[j][i].fr,b=per[j][i].sc;
			if((a-art[j].fr==0||a-art[j].fr==n+1)&&(b-art[j].sc==0||b-art[j].sc==m+1)){
				mx[j]=-1;
				continue;
			}
			ll resa=-arr[per[j][0].fr][per[j][0].sc];
			ll resb=-arr[per[j][i+1].fr][per[j][i+1].sc];

			for(int l=a;id[l][b][j]>=0;l+=art[j].fr){
				for(int r=b;id[l][r][j]>=0;r+=art[j].sc){
					app[id[l][r][j]][j]=1;
					id[l][r][j]=-1;
					mx[j]=max(mx[j],arr[l][r]);
				}
			}
			while(app[p[j]][j]){
				p[j]--;
			}
			if(p[j]==k-1){
				resb+=arr[per[j][k-1].fr][per[j][k-1].sc];
				resa+=mx[j];
			}
			else{
				resa+=arr[per[j][k-1].fr][per[j][k-1].sc];
				resb+=arr[per[j][p[j]].fr][per[j][p[j]].sc];
			}
			ans=min(ans,max(resa,resb));
		}
	}
	cout<<ans<<endl;
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 0 / 40