#997771 (C++14) No.2826 Earthwork

提出ソース

結果

問題	No.2826 Earthwork
ユーザー	👑 hos.lyric
提出日時	2024-07-26 22:25:41
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	5,930 bytes
コンパイル時間	1,271 ms
コンパイル使用メモリ	118,448 KB
実行使用メモリ	173,804 KB
最終ジャッジ日時	2024-07-26 22:25:54
合計ジャッジ時間	11,878 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 14,824 KB
testcase_01	AC	1,502 ms 12,320 KB
testcase_02	TLE	-
testcase_03	--	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

// using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


#ifndef LIBRA_OTHER_INT128_H_
#define LIBRA_OTHER_INT128_H_

#include <stdio.h>
#include <iostream>

constexpr unsigned __int128 toUInt128(const char *s) {
  unsigned __int128 x = 0;
  for (; *s; ++s) x = x * 10 + (*s - '0');
  return x;
}
constexpr __int128 toInt128(const char *s) {
  if (*s == '-') return -toInt128(s + 1);
  __int128 x = 0;
  for (; *s; ++s) x = x * 10 + (*s - '0');
  return x;
}
unsigned __int128 inUInt128() {
  static char buf[41];
  scanf("%s", buf);
  return toUInt128(buf);
}
__int128 inInt128() {
  static char buf[41];
  scanf("%s", buf);
  return toInt128(buf);
}

void out(unsigned __int128 x) {
  static char buf[41];
  int len = 0;
  do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10);
  for (int i = len; --i >= 0; ) putchar(buf[i]);
}
void out(__int128 x) {
  if (x < 0) {
    putchar('-');
    out(-static_cast<unsigned __int128>(x));
  } else {
    out(static_cast<unsigned __int128>(x));
  }
}
std::ostream &operator<<(std::ostream &os, unsigned __int128 x) {
  static char buf[41];
  int len = 0;
  do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10);
  for (int i = len; --i >= 0; ) os << buf[i];
  return os;
}
std::ostream &operator<<(std::ostream &os, __int128 x) {
  if (x < 0) {
    os << '-' << -static_cast<unsigned __int128>(x);
  } else {
    os << static_cast<unsigned __int128>(x);
  }
  return os;
}

#endif  // LIBRA_OTHER_INT128_H_


using INT = __int128;
constexpr INT INF = toInt128("1002003004005006007006005004003002001");

#define abs my_abs
INT abs(INT x) {
  return (x < 0) ? -x : x;
}

#define MAX [810][810]

int N;
INT H MAX;
char C MAX;
INT A MAX, B MAX;

int id(int x, int y) {
  return x * N + y;
}

vector<pair<pair<int, int>, INT>> es;
void ae(int u, int v, INT c) {
// cerr<<"[ae] "<<u<<" "<<v<<" "<<c<<endl;
  es.emplace_back(make_pair(u, v), c);
}

int main() {
  for (; ~scanf("%d", &N); ) {
    for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) H[x][y] = inInt128();
    for (int x = 0; x < N; ++x) scanf("%s", C[x]);
    for (int x = 0; x < N - 1; ++x) for (int y = 0; y < N; ++y) A[x][y] = inInt128();
    for (int x = 0; x < N; ++x) for (int y = 0; y < N - 1; ++y) B[x][y] = inInt128();
    
    const int U = N * N + 1;
    const int S = N * N;
    es.clear();
    for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) {
      if (C[x][y] == '-' || C[x][y] == '=') {
        // h[x][y] <= H[x][y]
        if ((x + y) & 1) {
          ae(id(x, y), S, +H[x][y]);
        } else {
          ae(S, id(x, y), +H[x][y]);
        }
      }
      if (C[x][y] == '+' || C[x][y] == '=') {
        // h[x][y] >= H[x][y]
        if ((x + y) & 1) {
          ae(S, id(x, y), -H[x][y]);
        } else {
          ae(id(x, y), S, -H[x][y]);
        }
      }
    }
    for (int x = 0; x < N - 1; ++x) for (int y = 0; y < N; ++y) {
      // -lim <= h[x][y] - (-h[x+1][y]) <= +lim
      // -lim <= h[x+1][y] - (-h[x][y]) <= +lim
      const INT lim = A[x][y] * abs(H[x][y] + H[x+1][y]);
      ae(id(x, y), id(x+1, y), lim);
      ae(id(x+1, y), id(x, y), lim);
    }
    for (int x = 0; x < N; ++x) for (int y = 0; y < N - 1; ++y) {
      const INT lim = B[x][y] * abs(H[x][y] + H[x][y+1]);
      ae(id(x, y), id(x, y+1), lim);
      ae(id(x, y+1), id(x, y), lim);
    }
    
    // TODO
    vector<INT> dist(U, INF), tsid(U, INF);
    dist[S] = 0;
    tsid[S] = 0;
    for (int h = 1; h <= U; ++h) {
      for (const auto &e : es) {
        const int u = e.first.first;
        const int v = e.first.second;
        const INT c = e.second;
        chmin(dist[v], dist[u] + c);
        chmin(tsid[u], c + tsid[v]);
      }
    }
/*
for(int x=0;x<N;++x)pv(dist.begin()+id(x,0),dist.begin()+id(x+1,0));cerr<<dist[S]<<endl;
for(int x=0;x<N;++x)pv(tsid.begin()+id(x,0),tsid.begin()+id(x+1,0));cerr<<tsid[S]<<endl;
vector<vector<INT>>d(U,vector<INT>(U,INF));
for(int u=0;u<U;++u)d[u][u]=0;
for(const auto&e:es)chmin(d[e.first.first][e.first.second],e.second);
for(int w=0;w<U;++w)for(int u=0;u<U;++u)for(int v=0;v<U;++v)chmin(d[u][v],d[u][w]+d[w][v]);
for(int u=0;u<U;++u)assert(d[S][u]==dist[u]);
for(int u=0;u<U;++u)assert(d[u][S]==tsid[u]);
*/
    
    int Q;
    scanf("%d", &Q);
    for (; Q--; ) {
      int X, Y;
      scanf("%d%d", &X, &Y);
      --X;
      --Y;
      const INT E = inInt128();
// cerr<<COLOR("33")<<X<<" "<<Y<<" "<<E<<": "<<dist[id(X,Y)]<<" "<<tsid[id(X,Y)]<<COLOR()<<endl;
      
      // h[X][Y] >= E
      bool ans;
      if ((X + Y) & 1) {
        // ae(S, id(X, Y), -E);
        ans = (-E + tsid[id(X, Y)] >= 0);
      } else {
        // ae(id(X, Y), S, -E);
        ans = (-E + dist[id(X, Y)] >= 0);
      }
      puts(ans ? "Yes" : "No");
    }
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード