Skip to content

Instantly share code, notes, and snippets.

@takageymt
Created March 8, 2017 08:48
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save takageymt/9298d1514ca2a6376d6cffd303b188c1 to your computer and use it in GitHub Desktop.
Save takageymt/9298d1514ca2a6376d6cffd303b188c1 to your computer and use it in GitHub Desktop.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define min(...) min({__VA_ARGS__})
#define max(...) max({__VA_ARGS__})
template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}
using pint = pair<int, int>;
using tint = tuple<int, int, int>;
using vint = vector<int>;
const int inf = 1LL << 55;
const int mod = 1e9 + 7;
int R, G, B;
int leftend = -1000;
int rightend = 1000;
int offset = 1000;
int red = -100;
int green = 0;
int blue = 100;
int dp[2000][1000];
int solve(int idx, int rem) {
if(rem == 0) return 0;
if(rightend-idx < rem) return inf;
if(idx >= rightend) return inf;
int& ret = dp[idx+offset][rem];
if(~ret) return ret;
ret = inf;
if(rem > G+B) ret = min(solve(idx+1, rem), solve(idx+1, rem-1) + abs(idx-red));
else if(rem > B) ret = min(solve(idx+1, rem), solve(idx+1, rem-1) + abs(idx-green));
else ret = min(solve(idx+1, rem), solve(idx+1, rem-1) + abs(idx-blue));
return ret;
}
signed main()
{
cin.tie(0);
ios_base::sync_with_stdio(0);
cout << fixed << setprecision(12);
cin >> R >> G >> B;
memset(dp, -1, sizeof(dp));
cout << solve(-1000, R+G+B) << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment