QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#430241 | #8772. House Deconstruction | djq_cpp | WA | 0ms | 13376kb | C++14 | 2.7kb | 2024-06-03 16:23:26 | 2024-06-03 16:23:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
LL sgnx(LL x) {
return x < 0 ? -1 : 1;
}
LL absx(LL x) {
return x < 0 ? -x : x;
}
int n, m, t, x[400005], y[400005], psum[400005], pre[400005];
LL rsum[400005], dp[400005];
LL gen_dp(int ps) {
int l, r;
for(l = 0; l <= n && psum[l] != ps; l++) ;
for(r = n; r >= 0 && psum[r] != psum[n] + ps; r--) ;
if(l > r) return INF + absx(ps) * t;
dp[l] = 0;
for(int i = l; i < r; i++) {
dp[i + 1] = INF;
if(y[i] == 1) dp[i + 1] = min(dp[i + 1], dp[i]);
if(pre[i + 1] >= l) dp[i + 1] = min(dp[i + 1], dp[pre[i + 1]] + absx(rsum[i + 1] - rsum[pre[i + 1]]));
}
LL ret = dp[r] + sgnx(ps) * (1LL * ps * t + rsum[l] - rsum[r] + rsum[n]);
return ret;
}
const int MOD = 998244353;
int ans, cdp[400005];
bool bc[400005];
void count(int ps) {
int l, r;
for(l = 0; l <= n && psum[l] != ps; l++) ;
for(r = n; r >= 0 && psum[r] != psum[n] + ps; r--) ;
for(int i = l; i <= r; i++) {
bc[i] = false; cdp[i] = 0;
}
bc[r] = true;
for(int i = r - 1; i >= 0; i--) if(bc[i + 1]) {
if(y[i] == 1 && dp[i + 1] == dp[i]) bc[i] = true;
if(pre[i + 1] >= l && dp[i + 1] == dp[pre[i + 1]] + absx(rsum[i + 1] - rsum[pre[i + 1]])) bc[pre[i + 1]] = true;
}
cdp[l] = 1;
for(int i = l; i < r; i++) if(bc[i + 1]) {
if(dp[i + 1] == dp[i]) cdp[i + 1] = (cdp[i + 1] + cdp[i]) % MOD;
if(pre[i + 1] >= l && dp[i + 1] == dp[pre[i + 1]] + absx(rsum[i + 1] - rsum[pre[i + 1]])) {
int coef = cdp[pre[i + 1]];
cdp[i + 1] = (cdp[i + 1] + coef) % MOD;
}
}
ans = (ans + cdp[r]) % MOD;
}
int pp[800005];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> t >> n >> m;
n += m;
for(int i = 0; i < n; i++) {
char ch;
cin >> x[i] >> ch;
y[i] = ch == 'P' ? -1 : 1;
}
for(int i = 0; i < n; i++) {
psum[i + 1] = psum[i] + y[i];
rsum[i + 1] = rsum[i] + x[i] * y[i];
}
memset(pp, -1, sizeof(pp));
for(int i = 0; i <= n; i++) {
pre[i] = pp[psum[i] + n];
pp[psum[i] + n] = i;
}
int l = -n, r = n;
LL a0, a1;
while(l < r) {
int mid = (l + r) >> 1;
a0 = gen_dp(mid);
a1 = gen_dp(mid + 1);
if(a0 > a1) l = mid + 1;
else r = mid;
}
for(int i = l; i <= r; i++) {
a0 = gen_dp(i); count(i);
}
while(gen_dp(l - 1) == min(a0, a1)) count(--l);
while(gen_dp(r + 1) == min(a0, a1)) count(++r);
assert(r - l <= 1);
cout << a0 << ' ' << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 13376kb
input:
6 2 4 1 P 2 H 3 P 4 H 5 H 6 H
output:
2 3
result:
wrong answer 1st lines differ - expected: '2', found: '2 3'