#pragma warning(disable:4996) #include using namespace std; #if __has_include() #include using namespace atcoder; using mint = static_modint<998244353>; using vmint = vector; using vvmint = vector; using vvvmint = vector; using vvvvmint = vector; istream& operator>>(istream& is, mint& a) { long long v; is >> v; a = v; return is; } ostream& operator<<(ostream& os, mint a) { return os << a.val(); } #endif #ifdef _MSC_VER #include #define __builtin_popcount __popcnt #define __builtin_popcountll __popcnt64 #endif template using vec = vector; using ll = long long; using ull = unsigned long long; using stirng = string; using itn = int; using vs = vec; using vc = vec; using vvc = vec; using vvvc = vec; using vi = vec; using vvi = vec; using vvvi = vec; using vvvvi = vec; using vll = vec; using vvll = vec; using vvvll = vec; using vvvvll = vec; using si = set; using vsi = vec; using vvsi = vec; using vvvsi = vec; using sll = set; using vsll = vec; using vvsll = vec; using vvvsll = vec; using vd = vec; using vvd = vec; using vvvd = vec; using vvvvd = vec; using pii = pair; using pll = pair; using pdd = pair; using mii = map; using mll = map; using msi = multiset; using msll = multiset; using vpii = vec; using vvpii = vec; using vvvpii = vec; using vpll = vec; using vvpll = vec; using vvvpll = vec; using vpdd = vec; using spii = set; using spll = set; using spdd = set; using vspll = vec; using vvspll = vec; using vb = vec; using vvb = vec; using vvvb = vec; #define rep(i,j,n) for(ll i=j;i<(n);i++) #define rrep(i,j,n) for (ll i = (n)-1; i >=j; i--) #define Call_4th(_1, _2, _3, _4, ...) _4 #define rp(...) Call_4th(__VA_ARGS__, _1, rp2)(__VA_ARGS__) #define rp2(i, n) rep(i, 0, n) #define rrp(i,n) rrep(i,0,(n)) #define all(v) v.begin(), v.end() #define pb push_back #define ins insert #define yes cout<<"Yes"< int len(T& x) { return int(x.size()); } #define sz size() #define fi first #define se second #define nxp next_permutation ll mod0 = 998244353, lmax = 4e18, inf = 1050000000; double pi = 3.141592653589793238462643; //cin系統 template void in(T&... X) { (cin >> ... >> X); } template void ain(vec& Y) { rp(K, Y.size()) cin >> Y[K]; } template void ain(set& Y, auto n) { rp(i, n) { T YY; cin >> YY; Y.insert(YY); } } template void ain(multiset& Y, auto n) { rp(i, n) { T YY; cin >> YY; Y.insert(YY); } } template void ain(pair& a) { cin >> a.fi >> a.se; } template void bin(vec& Z) { rp(L, Z.size()) ain(Z[L]); } //cout系統 // vector template struct is_vector : false_type {}; template struct is_vector> : true_type {}; // queue template struct is_queue : false_type {}; template struct is_queue> : true_type {}; // stack template struct is_stack : false_type {}; template struct is_stack> : true_type {}; // pair template struct is_pair : false_type {}; template struct is_pair> : true_type {}; // set / multiset template struct is_set_like : false_type {}; template struct is_set_like> : true_type {}; template struct is_set_like> : true_type {}; // map / multimap template struct is_map_like : false_type {}; template struct is_map_like> : true_type {}; template struct is_map_like> : true_type {}; template void aout(const T& x) { if constexpr (is_vector::value) { for (const auto& e : x) aout(e); cout << endl; } else if constexpr (is_queue::value) { auto copy = x; while (!copy.empty()) { aout(copy.front()); copy.pop(); } cout << endl; } else if constexpr (is_stack::value) { auto copy = x; while (!copy.empty()) { aout(copy.top()); copy.pop(); } cout << endl; } else if constexpr (is_pair::value) { aout(x.first); aout(x.second); cout << endl; } else if constexpr (is_set_like::value) { for (const auto& e : x) aout(e); cout << endl; } else if constexpr (is_map_like::value) { for (const auto& e : x) aout(e); // pair cout << endl; } else { cout << x << " "; } } //数学系 ll modcnt(ll l, ll r, ll m, ll a) {//l以上r以下の整数iでi≡a(mod m)となるものの個数(l>r,a<0等も可) assert(m != 0); m = abs(m); ll x = l + ((a - l) % m + m) % m;//l以上で最小のi≡a(mod m)となるi if (x > r) return 0; return (r - x) / m + 1; } ll dsum(ll a) {//桁和 ll r = 0; while (a != 0) { r += a % 10; a /= 10; } return r; } ll dnum(ll a) {//桁数(0は0桁) ll r = 0; while (a != 0) { r++; a /= 10; } return r; } sll yk(ll n) {//約数全列挙O(sqrt(N)),set sll yaku; for (ll i = 1; i * i <= n; i++) if (n % i == 0) { yaku.insert(i); yaku.insert(n / i); } return yaku; } vi ssa(int n) {//n:必要な素数の最大値 素数全列挙 線形篩 vector prime; vectorlpf(n + 1, 0);//最小素因数 rep(i, 2, n + 1) { if (lpf[i] == 0) { lpf[i] = i; prime.push_back(i); } for (int k : prime) { if (k * i > n || k > lpf[i]) break;//k最小素因数よりk<=i lpf[k * i] = k;//kを最小素因数に持つ数k*iを拾う } } return prime; } vector sib(ll x) {//素因数分解 //if (x == 1) return vector(1, { 1,1 }); vector ans; for (ll i = 2; i * i <= x; i++) {//rootx回iを回しxで割る ll kaisu = 0; while (x % i == 0) { x /= i; kaisu++; } if (kaisu > 0) ans.pb({ i,kaisu }); } if (x != 1) ans.pb({ x,1 }); return ans; } bool isp(ll x) {//素数判定 O(sqrt(x)) auto y = sib(x); return (x != 1 && y.sz == 1 && y[0] == pll{ x, 1 }); } vec> sib(ll x, ll y) {//閉区間[x,y]全素因数分解 x=1は何も返さない O(max(sqrt(y),y-x)loglogy) ABC227G ABC412E vi b = ssa(sqrt(y) + 100); vec> r(y - x + 1); vll num(y - x + 1); rp(i, y - x + 1) num[i] = x + i; for (ll k : b) for (ll a = (1 + (x - 1) / k) * k; a <= y; a += k) { ll kaisu = 0; while (num[a - x] % k == 0) { num[a - x] /= k; kaisu++; } if (kaisu) r[a - x].pb({ k,kaisu }); } rp(i, y - x + 1) if (num[i] != 1) r[i].pb({ num[i],1 }); return r; } template ll sqrtll(T a, bool is_cut = 0) {//整数sqrt a<0orr非整数の場合-1を返す if (a < 0) return -1; ll r = sqrt(a); while (r * r > a) r--; while ((r + 1) * (r + 1) <= a) r++; if (r * r == a || is_cut)return r; else return -1; } #define llsqrt sqrtll ll powll(ll a, ll b) {//llでpow ll c = 1; assert(pow(a, b) <= 9e18); rp(i, b) { c *= a; } return c; } #define llpow powll template T sq(T a) {//2乗 return a * a; } template T cb(T a) {//3乗 return a * a * a; } string basea(ll x, ll a) {//xをa進法に変換 string r; while (x != 0) { r.pb(x % a + '0'); x /= a; } reverse(all(r)); return r; } ll base10(string x, ll a) {//a進数のxを10進法に戻す ll r = 0; rp(i, x.sz) { r *= a; r += x[i] - '0'; } return r; } vll vbasea(ll x, ll a) {//xをa進法に変換(vector) vll r; while (x != 0) { r.pb(x % a); x /= a; } reverse(all(r)); return r; } template ll bc(T x) {//bitcount assert(x >= 0); return __builtin_popcount(x); } double ds(double x1, double x2, double y1, double y2) {//dist return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); } ll ds2(ll x1, ll x2, ll y1, ll y2) {//distの2乗(整数値) return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); } template ll ds2(vec a) { return (a[0] - a[2]) * (a[0] - a[2]) + (a[1] - a[3]) * (a[1] - a[3]); } ll gpsum(ll a, ll r, ll n, ll m) {//初項a,公比r,項数nの等比数列の総和mod m r=10でレピュニットも可能 if (n == 0) return 0; if (n == 1) return a % m; modint::set_mod(m); if (n % 2 == 1) return (a + gpsum(a * r % m, r, n - 1, m)) % m; else return ((modint(r).pow(n / 2) + 1) * gpsum(a, r, n / 2, m)).val(); } //二分探索 template auto lwa(typename std::vector::iterator b, typename std::vector::iterator e, T c) {//[b,e)でcより小さい最大の値のイテレータ(複数あれば右端) auto it = std::lower_bound(b, e, c); if (it == b) return e; --it; return it; } template auto lwa(vector& a, T b) {//aでbより小さい最大の値のイテレータ(複数あれば右端) return lwa(all(a), b); } template auto lwa(set& a, T b) {//aでbより小さい最大の値のイテレータ(複数あれば右端) auto i = a.lwb(b); if (i == a.begin()) return a.end(); else i--; return i; } template auto lwa(multiset& a, T b) {//aでbより小さい最大の値のイテレータ(複数あれば右端) auto i = a.lwb(b); if (i == a.begin()) return a.end(); else i--; return i; } template auto lwc(typename std::vector::iterator b, typename std::vector::iterator e, T c) {//aでb以下の最大の値のイテレータ(複数あれば左端) auto i = lwb(b, e, c); if (i != e && *i == c) return i; if (i == b) return e; else i--; return i; } template auto lwc(vector& a, T b) {//aでb以下の最大の値のイテレータ(複数あれば左端) return lwc(all(a), b); } template auto lwc(set& a, T b) {//aでb以下の最大の値のイテレータ(複数あれば左端) auto i = a.lwb(b); if (i != a.end() && *i == b) return i; if (i == a.begin()) return a.end(); else i--; return i; } template auto lwc(multiset& a, T b) {//aでb以下の最大の値のイテレータ(複数あれば左端) auto i = a.lwb(b); if (i != a.end() && *i == b) return i; if (i == a.begin()) return a.end(); else i--; return i; } template std::pair::iterator, typename vector::iterator> its(vec& v, T a) {//{--lwb,lwb}({x未満の右端,x以上の左端})のpair返す(なければend()) auto it = lwb(all(v), a); if (it == v.begin()) return { v.end(), it }; auto it2 = it; it2--; return { it2,it }; } template std::pair::iterator, typename set::iterator> its(set& v, T a) {//{--lwb,lwb}({x未満の右端,x以上の左端})のpair返す(なければend()) auto it = v.lwb(a); if (it == v.begin()) return { v.end(), it }; auto it2 = it; it2--; return { it2,it }; } template std::pair::iterator, typename multiset::iterator> its(multiset& v, T a) {//{--lwb,lwb}({x未満の右端,x以上の左端})のpair返す(なければend()) auto it = v.lwb(a); if (it == v.begin()) return { v.end(), it }; auto it2 = it; it2--; return { it2,it }; } template int rcount(vec& a, T l, T r) {//ソート済配列aから[l,r]の範囲(l以上r以下)の要素カウント //右端を超える最小のi-左端に引っかかる最小のi //l,rのどちらに対しても境界を含む/含まないを入れ替えるときupb/lwbを変えれば良い return upb(all(a), r) - lwb(all(a), l); } template int rcount(set& a, T l, T r) {//ソート済配列aから[l,r]の範囲(l以上r以下)の要素カウント return a.upb(r) - a.lwb(l); } template bool has(const Container& c, const Key& x) {//sort済vector/set/map等に対しその値を持つかどうか返す if constexpr (is_set_like::value || is_map_like::value) { // set / multiset / map return c.find(x) != c.end(); } else { // vector 等(ソート済前提) return std::binary_search(c.begin(), c.end(), x); } } //配列便利関数系 template bool chmin(T& M1, T M2) { if (M1 > M2) { M1 = M2; return 1; } else return 0; } template bool chmax(T& M1, T M2) { if (M1 < M2) { M1 = M2; return 1; } else return 0; } template auto vmax(T a) { return *max_element(all(a)); } template auto vmin(T a) { return *min_element(all(a)); } template auto vmaxi(T a) { return max_element(all(a)) - a.begin(); } template auto vmini(T a) { return min_element(all(a)) - a.begin(); } template auto vsum(vector a) { T x = 0; for (auto i : a)x += i; return x; } template vec inv(vec a) {//0-indexed 逆関数 vec ans(a.sz); rp(i, a.sz) { ans[a[i]] = i; } return ans; } template vec inv1(vec a) {//1-indexed vec ans(a.sz); rp(i, a.sz) { ans[a[i] - 1] = i + 1; } return ans; } template vec zat(vec a) {//座標圧縮 T=ll,int auto b = a; sort(all(b)); b.erase(unique(all(b)), b.end()); vec c(a.size()); rp(i, a.size()) { c[i] = lwb(all(b), a[i]) - b.begin(); } return c; } template vec rsw(vec a) {//累積和 T=ll,int vec b = { 0 }; rp(i, a.sz) b.pb(a[i] + b[b.sz - 1]); return b; } template T rswsum(vec& a, int l, int r) {//rsw配列から元の配列の[l,r)番目(0indexed)の和を取得 assert(0 <= l && l <= r); assert(r < a.sz); return a[r] - a[l]; } template T rswsum2(vec& a, int l, int r) {//rsw配列から元の配列の[l,r]番目(0indexed)の和を取得 return rswsum(a, l, r + 1); } //文字列系 vector> rle(string rr) { vector> ret; char lc; rep(i, 0, rr.size()) { if (i > 0 && rr[i] == lc) ret[ret.sz - 1].second++; else { ret.pb({ rr[i],1 }); } lc = rr[i]; } return ret; } vector> rle(vi rr) { vector> ret; int lc; rep(i, 0, rr.size()) { if (i > 0 && rr[i] == lc) ret[ret.sz - 1].second++; else { ret.pb({ rr[i],1 }); } lc = rr[i]; } return ret; } vector> rle(vll rr) { vector> ret; ll lc; rep(i, 0, rr.size()) { if (i > 0 && rr[i] == lc) ret[ret.sz - 1].second++; else { ret.pb({ rr[i],1 }); } lc = rr[i]; } return ret; } bool kai(string S) {//回文か判定 bool ans = 1; rp(i, S.size()) if (S[i] != S[S.size() - 1 - i]) ans = 0; return ans; } //その他 ll max(ll a, int b) { return max(a, ll(b)); } ll max(int a, ll b) { return max(ll(a), b); } ll min(ll a, int b) { return min(a, ll(b)); } ll min(int a, ll b) { return min(ll(a), b); } bool yn(bool jg) { if (jg) { cout << "Yes" << endl; return true; } else { cout << "No" << endl; return false; } } template void cp(map < T, ll >& a, T b, ll c) {//countplus if (a.find(b) == a.end()) a[b] = c; else a[b] += c; if (a[b] == 0) a.erase(b); } template bool cross(T a, T b, T c, T d) {//区間(a,b)と区間(c,d)が重なるか判定 return !(b <= c || d <= a); } template bool crosse(T a, T b, T c, T d) {//区間[a,b]と区間[c,d]が重なるか判定 return !(b < c || d < a); } template vec absort(vec a, vec b) {//l,rのl昇順r逆順sort vec> ab(a.sz); rp(i, a.sz) ab[i] = { a[i],-b[i],i }; sort(all(ab)); rp(i, a.sz) ab[i][1] = -ab[i][1]; return ab; } template bool rabc(T a, T b, T c) {//円環状でa,b,cがこの順か判定 同じ値はfalse return ((a - b) / abs(a - b)) * ((b - c) / abs(b - c)) * ((c - a) / abs(c - a)) > 0; } template bool labc(T a, T b, T c) {//a<=b bool labc2(T a, T b, T c) {//a<=b<=cか判定 return a <= b && b <= c; } #define inr2 labc2 vector> rot(vs a) {//時計回り90度回転 vector> r(a[0].sz, vector(a.sz)); rp(i, a.sz)rp(j, a[0].sz) r[j][a[0].sz - 1 - i] = a[i][j]; return r; } template vector> rot(vector> a) { vector> r(a[0].sz, vector(a.sz)); rp(i, a.sz)rp(j, a[0].sz) r[j][a.sz - 1 - i] = a[i][j]; return r; } template vector freq(vector a) {// 配列から度数分布 vector r(vmax(a) + 1, 0); rp(i, a.sz) { r[a[i]]++; } return r; } //実行時間調整付きassert std::chrono::steady_clock::time_point START_TIME; void start() { START_TIME = std::chrono::steady_clock::now(); } void assertt(bool b, int t) { if (b) return; if (START_TIME.time_since_epoch().count() == 0) { start(); } auto target_time = START_TIME + std::chrono::milliseconds(t - 100); while (std::chrono::steady_clock::now() < target_time); assert(0); } //lazy_segtree seg(n); //S:中身型 op:左右合成 e:初期値 //F:遅延型 mapping:遅延適用後の要素 composition:遅延合成( 関数f(g()) ) id:遅延初期値(何もさせない) using S = vll; using F = ll; S op(S a, S b) { return { a[0] + b[0],a[1] + b[1],a[2] + b[2] }; } S e() { return { 0,0,0 }; } using segt = segtree; S mapping(F x, S a) {//xをaに作用(x初期値に注意) S[l]~S[r]のopであるSにF適用するとF(S[l])~F(S[r])のopになる必要がある 、つまりL~Rの代表にFかけてもL~Rの代表であり続けられるようS作る必要がある if (x == -1) return a; vll t = { 0,0,0 }; t[x] = vsum(a); return t; } F composition(F f, F g) {//fの方が後(f初期値に注意) Fを何個合成しても1つのFで表せる if (f == -1)return g; return f; } F id() { return -1; } using lsegt = lazy_segtree; //cout< 関数名 = [&](引数の型1 引数名1, 引数の型2, 引数名2, ...) //function f=[&](int a,int b) //再帰しない場合 auto f=[&](int a,int b) ->ll{} int main() { ll h, w, sx, sy, n; cin >> h >> w >> sx >> sy >> n; vll dp(n + 1, -lmax); dp[0] = 0; vll x(n+1), y(n+1), c(n+1); x[0] = sx; y[0] = sy; c[0] = 0; rep(i,1,1+ n) cin >> x[i] >> y[i] >> c[i]; rp(i, n) { if(x[i]==x[i+1] || y[i]==y[i+1] || x[i]-y[i]==x[i+1]-y[i+1] || x[i] + y[i] == x[i + 1] + y[i + 1])chmax(dp[i + 1], dp[i]+c[i+1]); if(i!=n-1)chmax(dp[i + 2], dp[i]+c[i+2]); } cout << vmax(dp); }