#1173212 (C++23(gcc16)) No.3597 Queen Score Attack 2

• 問題: No.3597 Queen Score Attack 2
• ユーザー: Leal-0
• 提出日時: 2026-07-24 22:38:18
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 340 ms / 2,000 ms
• コード長: 2,843 bytes
• コンパイル時間: 4,923 ms
• コンパイル使用メモリ: 376,696 KB
• 実行使用メモリ: 23,040 KB
• 最終ジャッジ日時: 2026-07-24 22:38:31
• 合計ジャッジ時間: 11,690 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_1

ファイルパターン	結果
sample	AC * 3
other	AC * 18

ソースコード

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define srep(i,l,r) for(ll i=l;i<=r;i++)
#define irep(i,r,l) for(ll i=r;i>=l;i--)
using ll = long long;
using ld = long double;
const ll mod=998244353;
#define vout(v) for(auto i :v) cout<<i<<" "; cout<<nl;
#define INF 9223300000000000000ll
#define Winf 5e12
#define nl "\n"
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define vl vector<ll>
#define pb push_back
#define vc vector<char>
#define vb vector<bool>
#define uniq(x) sort((x).begin(),(x).end());(x).erase(unique((x).begin(),(x).end()),(x).end())
#define eb emplace_back



void no(void) { cout<<"No"<<nl;}
void yes(void) {cout<<"Yes"<<nl;}
void yn(bool a) {
    cout<<(a ? "Yes":"No")<<nl;
}


vector<ll> dx={-1,0,1,0,1,1,-1,-1};
vector<ll> dy={0,-1,0,1,-1,1,-1,1};

bool isin(ll i,ll j,ll h,ll w) {
    if(i<0 || i>=h || j<0 || j>=w) return false;
    return true;
}

template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}


template<class T>T vecmax(const vector<T>&v){return *max_element(all(v));}
template<class T>T vecmin(const vector<T>&v){return *min_element(all(v));}

ll safemod(ll num,ll rule) {
    return (num%rule+rule)%rule;
}

ll sum(vector<ll> &a) {
    return accumulate(all(a),0ll);
}
template<class T>void vvpr(vector<vector<T>> g) {
    rep(i,g.size()) {
        cout<<"here: i="<<i<<" ";
        rep(j,g[i].size()) {
            cout<<g[i][j]<<(j==g[i].size()-1 ? "\n":" ");
        }
    }
}
ll modpow(ll fl, ll po, ll mode) {  // mode: 0=modなし, 1=modあり
    ll ret(1);
    #define MOD 998244353
    if (mode) {
        fl%=ll(MOD);
        while (po>0) {
            if (po&1) ret=(ret*fl)%ll(MOD);
            fl=(fl*fl)%ll(MOD);
            po>>=1;
        }
    } else {
        while (po>0) {
            if(po&1) ret*=fl;
            fl*=fl;
            po>>=1;
        }
    }
    return ret;
}


bool pasolve(ll h,ll w,ll h1,ll w1) {
    //if(h==h1 && w==w1) return false;
    return (h==h1 || w==w1 || h+w==h1+w1 || h-w==h1-w1);
}
int main() {
    ll h,w,sx,sy,n;
    cin>>h>>w>>sx>>sy>>n;
    //2ta-nでいけるはず
    vl x(n),y(n),c(n);
    rep(i,n) cin>>x[i]>>y[i]>>c[i];
    ll score=0;
    vector<array<ll,2>> dp(n+1,{(ll)-1e16,(ll)-1e16});
    dp[0][0]=0;
    if(pasolve(sx,sy,x[0],y[0])) dp[0][1]=0;
    srep(i,1,n) {
        if(i<n && pasolve(x[i-1],y[i-1],x[i],y[i])) {
            dp[i][1]=dp[i-1][1]+c[i-1];
        }
        else {
            dp[i][0]=dp[i-1][1]+c[i-1];
        }
        chmax(dp[i][1],dp[i-1][0]);
        chmax(dp[i][1],dp[i-1][1]);
        chmax(dp[i][0],dp[i-1][0]);
    }
    cout<<max(dp[n][0],dp[n][1])<<nl;
}