Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <algorithm>
- #include <vector>
- #include <algorithm>
- #include <set>
- #include <cstring>
- using namespace std;
- int n,m;
- int mat[1000][1000];
- int dp[1000][1000];
- vector<pair<int, int> > v[1000];
- int main(){
- ios_base::sync_with_stdio(false);
- cin >> n >> m;
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- cin >> mat[i][j];
- }
- }
- for(int i = 0; i < n - 1; i++) {
- for(int j= 0; j < m; j++) {
- v[i].push_back(make_pair(mat[i][j] + mat[i + 1][j], j));
- }
- sort(v[i].begin(), v[i].end());
- reverse(v[i].begin(), v[i].end());
- }
- memset(dp,0,sizeof dp);
- dp[0][0] = mat[0][0];
- for (int i = 0; i < n-1; i++) {
- for (int j = 0; j < m; j++) {
- for (int k = 0; k < min(3, m) ; k++) {
- if(v[i][k].second != j) {
- dp[i + 1][v[i][k].second] = max(dp[i + 1][v[i][k].second], dp[i][j] + v[i][k].first);
- }
- }
- }
- }
- int res = dp[n-1][m-1];
- for(int i = 0; i < m-1; i++) {
- if(n == 2 && i == 0){
- continue;
- }
- res = max(res,dp[n-1][i] + mat[n-1][m-1]);
- }
- cout << res;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement