This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef pair<int, int> ii;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int dp[2][N];
int a[N], n, sum = 0;
bool lst = 0, now = 1;
void maximize(int &a, const int &b)
{
if(a < b) a = b;
}
void solve()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i], sum += a[i];
for(int i = 0; i <= sum; i++)
dp[0][i] = dp[1][i] = -1;
dp[0][0] = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= sum; j++)
dp[now][j] = -1;
for(int j = 0; j <= sum; j++) if(dp[lst][j] != -1)
{
int team1 = dp[lst][j];
int team2 = dp[lst][j] - j;
//team1
int newt1 = team1 + a[i];
if(newt1 > team2)
maximize(dp[now][newt1 - team2], newt1);
else
maximize(dp[now][team2 - newt1], team2);
//team2
int newt2 = team2 + a[i];
if(newt2 > team1)
maximize(dp[now][newt2 - team1], newt2);
else
maximize(dp[now][team1 - newt2], team1);
// team1 nor team2
maximize(dp[now][j], dp[lst][j]);
}
swap(lst, now);
}
cout << dp[lst][0] + (sum - dp[lst][0] * 2);
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
int t = 1;
// cin >> t;
while(t--) solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |