| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 965467 |
2024-04-18T16:44:10 Z |
phamducminh |
Kas (COCI17_kas) |
C++17 |
|
248 ms |
399020 KB |
//******************/
//* I<3 C++ */
//* I WANT ANY AC */
//* I LOVE PROGRAM!*/
//*IT'S long longERESTING*/
//* I LOVE PROGRAM!*/
//* IN CONTESTS */
//* GET SCORE */
//* AC CODE */
//* LET'S */
//* GO */
//* Written by: */
//* Duc Minh */
#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define file(name) freopen(name".inp", "r", stdin);\
freopen(name".out", "w", stdout);
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define all(a) a.begin(),a.end()
#define endl "\n"
#define all1(a) a+1,a+n+1
#define unordered_map map
// #define push_back emplace_back
// #define gcd(a,b) __gcd(a,b);
// #define lcm(a,b) (a*b)/gcd(a,b);
const long long INF = (long long)1e9;
const long long MOD = (long long)1e9+7;
const long long MODD = 1e9; /// 998244353
const int maxN = 1e5+55;
const int LOG = 30;
const int mlift = 20;
///--------------------------------
void solve();
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
// file("CTREE");
long long t;
// cin >> t;
t=1;
while (t--){
solve();
}
cerr << "Time elapsed: " << TIME << "s.\n";
cerr << "ducminh" << "\n";
return 0;
}
///--------------------[PROBLEM SOLUTION]--------------------///
long long dp[509][100009];
long long sum=0,n,a[509];
void solve(){
// dp[i][sum]
cin >> n;
for (int i=1; i<=n; i++){
cin >> a[i];
sum+=a[i];
}
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
for (int i=1; i<=n; i++){
for (int j=0; j<=sum; j++){
if (j+a[i]<=sum) dp[i][j]=min(dp[i][j],dp[i-1][j+a[i]]);
dp[i][j]=min({dp[i][j],dp[i-1][j]+a[i],dp[i-1][abs(j-a[i])]});
}
}
cout << (sum-dp[n][0])/2+dp[n][0];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
203 ms |
398740 KB |
Output is correct |
| 2 |
Correct |
119 ms |
399020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
155 ms |
398848 KB |
Output is correct |
| 2 |
Correct |
117 ms |
398852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
398676 KB |
Output is correct |
| 2 |
Correct |
116 ms |
398672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
398676 KB |
Output is correct |
| 2 |
Correct |
116 ms |
398912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
398916 KB |
Output is correct |
| 2 |
Correct |
116 ms |
398752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
398696 KB |
Output is correct |
| 2 |
Correct |
116 ms |
398768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
398784 KB |
Output is correct |
| 2 |
Correct |
118 ms |
398676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
192 ms |
398908 KB |
Output is correct |
| 2 |
Correct |
165 ms |
398664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
176 ms |
398900 KB |
Output is correct |
| 2 |
Correct |
205 ms |
398908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
248 ms |
398816 KB |
Output is correct |
| 2 |
Correct |
224 ms |
398904 KB |
Output is correct |
