# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
922217 |
2024-02-05T08:50:55 Z |
Whisper |
Kas (COCI17_kas) |
C++17 |
|
395 ms |
395860 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using str = string;
using T = tuple<ll, ll, ll>;
#define int long long
#define Base 41
#define sz(a) (int)a.size()
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for ( int i = b ; i >= a ; i-- )
#define REP(i, n) for ( int i = 0 ; i < n ; ++i )
#define REPD(i, n) for ( int i = n - 1 ; ~(--i) ; )
#define all(x) x.begin() , x.end()
#define pii pair<int , int>
#define fi first
#define se second
#define Lg(x) 31 - __builtin_clz(x)
constexpr ll MN = 1e6 + 1;
constexpr ll LINF = (1ll << 62);
constexpr int INF = (1ll << 31);
constexpr int MAX = 5e2 + 5;
constexpr int Mod = 1e9 + 7;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
void setupIO( const string& PROB ){
//Phu Trong from Nguyen Tat Thanh High School for gifted student
srand(time(NULL));
cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
// freopen( (PROB + ".inp").c_str(), "r", stdin);
// freopen( (PROB + ".out").c_str(), "w", stdout);
cout << fixed << setprecision(10);
}
int n;
int a[MAX];
const int maxN = 1e5 + 5;
int dp[MAX][maxN];
//dp(i, diff) is the total money with difference diff till i
int f(int i , int diff){
if (i == n + 1) return (diff == 0 ? 0 : -INF);
if (diff >= (int)(1e6)) return -INF;
int &ans = dp[i][diff];
if (~ans) return ans;
ans = max({f(i + 1, diff), f(i + 1, diff + a[i]) + a[i], f(i + 1, abs(diff - a[i])) + a[i]});
return ans;
}
void Whisper(){
cin >> n;
for (int i = 1 ; i <= n ; i++) cin >> a[i];
int sum = accumulate(a + 1, a + n + 1, 0ll);
memset(dp, -1, sizeof dp);
int ans = f(0, 0) / 2 + sum - f(0, 0);
cout << ans;
}
signed main(){
setupIO("Whisper");
int Test = 1;
// cin >> Test;
for ( int i = 1 ; i <= Test ; i++ ){
Whisper();
if (i < Test) cout << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
156 ms |
395712 KB |
Output is correct |
2 |
Correct |
152 ms |
395752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
154 ms |
395560 KB |
Output is correct |
2 |
Correct |
162 ms |
395572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
146 ms |
395672 KB |
Output is correct |
2 |
Correct |
146 ms |
395668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
140 ms |
395652 KB |
Output is correct |
2 |
Correct |
135 ms |
395576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
154 ms |
395604 KB |
Output is correct |
2 |
Correct |
135 ms |
395720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
135 ms |
395516 KB |
Output is correct |
2 |
Correct |
143 ms |
395860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
168 ms |
395740 KB |
Output is correct |
2 |
Correct |
138 ms |
395596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
177 ms |
395764 KB |
Output is correct |
2 |
Correct |
152 ms |
395756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
172 ms |
395588 KB |
Output is correct |
2 |
Correct |
182 ms |
395660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
254 ms |
395604 KB |
Output is correct |
2 |
Correct |
395 ms |
395800 KB |
Output is correct |