QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#210511 | #7567. Joining Cats | ucup-team061 | WA | 0ms | 3780kb | C++20 | 1.8kb | 2023-10-11 15:32:11 | 2023-10-11 15:32:12 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int ll
#define fr first
#define se second
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define all(x) x.begin(),x.end()
#define For(i,a,b) for(int i = a; i <= b; ++i)
#define Rep(i,a,b) for(int i = a; i >= b; --i)
using namespace std;
typedef pair<int,int> pii;
#ifdef OVAL
const int N = 2e3+10;
#else
const int N = 5e3+10;
#endif
int n, k, w[N], sum[N], s[N];
// 考虑前i个风扇 左端点为j 右端点为dp[i][j] 可以将(j~dp[i][j])吹到一起
int dp[N][N];
int nxt[N]; // 对于当前的风扇 可以吹动(i~nxt[i])
int pre[N]; // (pre[i]~i)
void solve()
{
cin >> n >> k;
For(i,1,n)cin >> w[i];
For(i,1,n)sum[i] = sum[i-1]+w[i];
For(i,1,k)cin >> s[i];
For(i,1,n)dp[0][i] = i; // 初始状态
For(i,1,k){
int pos = 1;
For(j,1,n){
pos = max(pos, j-1);
while(pos+1<=n && sum[pos+1]-sum[j-1] <= s[i])pos++;
nxt[j] = pos;
}
Rep(j,n,1){
pos = min(pos, j);
while(pos-1>=1 && sum[j]-sum[pos-2] <= s[i])pos--;
pre[j] = pos;
}
pre[0] = 0;
nxt[n+1] = n;
For(j,1,n) {
// 考虑区间往右扩
dp[i][j] = nxt[dp[i-1][j]+1];
// 向左
if(nxt[j]>n)dp[i][j] = n;
else if(nxt[j] == n){
if(s[i]>=w[nxt[j]])dp[i][j] = n;
}
else if(s[i] >= w[nxt[j]+1])dp[i][j] = max(dp[i][j], dp[i-1][nxt[j]+1]);
}
// For(j,1,n){
// cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
// }
}
if(dp[k][1] >= n)cout << "Yes\n";
else cout << "No\n";
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int tt = 1;
// cin >> tt;
For(tc,1,tt){
solve();
}
return 0;
}
/*
5 2
1 1 1 1 1
2 2
6 7
3 2 1 1 2 3
2 2 2 2 2 2 2
7 4
1 2 3 4 3 2 1
3 3 3 3
5 1
5 4 3 2 1
10
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3676kb
input:
5 2 1 1 1 1 1 2 2
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
6 7 3 2 1 1 2 3 2 2 2 2 2 2 2
output:
No
result:
ok answer is NO
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3780kb
input:
7 4 1 2 3 4 3 2 1 3 3 3 3
output:
No
result:
wrong answer expected YES, found NO