結果

問題 No.1490 スライムと爆弾
ユーザー ytft
提出日時 2021-08-11 09:53:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,774 bytes
コンパイル時間 1,706 ms
コンパイル使用メモリ 176,024 KB
実行使用メモリ 22,528 KB
最終ジャッジ日時 2024-09-24 18:45:59
合計ジャッジ時間 6,044 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;



int main(){
    int H,W,N,M;
    cin>>H>>W>>N>>M;
    vector<int> T(N),U(N),L(N),R(N),A(N);
    vector<int> X(M),Y(M),B(M),C(M);
    for(int i=0;i<N;i++){
        cin>>T[i]>>U[i]>>L[i]>>R[i]>>A[i];
        T[i]--;
        U[i]--;
        L[i]--;
        R[i]--;
    }
    for(int i=0;i<M;i++){
        cin>>X[i]>>Y[i]>>B[i]>>C[i];
        X[i]--;
        Y[i]--;
    }   
    vector<vector<int>> imp(H,vector<int>(W,0));
    for(int i=0;i<M;i++){
        imp[max(0,X[i]-B[i])][max(0,Y[i]-B[i])]+=C[i];
        if(X[i]+B[i]+1<H){
            imp[X[i]+B[i]+1][max(0,Y[i]-B[i])]-=C[i];
        }
        if(Y[i]+B[i]+1<W){
            imp[max(0,X[i]-B[i])][Y[i]+B[i]+1]-=C[i];
        }
        if(X[i]+B[i]+1<H && Y[i]+B[i]+1<W){
            imp[X[i]+B[i]+1][Y[i]+B[i]+1]+=C[i];
        }
    }
    for(int i=1;i<H;i++){
        imp[i][0]+=imp[i-1][0];
    }
    for(int i=1;i<W;i++){
        imp[0][i]+=imp[0][i-1];
    }
    for(int i=1;i<H;i++){
        for(int j=1;j<W;j++){
            imp[i][j]+=imp[i][j-1]+imp[i-1][j]-imp[i-1][j-1];
        }
    }
    for(int i=H-2;i>=0;i--){
        imp[i][W-1]+=imp[i+1][W-1];
    }
    for(int i=W-2;i>=0;i--){
        imp[H-1][i]+=imp[H-1][i+1];
    }
    for(int i=H-2;i>=0;i--){
        for(int j=W-2;j>=0;j--){
            imp[i][j]+=imp[i][j+1]+imp[i+1][j]-imp[i+1][j+1];
        }
    }  
    int ans=0;
    for(int i=0;i<N;i++){
        int damage=imp[T[i]][L[i]];
        if(R[i]+1<W){
            damage-=imp[T[i]][R[i]+1];
        }
        if(U[i]+1<H){
            damage-=imp[U[i]+1][L[i]];
        }
        if(U[i]+1<H && R[i]+1<W){
            damage+=imp[U[i]+1][R[i]+1];
        }
        if(damage<A[i]){
            ++ans;
        }
    }
    cout<<ans<<endl;
}
0