12323 - Inspecting Radars

gistfile1.cpp

#include <iostream>
using namespace std;

const int MAXA = 360 * 2;
const int MAXH = 105;

int mat[MAXH][MAXA];
int a[MAXA];

int maximo_subarreglo(int ancho) {
    int suma = 0;
    for (int j = 0; j <= ancho; ++j) {
        suma += a[j];
    }
    int ans = suma;
    for (int j = ancho + 1; j < MAXA; ++j) {
        suma -= a[j - ancho - 1];
        suma += a[j];
        ans = max(ans, suma);
    }
    return ans;
}

int main(){
    int N, R;
    while (cin >> N >> R){
        if (N == 0 and R == 0) break;
        
        for (int i = 0; i <= R; ++i){
            for (int j = 0; j < MAXA; ++j) {
                mat[i][j] = 0;
            }
        }
        
        for (int i = 0; i < N; ++i) {
            int r, t;
            cin >> r >> t;
            mat[r][t]++;
            mat[r][t+360]++;
        }
        
        int E;
        cin >> E;
        while (E--){
            int H, T;
            cin >> H >> T;
                
            for (int j = 0; j < MAXA; ++j) {
                a[j] = 0;
            }
            
            for (int i = 0; i <= H - 1; ++i) {
                for (int j = 0; j < MAXA; ++j) {
                    a[j] += mat[i][j];
                }
            }
            
            int ans = maximo_subarreglo(T);
            for (int i = H; i <= R; ++i) {
                for (int j = 0; j < MAXA; ++j){
                    a[j] -= mat[i - H][j];
                    a[j] += mat[i][j];
                }
                ans = max(ans, maximo_subarreglo(T));
            }
            cout << ans << endl;
        }        
    }
    return 0;
}