結果

問題 No.60 魔法少女
コンテスト
ユーザー hamray
提出日時 2021-05-22 17:45:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 91 ms / 5,000 ms
コード長 1,404 bytes
コンパイル時間 792 ms
コンパイル使用メモリ 77,264 KB
実行使用メモリ 13,312 KB
最終ジャッジ日時 2024-10-10 16:01:29
合計ジャッジ時間 2,518 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define PROBLEM "https://yukicoder.me/problems/no/60"
#include <iostream>
#include <cassert>
#include <vector>
template<typename T>
struct imos2D{
  int H, W;
  std::vector<std::vector<T>> data;
 
  imos2D(int h, int w): H(h), W(w){
    data.resize(H+10, std::vector<T>(W+10));
  }
 
  // [y0, y1) * [x0, x1)
  void add(int y0, int x0, int y1, int x1, T x) {
    data[y0][x0] += x;
    data[y1][x1] += x;
    data[y0][x1] -= x;
    data[y1][x0] -= x;
  } 
 
  void build() {
    for(int i=0; i<H; i++) {
      for(int j=0; j<W-1; j++) {
        data[i][j+1] += data[i][j];
      }
    }
    for(int j=0; j<W; j++) {
      for(int i=0; i<H-1; i++) {
        data[i+1][j] += data[i][j];
      }
    }
  }
 
  inline T operator()(int i, int j) { 
    assert(i <= H && j <= W);
    return data[i][j]; 
  }
};

int main(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int N, K; 
  std::cin >> N >> K;
  std::vector<int> x(N), y(N), hp(N);
  for(int i=0; i<N; i++) {
    std::cin >> x[i] >> y[i] >> hp[i];
    x[i] += 500;
    y[i] += 500;
  }
  imos2D<int> grid(1500, 1500);
  for(int i=0; i<K; i++) {
    int ax, ay, w, h, d;
    std::cin >> ax >> ay >> w >> h >> d;
    ax += 500; ay += 500;
    grid.add(ay, ax, ay+h+1, ax+w+1, d);
  }
  grid.build();
  int ans = 0;
  for(int i=0; i<N; i++) {
    ans += std::max(0, hp[i]-grid(y[i],x[i]));
  }
  std::cout << ans << '\n';
  return 0;
}
0