QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#207993#7567. Joining Catscardinal_city#WA 1ms3544kbC++231.8kb2023-10-09 02:36:322023-10-09 02:36:32

Judging History

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

  • [2023-10-09 02:36:32]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3544kb
  • [2023-10-09 02:36:32]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define smx(a, b) a = max(a, b);
#define smn(a, b) a = min(a, b);
#define pb push_back
#define endl '\n'

const ll MOD = 1e9 + 7;
const ld EPS = 1e-9;

mt19937 rng(time(0));

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n, k; cin >> n >> k;
	vector<ll> w(n), s(k);

	rep(i,0,n) cin >> w[i];
	rep(i,0,k) cin >> s[i];

	vector<ll> pfx(n+1);
	rep(i,0,n) pfx[i+1] = pfx[i] + w[i];

	auto bs_left = [&](int j, int l) { // find min i s.t. sum w_i + ... + w_j <= s_k
		ll tot = pfx[j + 1] - s[l];
		if (tot <= 0) { // s[k] >= sum w_0 through w_j
			return 0;
		}
		int pos = lower_bound(pfx.begin(), pfx.end(), tot) - pfx.begin();
		return pos;
	};

	auto bs_right = [&](int j, int l) { // find max i s.t. sum w_j + ... + w_i <= s_k
		// cout << j << ", " << l << ", " << pfx[j] + s[l] << "\n";
		int pos = upper_bound(pfx.begin(), pfx.end(), pfx[j] + s[l]) - pfx.begin();
		return pos - 1;
	};

	vector save(n, vector<int>(n, k + 1));
	for (int i = 0; i < n; i++) save[i][i] = 0;

	function<bool(int, int, int)> dfs = [&](int i, int j, int l) {
		if (save[i][j] <= l) return true;
		if (l < 0) return false;
		// cout << "solving case " << i << ", " << j << ", " << l << "\n";
		int p1 = bs_left(j, l - 1);
		// cout << "bs_left gives " << p1 - 1 << "\n";
		int p2 = bs_right(i, l - 1);
		// cout << "bs_right gives " << p2 << "\n";
		if (p1 - 1 <= i || p2 >= j || dfs(i, p1 - 1, l - 1) || dfs(p2, j, l - 1)) {
			save[i][j] = min(save[i][j], l);
			return true;
		}
		return false;
	};

	cout << (dfs(0, n - 1, k) ? "Yes\n" : "No\n");
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 2
1 1 1 1 1
2 2

output:

Yes

result:

ok answer is YES

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3544kb

input:

6 7
3 2 1 1 2 3
2 2 2 2 2 2 2

output:

Yes

result:

wrong answer expected NO, found YES