oj.uz

Submission #10090

# Submission time Handle Problem Language Result Execution time Memory
10090 2014-10-12T04:06:42 Z gs14004 고기잡이 (KOI13_fish) C++
15.84 / 18
 4 ms 1284 KB 
#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];
        }
    }
    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.0 / 2.16

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1284 KB Output is correct
2 Incorrect 0 ms 1284 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
2.7 / 2.7

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1284 KB Output is correct
2 Correct 0 ms 1284 KB Output is correct
3 Correct 0 ms 1284 KB Output is correct
4 Correct 0 ms 1284 KB Output is correct

Subtask #3
3.42 / 3.42

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1284 KB Output is correct
2 Correct 0 ms 1284 KB Output is correct
3 Correct 0 ms 1284 KB Output is correct
4 Correct 0 ms 1284 KB Output is correct
5 Correct 0 ms 1284 KB Output is correct

Subtask #4
4.32 / 4.32

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1284 KB Output is correct
2 Correct 0 ms 1284 KB Output is correct
3 Correct 4 ms 1284 KB Output is correct
4 Correct 0 ms 1284 KB Output is correct

Subtask #5
5.4 / 5.4

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1284 KB Output is correct
2 Correct 0 ms 1284 KB Output is correct
3 Correct 4 ms 1284 KB Output is correct
4 Correct 0 ms 1284 KB Output is correct