dp intermediate 1

intermediate.cpp

// ConsoleApplication5.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <iostream>
using namespace std;

int maxim(int a, int b){
	return a > b ? a : b;
}

void print(int* data, int n, int m){
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			cout << data[i*m + j] << " ";
		}
		cout << endl;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	int n, m, q;
	cin >> n >> m >> q;

	auto data = new int[n*m];

	for (int i = 0; i < n; i++){
		for (int k = 0; k < m; k++){
			cin >> data[i*m + k];
		}
	}

	int max = 0;
	int* mem = new int[n*m];
	for (int i = 0; i < n*m; i++){
		mem[i] = 0;
	}

	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			int l = j > 0 ? mem[i*m + j - 1] : 0;
			int t = i>0 ? mem[(i - 1)*m + j] : 0;

			mem[i*m + j] = maxim(l, t) + data[i*m + j];
		}
	}

	for (int i = 0; i < q; i++){
		int x, y;
		cin >> y >> x;
		cout << mem[(y - 1) * m + (x - 1)] << endl;
	}

	return 0;
}