Submission #793188

#	Time	Username	Problem	Language	Result	Execution time	Memory
793188		Dan4Life	IOI Fever (JOI21_fever)	C++17	37 / 100	1056 ms	25116 KiB

fever

#include <bits/stdc++.h>
using namespace std;
using ar = array<int,3>;
const int mxN = (int)3e3+10;
const int X[] = {-1,1,0,0};
const int Y[] = {0,0,-1,1};
int n, d[mxN], x[mxN], y[mxN], sick[mxN];
priority_queue<ar,vector<ar>,greater<ar>> pq;

int main(){
	cin >> n; sick[0]=1; int ans = 1;
	for(int i = 0; i < n; i++)
		cin >> x[i] >> y[i];
	for(int i = n-1; i >= 0; i--)
		x[i]-=x[0], y[i]-=y[0];
	for(int t = 0; t < 4; t++){
		fill(sick+1,sick+n,0);
		for(int i = 0; i < n; i++){
			if(abs(x[i])==abs(y[i])) d[i]=(x[i]>=0?0:y[i]<0?3:2);
			else if(abs(x[i])>abs(y[i])) d[i]=(x[i]>0?0:1);
			else d[i]=(y[i]>0?2:3);
        }
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(d[i]/2==0 and d[j]/2==1){
					int t1=(x[j]-x[i])/X[d[i]];
					int t2=(y[i]-y[j])/Y[d[j]];
					if(t1==t2) pq.push({2*t1,i,j});
				}
				if(d[i]==1 and d[j]==0)
					if(y[i]==y[j] and x[i]<x[j])
						pq.push({x[j]-x[i],i,j});
				if(d[i]==3 and d[j]==2)
					if(x[i]==x[j] and y[i]<y[j])
						pq.push({y[j]-y[i],i,j});
			}
		}
		while(!empty(pq)){
			auto [t,i,j] = pq.top(); pq.pop();
			sick[i]=sick[j]=sick[i]|sick[j]; 
		}
		ans = max(ans, accumulate(sick,sick+n,0));
		for(int i = 0; i < n; i++)swap(x[i],y[i]),x[i]*=-1;
	}
	cout << ans << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31