QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#136227 | #5038. City | PetroTarnavskyi# | RE | 0ms | 0kb | C++17 | 3.4kb | 2023-08-07 17:12:24 | 2023-08-07 17:12:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int MAX = 7474;
const int MAX2 = 304;
struct node
{
int nxt[MAX2];
int pref[MAX2];
int cnt;
node()
{
cnt = 0;
FOR (i, 0, MAX2) nxt[i] = -1;
}
} trie[MAX];
int idx = 0;
int roots[14][MAX];
int c[14][MAX];
int prob[14];
void add(VI v, int i, int j)
{
if (i == SZ(v)) trie[j].cnt++;
else
{
trie[j].cnt++;
if (trie[j].nxt[v[i]] != -1)
{
add(v, i + 1, trie[j].nxt[v[i]]);
}
else
{
add(v, i + 1, idx++);
}
}
}
void add(int cnt, int tot, VI v)
{
prob[cnt]++;
c[cnt][tot + 1]++;
if (roots[cnt][tot] == -1)
{
roots[cnt][tot] = idx++;
}
add(v, 0, roots[cnt][tot]);
}
vector<PII> parse(string s)
{
vector<PII> v;
string t = "";
FOR (j, 0, SZ(s))
{
if (s[j] == ',')
{
int time, wa;
if (t == "-")
{
time = 474;
wa = -1;
}
else
{
int k = 0;
while(t[k] != ' ') k++;
time = stoi(t.substr(0, k));
wa = stoi(t.substr(k + 1, SZ(t) - (k + 1)));
}
t = "";
v.PB({time, wa});
}
else
t += s[j];
}
return v;
}
int get_pos(int cnt, int t, VI& v)
{
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
FOR (i, 0, 14) FOR (j, 0, MAX) roots[i][j] = -1;
int n;
cin >> n;
VI mn(10, 474);
int MN = 7474, MX = 0;
FOR (iter, 0, n - 1)
{
string s;
getline(cin, s);
vector<PII> v = parse(s);
int cnt = 0;
int tot = 0;
assert(SZ(v) == 10);
FOR (i, 0, SZ(v))
{
if (v[i].S != -1)
{
cnt++;
tot += v[i].F + v[i].S * 20;
}
mn[i] = min(mn[i], v[i].F);
}
if (cnt)
{
MN = min(MN, tot);
MX = max(MX, tot);
}
sort(ALL(v));
int j = 9;
while (j >= 0 && v[j].S == -1)
{
v.pop_back();
j--;
}
reverse(ALL(v));
VI toad;
FOR (i, 0, j + 1) toad.PB(v[i].F);
if (j >= 0)
add(cnt, tot, toad);
}
FOR (i, 0, MAX)
{
trie[i].pref[0] = trie[trie[i].nxt[0]].cnt;
FOR (j, 1, MAX2) trie[i].pref[j] = trie[i].pref[j - 1] + trie[trie[i].nxt[j]].cnt;
}
FOR (i, 0, 14)
{
int st = (i ? prob[i - 1] : 0);
FOR (j, 0, MAX)
{
c[i][j] += st;
st = c[i][j];
}
}
string s;
cin >> s;
vector<PII> v = parse(s);
sort(ALL(v));
VI idxes(10);
iota(ALL(idxes), 0);
int ans = 0;
do
{
int an = 0;
int p = 0;
int t = 0;
int w = 0;
VI times;
FOR (i, 0, 10)
{
if (v[idxes[i]].S == -1 || v[idxes[i]].F + t > 300) break; // ? +- 1
p++;
t += v[idxes[i]].F;
w += v[idxes[i]].S;
times.PB(t);
if (t <= mn[idxes[i]]) an += 800; //
}
reverse(ALL(times));
if (t + w * 20 <= MN) an += 700;
if (t + w * 20 >= MX) an += 500;
int pos = get_pos(p, t + w * 20, times);
an += 5000 / pos;
if (pos <= n / 10) an += 1200;
else if (pos <= 3 * n / 10) an += 800;
else if (pos <= 6 * n / 10) an += 400;
ans = max(ans, an);
} while (next_permutation(ALL(idxes)));
cout << ans << '\n';
return 0;
}
详细
Test #1:
score: 0
Runtime Error
input:
1 1