时间限制: 1 Sec 内存限制: 128 MB提交 状态
题目描述
在一个弱智游戏里，有m行n列的怪兽，每个怪兽用一个数值表示它的生命值。小李每次的攻击力都为k。 对于小李的每次攻击，给出三个整数x,y,r，表示对于以点(x−r,y−r)为左上角，点(x+r,y+r)为右下角的矩形范围内的怪兽生命值都减去k。怪兽生命值为0时就死了。请计算经过小李g轮的疯狂攻击，还剩几个怪兽存活。
输入
第一行四个整数，分别表示m,n,k,g。 接下来g行整数，每行三个分别表示对应的x,y,r。 接下来是m行n列的正整数ai,j。
输出
一个整数，表示答案。
样例输入 Copy
6 5 2 1 4 3 2 3 2 1 2 5 1 2 4 1 1 3 3 3 1 2 4 43 1 1 5 5 2 2 2 4 1 1 3 1 5样例输出 Copy
16提示
对于100%的数据，1≤n,m,x,y,r≤1025,1≤k,a≤100,1≤g≤106
999ms卡出来的题
#pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> using namespace std; typedef long long ll; ll a[1050][1050]; ll qz[1050][1050]; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); ll m,n,kk,g; scanf("%lld%lld%lld%lld",&m,&n,&kk,&g); ll x,y,r; for(int i=0;i<g;i++) { scanf("%lld%lld%lld",&x,&y,&r); for(int j=y-r;j<=y+r;j++) { qz[x-r][j]+=kk; qz[x+r+1][j]-=kk; } } for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { qz[i][j]=qz[i][j]+qz[i-1][j]; } } ll ans=0; for(ll i=1;i<=m;i++) { for(ll j=1;j<=n;j++) { scanf("%lld",&a[i][j]); if(a[i][j]>qz[i][j]) { ans++; } } } cout<<ans<<endl; return 0; } /************************************************************** Problem: 11795 User: 2019UPC110 Language: C++ Result: 正确 Time:999 ms Memory:19404 kb ****************************************************************/ #include<iostream> #include<cstdio> #define ll long long using namespace std; ll ans; ll G[1100][1100],sum[1100][1100]; int main() { int n,m,k,g; scanf("%d%d%d%d",&n,&m,&k,&g); for(int i=1;i<=g;i++){ int x,y,r; scanf("%d%d%d",&x,&y,&r); int x1=max(1,x-r); int y1=max(1,y-r); int x2=min(n,x+r); int y2=min(m,y+r); sum[x1][y1]+=k; sum[x2+1][y1]-=k; sum[x1][y2+1]-=k; sum[x2+1][y2+1]+=k; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%lld",&G[i][j]); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; //cout<<sum[i][j]<<' '; if(sum[i][j]<G[i][j])ans++; } //cout<<endl; } cout<<ans; }
