Submission #1156684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156684		_rain_	Garden (JOI23_garden)	C++20	30 / 100	3093 ms	8228 KiB

garden

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=(int)500000;
const LL INF=(LL)1e18;
int p[N+2][2],r[N+2][2];
int n,m,d;

namespace problem1{
	bool check(){
		return n+m<=5000;
	}	
	
	LL form_swap(int x,int a,int y){
		if (a>y) return -1;
		if (a<x && a+d>y) return -1;
		if (x<=a && a<=y) return a;
		return a+d;
	}

		
	LL Cost(int x,int y){
		vector<int>v;
		for(int i=1;i<=n;++i){
			if (form_swap(x,p[i][0],y)==-1) return INF;
			v.push_back(r[i][0]);
//			cout<<form_swap(x,p[i][0],y)<<' '<<x<<' '<<y<<'\n';
		}
		for(int i=1;i<=m;++i){
			if (form_swap(x,p[i][1],y)==-1) v.push_back(r[i][1]);
		}
		sort(v.begin(),v.end()); v.resize(unique(v.begin(),v.end())-v.begin());
		int height=y-x+1;
		int weight=v.back()-v.front()+1;
		v.push_back(v[0]);
		for(int i=1;i<v.size()-1;++i){
			weight=min(weight,v[i-1]+d-v[i]+1);
		}
		return (LL)height*weight;
	}
	
	void main_code(){
		LL ans=INF;
		for(int x=0;x<=d;++x){
			for(int y=x;y<=2*d;++y){
				ans=min(ans,Cost(x,y));
			}
		}
		cout<<ans<<'\n';
	}
}


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
//	freopen("txt.inp","r",stdin);
//	freopen("txt.out","w",stdout);
	
	cin>>n>>m>>d;
	for(int i=1;i<=n;++i) cin>>p[i][0]>>r[i][0];
	for(int i=1;i<=m;++i) cin>>p[i][1]>>r[i][1];
	if (problem1::check()) return problem1::main_code(),0;
}

• Subtask 1: 0 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25