Submission #242489

#TimeUsernameProblemLanguageResultExecution timeMemory
242489ant101Kas (COCI17_kas)C++14
70 / 100
129 ms3576 KiB
#include <iostream> #include <algorithm> #include <cstring> #include <iomanip> #include <fstream> #include <cmath> #include <vector> #include <set> #include <unordered_set> #include <unordered_map> #include <map> #include <stack> #include <queue> #include <assert.h> #include <limits> #include <cstdio> using namespace std; //#define RDEBUG 1 #ifdef RDEBUG #define D(x) x #else #define D(x) #endif #define inf 0x7fffffff #define MOD 1000000007 typedef long long ll; ll add(ll a, ll b) { a += b; if(a >= MOD) { a -= MOD; } return a; } ll sub(ll a, ll b) { a -= b; if(a < 0) { a += MOD; } return a; } ll mul(ll a, ll b) { return (a * b)%MOD; } void add_self(ll& a, ll b) { a = add(a, b); } void sub_self(ll& a, ll b) { a = sub(a, b); } void mul_self(ll& a, ll b) { a = mul(a, b); } const ll MAXN = 100010; // change this after sliding window implemented const ll offset = 50005; // and this ll N; ll hansIsAWeeb[2][MAXN]; ll coins[510]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> N; ll ret = 0; for (ll i = 0; i<N; i++) { cin >> coins[i]; ret+=coins[i]; } hansIsAWeeb[0][offset] = 0; for (ll i = 0; i<2; i++) { for (ll j = 0; j<MAXN; j++) { hansIsAWeeb[i][j] = 1e13; } } hansIsAWeeb[0][offset] = 0; for (ll i = 0; i<N; i++) { for (ll j = 0; j<MAXN; j++) { if (hansIsAWeeb[0][j] == 1e13) { continue; } ll delta = j-offset; hansIsAWeeb[1][delta-coins[i]+offset] = min(hansIsAWeeb[1][delta-coins[i]+offset], hansIsAWeeb[0][j]); hansIsAWeeb[1][delta+coins[i]+offset] = min(hansIsAWeeb[1][delta+coins[i]+offset], hansIsAWeeb[0][j]); hansIsAWeeb[1][delta+offset] = min(hansIsAWeeb[1][delta+offset], hansIsAWeeb[0][j]+coins[i]); } for (ll j = 0; j<MAXN; j++) { hansIsAWeeb[0][j] = hansIsAWeeb[1][j]; hansIsAWeeb[1][j] = 1e13; } } cout << (ret-hansIsAWeeb[0][offset])/2 + hansIsAWeeb[0][offset] << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...