Submission #97310

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

int n, m;
vector<int> a, b;
vector<vector<pair<int, int> > > memo;

pair<int, int> solve(int i, int j)
{
    if(i == n && j == m)
        return make_pair(0, 0);
    if(memo[i][j].first != -1)
        return memo[i][j];

    pair<int, int> ret(-1, -1);
    if(i < n){
        pair<int, int> p = solve(i+1, j);
        swap(p.first, p.second);
        p.first += a[i];
        ret = max(ret, p);
    }
    if(j < m){
        pair<int, int> p = solve(i, j+1);
        swap(p.first, p.second);
        p.first += b[j];
        ret = max(ret, p);
    }

    return memo[i][j] = ret;
}

int main()
{
    cin >> n >> m;
    a.resize(n);
    b.resize(m);
    for(int i=0; i<n; ++i)
        cin >> a[i];
    for(int i=0; i<m; ++i)
        cin >> b[i];

    memo.assign(n+1, vector<pair<int, int> >(m+1, make_pair(-1, -1)));
    cout << solve(0, 0).first << endl;

    return 0;
}

Submission Info

Judge Result