题解 | 收集金币

#include <iostream>
using namespace std;

#include<vector>
#include<algorithm>
int main(){
int n,m;
cin>>n>>m;
vector<vector<long long>>v(n+1,vector<long long>(m+1));
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++)
    {
        cin>>v[i][j];
    }
}
vector<vector<long long>>a(n+1,vector<long long>(m+1,1e18));
long long t;
cin>>t;
while(t--){
long long x,y,v;
cin>>x>>y>>v;
a[x][y]=v;


}
vector<vector<long long>>b(n+1,vector<long long>(m+1,-1e18));
b[0][1]=0;
b[1][0]=0;
long long re=-1;
for(long long i=1;i<=n;i++){
for(long long j=1;j<=m;j++){
if(a[i][j]>i+j-2){
    b[i][j]=max(b[i-1][j],b[i][j-1])+v[i][j];
    re=max(re,b[i][j]);
}


}

}
cout<<re;

    return 0;
}