| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1347135 | jump | Kas (COCI17_kas) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define int long long
int money[510];
int dp[2][50100];
std::pair<int,int> source[501][50100];
//dp[diff]=low =dp[(diff-money)]
signed main(){
int n;
std::cin >> n;
for(int i=0;i<n;i++){
std::cin >> money[i];
}
for(int m=50000;m>=0;m--){
dp[0][m]=-1e9;
dp[1][m]=-1e9;
}
dp[0][0]=0;
for(int i=0;i<n;i++){
for(int m=50000;m>=0;m--){
int diff = std::abs(money[i]-m);
if(diff>50000)continue;
int value = dp[0][m]+money[i];
if(value>dp[1][diff]){
source[i][diff]={i,m}
}
}
for(int m=50000;m>=0;m--){
int diff = std::abs(money[i]-m);
if(diff>50000)continue;
int value = dp[0][m]+money[i];
if(value>dp[1][diff]){
source[i][diff]={i,m}
}
}
}
}