Submission #10091

#	Time	Username	Problem	Language	Result	Execution time	Memory
10091		gs14004	고기잡이 (KOI13_fish)	C++98	15.84 / 18	4 ms	1284 KiB

fish

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> px,py;
int n,l,m;
int x[101],y[101];
int lx[101], ly[101], sx, sy;
int a[101][101];

int area(int sx, int sy, int ex, int ey){
    int res = a[ex][ey];
    if(sx) res -= a[sx-1][ey];
    if(sy) res -= a[ex][sy-1];
    if(sx && sy) res += a[sx-1][sy-1];
    return res;
}

int length(int sx, int sy, int ex, int ey){
    return lx[ex] - lx[sx] + ly[ey] - ly[sy];
}
int f(int x, int y){
    int res = 0, tx = sx-1;
    for (int i = y+1; i<sy; i++) {
        while (tx > x && length(x,y,tx,i) > l) tx--;
        if(tx == x) break;
        res = max(res,area(x,y,tx,i));
    }
    return res;
}

int main(){
    scanf("%d %d %d",&n,&l,&m);
    for (int i=0; i<m; i++) {
        scanf("%d %d",&x[i],&y[i]);
        px.push_back(x[i]);
        py.push_back(y[i]);
    }
    l >>= 1;
    sort(px.begin(),px.end());
    sort(py.begin(),py.end());
    px.resize(unique(px.begin(),px.end())-px.begin());
    py.resize(unique(py.begin(),py.end())-py.begin());
    sx = (int)px.size();
    sy = (int)py.size();
    for (int i=0; i<m; i++) {
        int tx = (int)(lower_bound(px.begin(),px.end(),x[i])-px.begin());
        int ty = (int)(lower_bound(py.begin(),py.end(),y[i])-py.begin());
        lx[tx] = x[i];
        ly[ty] = y[i];
        x[i] = tx;
        y[i] = ty;
        a[tx][ty]++;
    }
    for (int i=0; i<sx; i++) {
        for (int j=0; j<sy; j++) {
            if(i) a[i][j] += a[i-1][j];
            if(j) a[i][j] += a[i][j-1];
            if(i && j) a[i][j] -= a[i-1][j-1];
        }
    }
    if(sx == 1){
        lx[sx] = lx[sx-1] + 1;
        sx++;
    }
    if(sy == 1){
        ly[sy] = ly[sy-1] + 1;
        sy++;
    }
    int res = 0;
    for (int i=0; i<sx; i++) {
        for (int j=0; j<sy; j++) {
            res = max(res,f(i,j));
        }
    }
    printf("%d",res);
}

• Subtask 1: 0 / 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