Submission #1279080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279080		PieArmy	The Kingdom of JOIOI (JOI17_joioi)	C++20	15 / 100	24 ms	7612 KiB

joioi

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
#define int ll

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

int32_t 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++){
				dp[i][j][l]=1;
				per[l][k]={i,j};
			}
			k++;
		}
	}
	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;
		}
	}
	int ans=arr[per[0][k-1].fr][per[0][k-1].sc]*4;
	for(int i=0;i<k-1;i++){
		for(int j=0;j<4;j++){
			int resa=-arr[per[j][0].fr][per[j][0].sc];
			int resb=-arr[per[j][i+1].fr][per[j][i+1].sc];

			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==n+1)){
				mx[j]=-1;
			}
			if(mx[j]==-1)continue;
			for(int l=a;dp[l][b][j];l+=art[j].fr){
				for(int r=b;dp[l][r][j];r+=art[j].sc){
					dp[l][r][j]=0;
					app[id[l][r][j]][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: 0 / 45
• Subtask 3: 0 / 40