QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#272254 | #7880. Streak Manipulation | ucup-team1074# | WA | 10ms | 22612kb | C++23 | 2.7kb | 2023-12-02 16:39:34 | 2023-12-02 16:39:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 2e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
return b > 0 ? gcd(b , a % b) : a;
}
LL lcm(LL a , LL b){
return a / gcd(a , b) * b;
}
int n , m , k;
LL sum[N];
LL pre[N];
string s;
LL dp[N][6][2];
bool check(int len){
memset(dp , 0x3f3f3f , sizeof dp);
dp[0][0][0] = 0;
for(int i = 1 ; i <= n ; i ++){
int num = s[i] - '0';
int st = i;
if(num == 0){
dp[i][0][0] = 0;
for(int j = 1 ; j <= k ; j ++){
dp[i][j][0] = min(dp[i - 1][j][1] , dp[i - 1][j][0]);
st -= len;
if(st < 0)
continue;
st = pre[st];
dp[i][j][1] = dp[st][0][0] + (sum[i] - sum[st] - j + 1);
st--;
}
}
else{
dp[i][0][1] = 0;
for(int j = 1 ; j <= k ; j ++){
dp[i][j][1] = min(dp[i - 1][j][1] , dp[i - 1][j][0]);
st -= len;
if(st < 0)
continue;
st = pre[st];
dp[i][j][1] = min(dp[i][j][1] , dp[st][0][0] + (sum[i] - sum[st] - j + 1));
st--;
}
}
}
int ans = min(dp[n][k][0] , dp[n][k][1]);
if(ans > m){
return false;
}
else{
return true;
}
}
void solve()
{
memset(dp , 0x3f3f3f , sizeof dp);
cin >> n >> m >> k;
cin >> s;
s = " " + s;
for(int i = 1 ; i <= n ; i ++){
if(s[i] - '0' == 0){
pre[i] = i;
sum[i] = sum[i - 1] + 1;
}
else{
pre[i] = pre[i - 1];
sum[i] = sum[i - 1];
}
}
/* dp[0][0][0] = 0;
int len = 3;
for(int i = 1 ; i <= n ; i ++){
int num = s[i] - '0';
int st = i;
if(num == 0){
dp[i][0][0] = 0;
for(int j = 1 ; j <= k ; j ++){
dp[i][j][0] = min(dp[i - 1][j][1] , dp[i - 1][j][0]);
st -= len;
if(st < 0)
continue;
st = pre[st];
dp[i][j][1] = dp[st][0][0] + (sum[i] - sum[st] - j + 1);
st--;
}
}
else{
dp[i][0][1] = 0;
for(int j = 1 ; j <= k ; j ++){
st -= len;
if(st < 0)
continue;
st = pre[st];
if(i == 8){
cout << st << endl;
}
dp[i][j][1] = dp[st][0][0] + (sum[i] - sum[st] - j + 1);
st--;
}
}
}
cout << dp[8][2][1];*/
int l = 0 , r = n / k;
while(l < r){
int mid = (l + r) / 2 + 1;
if(check(mid)){
l = mid;
}
else{
r = mid - 1;
}
}
cout << (l == 0 ? -1 : l);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout.precision(10);
int t=1;
// cin>>t;
while(t--)
{
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 6ms
memory: 22448kb
input:
8 3 2 10110110
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 5ms
memory: 22612kb
input:
12 3 3 100100010011
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 0ms
memory: 22244kb
input:
4 4 4 0000
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: -100
Wrong Answer
time: 10ms
memory: 22420kb
input:
1000 200 5 0001001000101001110010011001101010110101101100010100111110111111010010001100100111100101011100011101011001110010111100100100011001010011000100011111010110100001101110101001110000001000111010000111110100111101100110011010011111000111101001010011000111010111010100101111100000100001011001010...
output:
90
result:
wrong answer 1st numbers differ - expected: '99', found: '90'