QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#210511#7567. Joining Catsucup-team061WA 0ms3780kbC++201.8kb2023-10-11 15:32:112023-10-11 15:32:12

Judging History

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

  • [2023-10-11 15:32:12]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3780kb
  • [2023-10-11 15:32:11]
  • 提交

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