QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#430241#8772. House Deconstructiondjq_cppWA 0ms13376kbC++142.7kb2024-06-03 16:23:262024-06-03 16:23:26

Judging History

你现在查看的是最新测评结果

  • [2024-06-03 16:23:26]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:13376kb
  • [2024-06-03 16:23:26]
  • 提交

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'