結果

問題 No.60 魔法少女
ユーザー Tomoya-Murakami2344Tomoya-Murakami2344
提出日時 2022-10-03 16:52:18
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 200 ms / 5,000 ms
コード長 2,939 bytes
コンパイル時間 3,233 ms
コンパイル使用メモリ 162,060 KB
実行使用メモリ 18,068 KB
最終ジャッジ日時 2023-08-27 16:03:47
合計ジャッジ時間 5,708 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 17 ms
11,296 KB
testcase_01 AC 17 ms
11,224 KB
testcase_02 AC 16 ms
11,216 KB
testcase_03 AC 14 ms
11,600 KB
testcase_04 AC 119 ms
16,480 KB
testcase_05 AC 122 ms
16,592 KB
testcase_06 AC 195 ms
17,828 KB
testcase_07 AC 148 ms
16,972 KB
testcase_08 AC 103 ms
16,320 KB
testcase_09 AC 53 ms
15,312 KB
testcase_10 AC 189 ms
18,068 KB
testcase_11 AC 31 ms
12,052 KB
testcase_12 AC 89 ms
15,684 KB
testcase_13 AC 200 ms
18,036 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/all>
#include<iostream>
#include<cmath>
#include<deque>
#include <string>
#include <map>
#include <unordered_map>
#include <vector>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <set>
#include<atcoder/modint>
using namespace std;
using ll=long long;
using namespace atcoder;
using mint = modint998244353;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, n) for (int i = 1; i <= (int)(n); i++)

using namespace std;

using Graph = vector<vector<int> >;
//vector<bool> seen;
//seen.assign(n,a)
//map<pair<int,int>,int> seen;
//vector<int> e[200002];
//bool flag[200002];
//deque<int> deq;
//bool stop;
//char field[501][501];
//int ans;


/*
void original_dfs(Graph &G,int v){
    seen[v] = true;

    for(auto e:G[v]){
        if(seen[e]==true) continue;
        else{
            dfs(G,e);
        }
    }
}*/

int dx[4] = {-1,0,0,+1};
int dy[4] = {0,-1,+1,0};

//int len[100001][100001];
map<pair<int,int> ,int> mp; //kaitsu or not
ll ans;
Graph g;

/*
void dfs3(vector<vector<int> > &v,int x,int color){
    seen[x] = color;
    int s = v[x].size();
    for(int i=0;i<s;i++){
        int tmp = v[x][i];
        if(seen[tmp]==1 || seen[tmp]==-1) continue;

        int a = mp[{x,tmp}];
        if(a%2==0) dfs3(v,tmp,color);
        else dfs3(v,tmp,-color);
    }
}*/

//int seen[200001];
//vector<vector<int> > vv(200001);
vector<ll> sum;
/*
void dfs(Graph &v,int x){
    seen[x] = 1;

    //for(int i=0;i<v[x].size();i++){
    for(auto e:v[x]){
        if(seen[e]==1) continue;
        else{
            sum[e] += sum[x];
            dfs(v,e);
            //vv[x].insert(vv[x].end(),vv[e].begin(),vv[e].end());
        }
    }
}*/

void era(vector<int> &v){
    for(int i=2;i<=100000;i++){
        if(v[i]==0) continue;
        else{
            int tmp = 100000/i;
            for(int j=i;j<=tmp;j++){
                v[i*j] = 0; 
            }
        }
    }
}

vector<int> seen;

int gg,l;
int field[2001][2001];

int main(){
    int n,k;cin >> n >> k;
    vector<int> x(n);
    vector<int> y(n);
    vector<int> hp(n);
    int tmp;
    rep(i,n){
        cin >> tmp;x[i] = tmp+500;
        cin >> tmp;y[i] = tmp+500;
        cin >> hp[i];
    }
    vector<int> ax(k);
    vector<int> ay(k);
    vector<int> w(k);
    vector<int> h(k);
    vector<int> d(k);
    rep(i,k){
        cin >> tmp; ax[i] = tmp+500;
        cin >> tmp; ay[i] = tmp+500;
        cin >>w[i]>>h[i]>>d[i];

        field[ax[i]][ay[i]]+=d[i];
        field[ax[i]+w[i]+1][ay[i]]-=d[i];
        field[ax[i]][ay[i]+h[i]+1]-=d[i];
        field[ax[i]+w[i]+1][ay[i]+h[i]+1]+=d[i];
    }
    rep(i,1001){
        rep2(j,1000){
            field[i][j] += field[i][j-1];
        }
    }
    rep(i,1001){
        rep2(j,1000){
            field[j][i] += field[j-1][i];
        }
    }
    int ans=0;
    //int tmp=0;
    rep(i,n){
        ans += max(0,hp[i] - field[x[i]][y[i]]);
    }
    cout << ans << endl;
}
0