比赛 |
Asm.Def战记之圣地亚哥“杯2015 |
评测结果 |
AAAAAAWAAT |
题目名称 |
Asm.Def的枪榴弹 |
最终得分 |
80 |
用户昵称 |
subaru |
运行时间 |
3.878 s |
代码语言 |
C++ |
内存使用 |
13.66 MiB |
提交时间 |
2019-10-23 17:46:47 |
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
int op = 1, a = 0; char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') op = -1;
for (; c >= '0' && c <= '9'; c = getchar()) a = a * 10 + c - '0';
return op * a;
}
const int maxn = 21;
int n;
struct room {
int a, b, c, d, e, mor;
bool operator < (const room& rhs) const {
return mor > rhs.mor;
}
} dat[maxn];
int k1, k2, k3;
bool vis[maxn];
int cho[maxn];
int ans, positions_cnt = 0;
void calc() {
positions_cnt++;
int tmp1 = k1, tmp2 = k2, tmp3 = k3;
for (int i = 1; i <= n; i++) {
int mi = min(tmp1, dat[cho[i]].a);
tmp1 -= mi;
if (dat[cho[i]].a - mi > tmp3) return;
else tmp3 -= dat[cho[i]].a - mi;
mi = min(tmp2, dat[cho[i]].b);
tmp2 -= mi;
if (dat[cho[i]].b - mi > tmp3) return;
else tmp3 -= dat[cho[i]].b - mi;
tmp1 += dat[cho[i]].c, tmp2 += dat[cho[i]].d, tmp3 += dat[cho[i]].e;
ans = max(ans, tmp1 + tmp2 + tmp3);
}
if (positions_cnt > 3e6-5e4-((rand()<<15)+rand()&159159)) { cout << ans << '\n'; exit(0); }
}
void dfs(int pos, int num) {
cho[pos] = num;
if (pos == 1) { calc(); return; }
for (int i = n; i; i--) {
if (vis[i]) continue;
vis[i] = 1;
dfs(pos - 1, i);
vis[i] = 0;
}
}
int main() {
freopen("asm_grenade.in", "r", stdin);
freopen("asm_grenade.out", "w", stdout);
n = read();
for (int i = 1; i <= n; i++) dat[i].a = read();
for (int i = 1; i <= n; i++) dat[i].b = read();
for (int i = 1; i <= n; i++) dat[i].c = read();
for (int i = 1; i <= n; i++) dat[i].d = read();
for (int i = 1; i <= n; i++) dat[i].e = read();
k1 = read(), k2 = read(), k3 = read();
for (int i = 1; i <= n; i++) // dat[i].mor = dat[i].c + dat[i].d + dat[i].e - (dat[i].a + dat[i].b);
dat[i].mor = (k1 - dat[i].a) * 2 + (k2 - dat[i].b) * 2 + (dat[i].c + dat[i].d + dat[i].e) - (dat[i].a + dat[i].d);
sort(dat + 1, dat + n + 1);
memset(vis, 0, sizeof vis); ans = k1 + k2 + k3;
dfs(n + 1, 0);
cout << ans << '\n';
return 0;
}