/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 576.0 KiB
#2 Accepted 1ms 532.0 KiB
#3 Accepted 41ms 660.0 KiB
#4 Accepted 27ms 632.0 KiB
#5 Accepted 42ms 640.0 KiB
#6 Accepted 45ms 724.0 KiB
#7 Accepted 55ms 576.0 KiB
#8 Accepted 53ms 3.195 MiB
#9 Accepted 41ms 3.195 MiB

Code

#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define dbg(a,b,c,d) cerr<<a<<"  "<<b<<"  "<<c<<"  "<<d<<endl;
#define kill(a) {cout<<a<<endl;continue;}
#define KILL(a) {cout<<a<<endl;return 0;}
#define debug cerr<<"Error Found"<<endl;
#define mem(a,b) memset(a,b,sizeof(a))
#define lcm(a, b) (a/__gcd(a,b))*b
#define w(t) cin>>t;while(t--)
#define pi  2 * acos(0.0)
#define endl "\n"
int t, cs = 0;
const int mxn = 2e5 + 3, mod = 1e9 + 7;
int vis[2][2][mxn], ar[2][mxn];
int64_t dp[2][2][mxn];
int m;
int64_t rec(int i, int j, bool k)
{
    if(j == m)return -1e14;
    if(i == 1 and j == m - 1)return ar[i][j];

    if(vis[i][k][j] == cs)return dp[i][k][j];
    vis[i][k][j] = cs;
    int64_t ans = -1e15;
    if(!k)
    {
        ans = ar[i][j] + max(rec(i, j + 1, 0), rec(i, j + 1, 1));
        if(!i)ans = max(ans, ar[i][j] + rec(i + 1, j, k));
    }
    else ans = -j - 1 + max(rec(i, j + 1, 0), rec(i, j + 1, 1));
    return dp[i][k][j] = ans;
}
int32_t main()
{

    fast
    w(t)
    {

        cin >> m;
        for(int i = 0; i < 2; i++)for(int j = 0; j < m; j++)cin >> ar[i][j];
        cs++;
        cout << rec(0, 0, 0) << endl;
    }
}

Information

Submit By
Type
Submission
Problem
P1050 Game on 2d grid
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-08 18:35:44
Judged At
2024-11-11 02:22:40
Judged By
Score
100
Total Time
55ms
Peak Memory
3.195 MiB