/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Accepted 1ms 568.0 KiB
#3 Accepted 1ms 416.0 KiB
#4 Accepted 2ms 576.0 KiB
#5 Accepted 31ms 584.0 KiB
#6 Accepted 46ms 17.254 MiB
#7 Accepted 46ms 17.34 MiB
#8 Accepted 45ms 17.309 MiB
#9 Accepted 44ms 17.277 MiB
#10 Accepted 44ms 17.312 MiB
#11 Accepted 44ms 17.355 MiB
#12 Accepted 44ms 17.312 MiB
#13 Accepted 44ms 17.262 MiB
#14 Accepted 45ms 17.352 MiB
#15 Accepted 46ms 17.363 MiB
#16 Accepted 45ms 17.266 MiB

Code

#include<bits/stdc++.h>
typedef long long   ll;
#define endl        '\n'
#define F           first
#define S           second
#define pb          push_back
#define yes         cout<<"YES\n"
#define no          cout<<"NO\n"
#define all(x)      x.begin(),x.end()
#define allr(x)     x.rbegin(),x.rend()
#define error1(x)   cerr<<#x<<" = "<<(x)<<endl
#define error2(a,b) cerr<<"("<<#a<<", "<<#b<<") = ("<<(a)<<", "<<(b)<<")\n";
#define coutall(v)  for(auto &it: v) cout<<it<<" "; cout<<endl;
#define _ASRafi__   ios::sync_with_stdio(false); cin.tie(0);
using namespace std;

const int N = 1e5 + 7;
ll n;
ll a[N], b[N], c[N];

ll rec(int i, short back, vector<vector<ll>> &dp)
{
    if(i >= n) return 0;
    if(dp[i][back] != -1) return dp[i][back];
    ll ans = LLONG_MIN;
    if(back != 1) ans = max(ans, a[i] + rec(i + 1, 1, dp));
    if(back != 2) ans = max(ans, b[i] + rec(i + 1, 2, dp));
    if(back != 3) ans = max(ans, c[i] + rec(i + 1, 3, dp));
    // cout << i << ", " << back << " => " << ans << endl;
    return dp[i][back] = ans;
}

void solve()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        ll x; cin >> x;
        a[i] = x;
    }
    for (int i = 0; i < n; i++)
    {
        ll x; cin >> x;
        b[i] = x;
    }
    for (int i = 0; i < n; i++)
    {
        ll x; cin >> x;
        c[i] = x;
    }
    vector<vector<ll>> dp(n + 3, vector<ll> (4, -1));
    cout << rec(0, 0, dp) << endl;
    return;
}

int32_t main()
{
    _ASRafi__;
    int tc = 1;
    cin >> tc;
    for (int t = 1; t <= tc; t++)
    {
        // cout << "Case " << t << ": ";
        solve();
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1046 Maximum sum in 3-array
Contest
TLE_Headquarters - round #1
Language
C++17 (G++ 13.2.0)
Submit At
2024-03-27 17:06:32
Judged At
2024-03-27 17:06:32
Judged By
Score
100
Total Time
46ms
Peak Memory
17.363 MiB