Submission #728556

#TimeUsernameProblemLanguageResultExecution timeMemory
728556penguin133Kas (COCI17_kas)C++17
0 / 100
297 ms524288 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pi pair<int, int> #define pii pair<int, pi> #define fi first #define se second #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #endif mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); pair <bool, pi> dp[501][100001]; int n, A[505]; void solve(){ cin >> n; int sm = 0; for(int i=1;i<=n;i++)cin >> A[i], sm += A[i]; dp[0][50000] = {1, {50000, 50000}}; for(int i=1;i<=n;i++){ for(int j=0;j<=100000;j++){ dp[i][j] = dp[i-1][j]; if(j - A[i] >= 0 && dp[i-1][j-A[i]].fi){ if(!dp[i][j].fi)dp[i][j] = dp[i-1][j-A[i]]; else{ dp[i][j].se.fi = min(dp[i][j].se.fi, dp[i-1][j-A[i]].se.fi); dp[i][j].se.se = max(dp[i][j].se.se, dp[i-1][j-A[i]].se.se); } } if(j + A[i] <= 100000 && dp[i-1][j+A[i]].fi){ if(!dp[i][j].fi)dp[i][j] = dp[i-1][j+A[i]]; else{ dp[i][j].se.fi = min(dp[i][j].se.fi, dp[i-1][j+A[i]].se.fi); dp[i][j].se.se = max(dp[i][j].se.se, dp[i-1][j+A[i]].se.se); } } if(dp[i][j].fi){ dp[i][j].se.fi = min(dp[i][j].se.fi, j); dp[i][j].se.se = max(dp[i][j].se.se, j); } } } int mx = max(5e4 - dp[n][50000].se.fi, dp[n][50000].se.se - 5e4); cout << sm - mx; } main(){ ios::sync_with_stdio(0);cin.tie(0); int tc = 1; //cin >> tc; for(int tc1=1;tc1<=tc;tc1++){ // cout << "Case #" << tc1 << ": "; solve(); } }

Compilation message (stderr)

kas.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main(){
      | ^~~~
#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...