QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#742975#6794. Sequence to SequenceJWRuixiAC ✓117ms6064kbC++171.7kb2024-11-13 17:47:032024-11-13 17:47:11

Judging History

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

  • [2024-11-13 17:47:11]
  • 评测
  • 测评结果:AC
  • 用时:117ms
  • 内存:6064kb
  • [2024-11-13 17:47:03]
  • 提交

answer

#ifdef LOCAL
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define sz(v) ((int) (v).size())
#define me(f, x) memset(f, x, sizeof(f))
#define mc(f, g) memcpy(f, g, sizeof(g))
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;

using vi = vector<int>;
#endif

constexpr int N = 1e6 + 9;
int n, a[N], b[N];
LL dp[1 << 2], _dp[1 << 2];

void slv () {
  cin >> n;
  L (i, 1, n) {
    cin >> a[i];
  }
  L (i, 1, n) {
    cin >> b[i];
  }
  L (i, 1, n) {
    if (!a[i] && b[i]) {
      cout << "-1\n";
      return;
    }
  }
  me(dp, -0x3f);
  dp[0] = 0;
  L (i, 1, n) {
    me(_dp, -0x3f);
    L (B, -1, 1) {
      if (!b[i] && B != 0) {
        continue;
      }
      L (A, B - 1, B + 1) {
        if ((!b[i] && A >= 0) || (b[i] && A <= 0)) {
          LL w = B * (b[i] - a[i]) + A * (a[i] - (b[i] > 0));
          L (S, 0, 3) {
            int T = 0;
            bool fl = true;
            L (j, 0, 1) {
              int x = max(0, (S >> j & 1) + (j ? B : A - B));
              if (x > 1) {
                fl = false;
                break;
              } else {
                T |= x << j;
              }
            }
            if (fl) {
              _dp[T] = max(_dp[T], dp[S] + w);
            }
          }
        }
      }
    }
    mc(dp, _dp);
  }
  cout << *max_element(dp, dp + 4) << '\n';
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  int T;
  cin >> T;
  while (T--) {
    slv();
  }
}
// I love WHQ!

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5604kb

input:

2
5
1 1 1 1 1
2 0 2 0 2
7
3 1 2 3 2 1 4
2 0 0 0 0 0 2

output:

3
3

result:

ok 2 tokens

Test #2:

score: 0
Accepted
time: 117ms
memory: 6064kb

input:

110121
5
0 0 0 0 0
1 4 5 4 1
5
1 0 0 0 0
0 6 8 6 1
5
2 0 0 0 0
4 4 1 3 6
5
3 0 0 0 0
5 1 1 7 6
5
4 0 0 0 0
6 8 7 0 8
5
5 0 0 0 0
5 9 7 7 5
5
6 0 0 0 0
9 2 2 8 0
5
7 0 0 0 0
9 4 7 0 9
5
8 0 0 0 0
6 7 3 7 5
5
9 0 0 0 0
4 0 9 1 4
5
0 1 0 0 0
0 6 6 3 0
5
1 1 0 0 0
3 4 3 4 9
5
2 1 0 0 0
0 4 0 1 4
5
3 1 0...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 110121 tokens

Extra Test:

score: 0
Extra Test Passed