比赛 |
集训 |
评测结果 |
AAAAAAAAATW |
题目名称 |
兔子集团军 |
最终得分 |
82 |
用户昵称 |
OTTF |
运行时间 |
3.282 s |
代码语言 |
C++ |
内存使用 |
80.95 MiB |
提交时间 |
2025-07-03 10:17:01 |
显示代码纯文本
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
template <typename T>
void read (T& num) {
T res = 0;
T ch = getchar();
T op = 1;
while (!isdigit (ch) && ch != EOF) {
op = (ch == '-' ? -1 : 1);
ch = getchar ();
}
while (isdigit (ch)) {
res = (res * 10) + (ch - '0');
ch = getchar ();
}
num = op * res;
}
class Read {
public:
Read operator>> (auto& other) {
read (other);
return (*this);
}
};
Read in;
constexpr int N = 1919810;
constexpr int Mod1 = 10000019;
constexpr int Mod2 = 10000079;
constexpr int Len = 10000100;
int n;
int c[N];
long long v[N];
long long f[N];
long long sum[N];
bool easy = true;
int first[N];
int last[N];
long long power1[N] = {1, 11};
long long power2[N] = {1, 13};
int ha1[Len];
int ha2[Len];
bool firstmark[N];
bool lastmark[N];
long long minn;
int main () {
freopen ("RRR.in", "r", stdin);
freopen ("RRR.out", "w", stdout);
in >> n;
for (int i = 1; i <= n; i++) {
in >> c[i];
if (!first[c[i]]) {
first[c[i]] = i;
}
last[c[i]] = i;
}
for (int i = 1; i <= n; i++) {
in >> v[i];
}
for (int i = 1; i <= n; i++) {
in >> f[i];
if (f[i] != 1) {
easy = false;
}
f[i] *= f[i];
sum[i] = f[i] + sum[i - 1];
}
for (int i = 2; i <= n; i++) {
power1[i] = power1[i - 1] * 11 % Mod1;
power2[i] = power2[i - 1] * 13 % Mod2;
}
for (int i = 1; i <= n; i++) {
if (first[i]) {
firstmark[first[i]] = lastmark[last[i]] = true;
}
}
long long now1 = 0;
long long now2 = 0;
for (int i = 1; i <= n; i++) {
if (firstmark[i]) {
ha1[now1] = i;
ha2[now2] = i;
now1 = (now1 + power1[c[i]]) % Mod1;
now2 = (now2 + power2[c[i]]) % Mod2;
}
if (lastmark[i]) {
now1 = (now1 - power1[c[i]] + Mod1) % Mod1;
now2 = (now2 - power2[c[i]] + Mod2) % Mod2;
if (ha1[now1] && ha2[now2] && (ha1[now1] == ha2[now2])) {
long long res = 0;
if (easy) {
res = sum[i] - sum[ha1[now1] - 1];
}
else {
for (int j = ha1[now1]; j <= i; j++) {
res += v[j] * f[j - ha1[now1] + 1];
}
}
if (!minn || (res < minn && res >= 0)) {
minn = res;
}
ha1[now1] = 0;
ha2[now2] = 0;
}
}
}
printf ("%lld\n", minn);
return 0;
}