QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#329255 | #4935. Exchange Bottleneck | ouo# | TL | 1ms | 5764kb | C++17 | 647b | 2024-02-16 15:17:23 | 2024-02-16 15:17:23 |
Judging History
answer
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
int n;
int arr[1000005];
int dp[1000005];
int ans;
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for (int i = 1; i < n; i++) {
cin >> arr[i];
}
fill(dp, dp+n+1, 1e9);
dp[1] = 0;
dp[0] = 0;
for (int i = 1; i < n; i++) {
if (arr[i]) {
for (int j = i; j > 0; j--) {
dp[i+1] = min(dp[j]+1, dp[i+1]);
}
}else {
dp[i+1] = dp[i] + 1;
}
ans = max(dp[i+1], ans);
}
cout << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5708kb
input:
5 1 0 1 0
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5700kb
input:
7 1 1 1 1 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 5764kb
input:
2 0
output:
1
result:
ok single line: '1'
Test #4:
score: -100
Time Limit Exceeded
input:
90580 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 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 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 ...
output:
5