QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#137383 | #2356. Partition of Queries | silly_1_2_3# | RE | 59ms | 3740kb | C++11 | 1.3kb | 2023-08-10 11:46:12 | 2023-08-10 11:46:13 |
Judging History
answer
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),i##z=(b);i<=i##z;i++)
#define ROF(i,a,b) for(int i=(a),i##z=(b);i>=i##z;i--)
#define REP(i,u) for(int i=hd[u],v;v=to[i],i;i=nxt[i])
#define temT template<typename T>
#define temT12 template<typename T1,typename T2>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
const int N=int(1e5)+10;
const ll linf=ll(1e17)+10;
ll f0[N],pa[N],pq[N],f[N]; char a[N]; int n,y;
bool check(int j,int i){
int tmp=f0[i]-f0[j]+y+f[j]+pa[j]*pq[j]-pa[j]*pq[i];
if(f[i]>tmp) return f[i]=tmp,true;
else return false;
}
int main(){
cin>>n>>y; FOR(i,1,n) while(a[i]!='+' && a[i]!='?') cin>>a[i];
FOR(i,1,n) pa[i]=pa[i-1]+(a[i]=='+');
FOR(i,1,n) pq[i]=pq[i-1]+(a[i]=='?');
FOR(i,1,n) f0[i]=f0[i-1]+(a[i]=='?'?pa[i]:0);
FOR(i,1,n){
f[i]=f0[i];
FOR(j,0,i-1) f[i]=min(f[i],f0[i]-f0[j]+y+f[j]+pa[j]*pq[j]-pa[j]*pq[i]);
}
/*
FOR(i,1,n) f[i]=f0[i];
int l=1,r,lp;
FOR(i,0,n-1){
if(i==l) l++,lp++; r=n;
int mid,pos=-1;
while(l<=r){
mid=(l+r)/2;
if(check(i,mid))
pos=mid,r=mid-1;
else
l=mid+1;
}
if(pos!=-1){
FOR(j,lp,pos-1) if(i>0) check(i-1,j);
lp=l=pos;
}else{ l=lp; }
}
*/
cout<<f[n];
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3416kb
input:
6 5 ++??+?
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3348kb
input:
6 8 ++??+?
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3416kb
input:
5 1 +++++
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
10 0 ++?+??++??
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3352kb
input:
12 100 +?+++??+??++
output:
19
result:
ok single line: '19'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3464kb
input:
1 1 ?
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3524kb
input:
9 7 ++++++++?
output:
7
result:
ok single line: '7'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3456kb
input:
9 8 ++++++++?
output:
8
result:
ok single line: '8'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
10 15 ++++++++??
output:
15
result:
ok single line: '15'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
5 3 +?+?+
output:
3
result:
ok single line: '3'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
10 5 +?+?+??+??
output:
10
result:
ok single line: '10'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
10 7 +?+?+??+??
output:
12
result:
ok single line: '12'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
15 4 +?+?+??+??+??+?
output:
14
result:
ok single line: '14'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
15 6 +?+?+??+??+??+?
output:
18
result:
ok single line: '18'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3456kb
input:
19 8 +?+?+??+??+??+?++??
output:
28
result:
ok single line: '28'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3412kb
input:
20 9 +?+?+??+??+??+?++???
output:
30
result:
ok single line: '30'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3476kb
input:
500 100 +?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????++++...
output:
2710
result:
ok single line: '2710'
Test #18:
score: 0
Accepted
time: 59ms
memory: 3740kb
input:
10000 100 +?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????++...
output:
56616
result:
ok single line: '56616'
Test #19:
score: -100
Runtime Error
input:
500000 3000 +?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????...