Codeforces Round #380 (Div. 1, Rated, Based on Technocup 2017 – Elimination Round 2), problem: (D) Financiers Game Solution in C/C++

Hi Guys , I Just Tried to solve the Financiers Game problem , hope you might like it , please share if you’ve any better code .

#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <math.h>
#include <stack>
#include <deque>
#include <numeric>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <bitset>
#include <functional>
#define mpair make_pair
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
const ld epsylon = 1e-9;

const std::string PROGRAM_NAME = “ivo”;

int mem[4001][90][90][2];

int n;
vector<int> a;

const int inf = 0x7f7f7f7f;

#define update(x, y, z, t) (mem[x][y][z][t] == inf ? solve(x, y, z, t) : mem[x][y][z][t])

vector<int> prefix;

inline int get(int from, int to) {
return prefix[to + 1] – prefix[from];
}

int solve(int from, int diff, int val, int player) {

int right_cut = from + diff;
if (player == 1) {
right_cut -= val;
}
int to = n – 1 – right_cut;

if (from + val – 1 > to) {
return mem[from][diff][val][player] = 0;
}
if (player == 0) {
int answer = update(from + val, diff, val, 1) + get(from, from + val – 1);
if (from + val <= to) {
answer = max(answer, update(from + val + 1, diff, val + 1, 1) + get(from, from + val));
}
return mem[from][diff][val][player] = answer;
} else {
int answer = update(from, diff, val, 0) – get(to – val + 1, to);
if (from + val <= to) {
answer = min(answer, update(from, diff + 1, val + 1, 0) – get(to – val, to));
}
return mem[from][diff][val][player] = answer;
}
}

int main() {
// freopen((PROGRAM_NAME + “.in”).c_str(), “r”, stdin);
// freopen((PROGRAM_NAME + “.out”).c_str(), “w”, stdout);

memset(mem, 0x7f, sizeof(mem));
cin >> n;
a.clear();
a.resize(n);
for (int i = 0; i < (int)a.size(); ++i) {
scanf(“%d”, &a[i]);
}

prefix.clear();
prefix.resize(n + 1);
prefix[0] = 0;
for (int i = 0; i < (int)a.size(); ++i) {
prefix[i + 1] = prefix[i] + a[i];
}
cout << solve(0, 0, 1, 0) << endl;
return 0;
}

Hi Guys , I Just Tried to solve the Financiers Game problem , hope you might like it , please share if you’ve any better code .

#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <math.h>
#include <stack>
#include <deque>
#include <numeric>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <bitset>
#include <functional>
#define mpair make_pair
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
const ld epsylon = 1e-9;

const std::string PROGRAM_NAME = “ivo”;

int mem[4001][90][90][2];

int n;
vector<int> a;

const int inf = 0x7f7f7f7f;

#define update(x, y, z, t) (mem[x][y][z][t] == inf ? solve(x, y, z, t) : mem[x][y][z][t])

vector<int> prefix;

inline int get(int from, int to) {
return prefix[to + 1] – prefix[from];
}

int solve(int from, int diff, int val, int player) {

int right_cut = from + diff;
if (player == 1) {
right_cut -= val;
}
int to = n – 1 – right_cut;

if (from + val – 1 > to) {
return mem[from][diff][val][player] = 0;
}
if (player == 0) {
int answer = update(from + val, diff, val, 1) + get(from, from + val – 1);
if (from + val <= to) {
answer = max(answer, update(from + val + 1, diff, val + 1, 1) + get(from, from + val));
}
return mem[from][diff][val][player] = answer;
} else {
int answer = update(from, diff, val, 0) – get(to – val + 1, to);
if (from + val <= to) {
answer = min(answer, update(from, diff + 1, val + 1, 0) – get(to – val, to));
}
return mem[from][diff][val][player] = answer;
}
}

int main() {
// freopen((PROGRAM_NAME + “.in”).c_str(), “r”, stdin);
// freopen((PROGRAM_NAME + “.out”).c_str(), “w”, stdout);

memset(mem, 0x7f, sizeof(mem));
cin >> n;
a.clear();
a.resize(n);
for (int i = 0; i < (int)a.size(); ++i) {
scanf(“%d”, &a[i]);
}

prefix.clear();
prefix.resize(n + 1);
prefix[0] = 0;
for (int i = 0; i < (int)a.size(); ++i) {
prefix[i + 1] = prefix[i] + a[i];
}
cout << solve(0, 0, 1, 0) << endl;
return 0;
}