結果

問題 No.60 魔法少女
ユーザー tottoripapertottoripaper
提出日時 2014-11-09 23:43:43
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 232 ms / 5,000 ms
コード長 1,551 bytes
コンパイル時間 1,968 ms
コンパイル使用メモリ 73,052 KB
実行使用メモリ 36,376 KB
最終ジャッジ日時 2023-08-30 02:51:26
合計ジャッジ時間 3,617 ms
ジャッジサーバーID
(参考情報)
judge15 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 54 ms
36,236 KB
testcase_01 AC 54 ms
36,084 KB
testcase_02 AC 55 ms
36,108 KB
testcase_03 AC 54 ms
36,124 KB
testcase_04 AC 149 ms
36,128 KB
testcase_05 AC 156 ms
36,376 KB
testcase_06 AC 226 ms
36,180 KB
testcase_07 AC 179 ms
36,176 KB
testcase_08 AC 133 ms
36,120 KB
testcase_09 AC 88 ms
36,184 KB
testcase_10 AC 215 ms
36,200 KB
testcase_11 AC 70 ms
36,276 KB
testcase_12 AC 124 ms
36,164 KB
testcase_13 AC 232 ms
36,292 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> P;
typedef std::pair<int,P> State;

const int INF = 1001001001;

// S N E W(南北東西)
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

int N, K;
int enemyX[100000], enemyY[100000];
ll enemyH[100000];
ll map[2002][2002];

P adjust(const int &x, const int &y){
    return mp(x + 1000, y + 1000);
}

int main(){
    std::cin >> N >> K;

    REP(i, N){
        std::cin >> enemyX[i] >> enemyY[i] >> enemyH[i];
    }

    REP(i, K){
        int x, y, w, h, d;
        std::cin >> x >> y >> w >> h >> d;

        P p = adjust(x, y), q = adjust(x+w, y+h);
        map[p.first][p.second] += d;
        map[p.first][q.second+1] -= d;
        map[q.first+1][p.second] -= d;
        map[q.first+1][q.second+1] += d;
    }

    REP(i, 2002){
        FOR(j, 1, 2002){
            map[j][i] += map[j-1][i];
        }
    }

    REP(i, 2002){
        FOR(j, 1, 2002){
            map[i][j] += map[i][j-1];
        }
    }

    ll res = 0ll;
    REP(i, N){
        P p = adjust(enemyX[i], enemyY[i]);
        res += std::max(1ll * enemyH[i] - map[p.first][p.second], 0ll);
    }

    std::cout << res << std::endl;
}
0