DTA

Run Settings
LanguageC++
Language Version
Run Command
#include <bits/stdc++.h> using namespace std; // type typedef long long ll; typedef long double ld; // loop //#define For(i, l, r, x) for (int i = l; i < r; i+=x) //#define ForE(i, l, r, x) for (int i = l; i <= r; i+=x) //#define Ford(i, r, l) for (int i = r; i > l; i--) //#define FordE(i, r, l) for (int i = r; i >= l; i--) //#define Fora(i, a) for (auto i : a) // I/O #define FAST_IO std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //#define PrintV(a) Fora(ii, a) cout << ii << ' '; cout << rl; //#define PrintVl(a) Fora(ii, a) cout << ii << rl; //#define PrintA(a, l, r) for (int ii = l; ii <= r; ii++) cout << a[ii] << ' '; cout << rl; //#define PrintAl(a, l, r) for (int ii = l; ii <= r; ii++) cout << a[ii] << rl; //#define Ptest(x) return cout << x, 0; #define setpre(n) fixed << setprecision(n) // pair #define F first #define S second #define pii pair<int, int> #define pll pair<ll, ll> #define pdd pair<ld, ld> // vector & !!?(string) #define eb emplace_back #define pb push_back #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define sz(a) a.size() #define len(a) a.length() // geometry calc #define pi acos(-1.0) #define g_sin(a) sin(a*pi/180) #define g_cos(a) cos(a*pi/180) #define g_tan(a) tan(a*pi/180) // set val #define ms0(a) memset(a, 0, sizeof(a)); #define ms1(a) memset(a, 1, sizeof(a)); #define msn1(a) memset(a, -1, sizeof(a)); #define msinf(a) memset(a, 0x3f3f3f, sizeof(a)); // constant const int mod1 = 998244353, mod = 1e9+7; const int MAX_N = 100005, MAX_M = 200010; // code //#define int long long int a[3][MAX_N], n, re[3][MAX_N], dp[3][MAX_N]; void Solve() { cin >> n; for (int i = 0; i < 2; i++){ for (int j = 1; j <= n; j++){ cin >> a[i][j]; } } for (int i = 1; i <= n; i++){ a[0][i] += a[0][i-1]; a[1][i] += a[1][i-1]; a[2][i] = a[1][i] + a[0][i]; } for (int t = 0; t < 3; t ++){ map<int, int> idx; for (int i = 0; i <= n; i++){ if (idx.count(a[t][i])){ re[t][i] = idx[a[t][i]]; }else{ re[t][i] = -1; } idx[a[t][i]] = i; } } for (int t = 0; t < 2; t ++){ for (int i = 1; i <= n; i++){ dp[t][i] = dp[t][i-1]; if (re[t][i] != -1) dp[t][i] = max(dp[t][i], 1 + dp[t][re[t][i]]); dp[2][i] += dp[t][i]; } } for (int i = 1; i <= n; i++){ dp[2][i] = max(dp[2][i-1], dp[2][i]); if (re[2][i] != -1) dp[2][i] = max(dp[2][i], 1 + dp[2][re[2][i]]); } /* for (int i = 0; i < 3; i++){ for (int j = 1; j <= n; j++) cout << dp[i][j] << ' '; cout << endl; } */ cout << dp[2][n]; } signed main(){ FAST_IO; int TC = 1; //cin >> TC; while(TC--) Solve(); return 0; }
Editor Settings
Theme
Key bindings
Full width
Lines