Submission #1279103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279103		PieArmy	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	3115 ms	110920 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];
pair<int,int>art[4]={{1,1},{1,-1},{-1,-1},{-1,1}};
int app[4000023];
int p,mx;
pair<short,short>per[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];
			mx=max(mx,arr[i][j]);
			per[k]={i,j};
			k++;
		}
	}
	for(int l=0;l<=n+1;l++){
		for(int r=0;r<=m+1;r++){
			id[l][r]=-1;
		}
	}
	ll ans=mx*4ll;
	for(int j=0;j<4;j++){
		p=k-1;
		mx=0;
		sort(per,per+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[j].sc>y.sc*art[j].sc;
				}
				return x.fr*art[j].fr>y.fr*art[j].fr;
			}
			return arr[x.fr][x.sc]<arr[y.fr][y.sc];
		});
		for(int i=0;i<k;i++){
			id[per[i].fr][per[i].sc]=i;
			app[i]=0;
		}
		for(int i=0;i<k-1;i++){
			int a=per[i].fr,b=per[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)){
				break;
			}
			ll resa=-arr[per[0].fr][per[0].sc];
			ll resb=-arr[per[i+1].fr][per[i+1].sc];

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

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