Submission #1169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169		kriii	고기잡이 (KOI13_fish)	C++98	18 / 18	6 ms	1188 KiB

fish

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> X[10010];
int N,L,M,C[10010],Y[101],A;

int main()
{
	int i,j,k,x,y,s;

	scanf ("%d %d %d",&N,&L,&M); L /= 2;
	for (i=0;i<M;i++){
		scanf ("%d %d",&x,&y);
		X[x].push_back(y);
		Y[i] = y;
	}
	sort(Y,Y+M); M = unique(Y,Y+M) - Y;

	for (x=1;x<L;x++){
		y = L - x;

		for (i=1;i<=N;i++) C[i] = 0;
		for (i=1;i<=N;i++){
			for (j=0;j<X[i].size();j++) C[X[i][j]]++;
			if (i - x > 1) for (j=0;j<X[i-x-1].size();j++) C[X[i-x-1][j]]--;

			if (!X[i].empty() || !X[i-x].empty()){
				s = 0;
				for (j=k=0;k<M;k++){
					s += C[Y[k]];
					while (Y[k] - Y[j] > y){
						s -= C[Y[j]]; j++;
					}
					if (A < s)
						A = s;
				}
			}
		}
	}

	printf ("%d",A);

	return 0;
}

• Subtask 1: 2.16 / 2.16
• Subtask 2: 2.7 / 2.7
• Subtask 3: 3.42 / 3.42
• Subtask 4: 4.32 / 4.32
• Subtask 5: 5.4 / 5.4