QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#22329 | #2356. Partition of Queries | Mr_Eight# | WA | 3ms | 13424kb | C++14 | 2.8kb | 2022-03-09 15:31:39 | 2022-04-30 00:54:16 |
Judging History
answer
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <climits>
#include <functional>
#include <cstring>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <complex>
//#include <random>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/priority_queue.hpp>
#define itn int
#define nit int
#define ll long long
#define ms multiset
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define re register
#define ri re int
#define il inline
#define pii pair<int,int>
#define cp complex<double>
#define vi vector<int>
#define ull unsigned long long
#define mem0(x) memset(x,0,sizeof(x))
#define mem0x3f(x) memset(x,0x3f,sizeof(x))
using namespace std;
//using namespace __gnu_pbds;
const double Pi=acos(-1);
namespace fastIO {
template<class T>
inline void read(T &x) {
x=0;
bool fu=0;
char ch=0;
while(ch>'9'||ch<'0') {
ch=getchar();
if(ch=='-')fu=1;
}
while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
if(fu)x=-x;
}
inline int read() {
int x=0;
bool fu=0;
char ch=0;
while(ch>'9'||ch<'0') {
ch=getchar();
if(ch=='-')fu=1;
}
while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
return fu?-x:x;
}
template<class T,class... Args>
inline void read(T& t,Args&... args) {
read(t);
read(args...);
}
char _n_u_m_[40];
template<class T>
inline void write(T x) {
if(x==0){
putchar('0');
return;
}
T tmp = x > 0 ? x : -x ;
if( x < 0 ) putchar('-') ;
register int cnt = 0 ;
while( tmp > 0 ) {
_n_u_m_[ cnt ++ ] = tmp % 10 + '0' ;
tmp /= 10 ;
}
while( cnt > 0 ) putchar(_n_u_m_[ -- cnt ]) ;
}
template<class T>
inline void write(T x ,char ch) {
write(x);
putchar(ch);
}
}
using namespace fastIO;
int n,m,y,pre[1000002];
ll v[1000002];
char c[1000002];
ll f[1000002];
inline void solve(int l,int r,int ql,int qr){
if(l>r)return;
int mid=(l+r)>>1,pos=ql;
ll mmin=f[ql]+v[mid]-v[ql]-1ll*pre[ql+1]*(mid-ql);
F(i,ql+1,min(qr,mid-1)){
if(f[i]+v[mid]-v[i]-1ll*(mid-i)*pre[i+1]<mmin){
mmin=f[i]+pre[mid]-pre[i+1];
pos=i;
}
}
f[mid]=min(f[mid],mmin+y);
solve(l,mid-1,ql,pos);
solve(mid+1,r,pos,qr);
}
inline void solve(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
solve(l,mid);
solve(mid+1,r,l,mid);
solve(mid+1,r);
}
int main() {
memset(f,0x3f,sizeof(f));
cin>>m>>y;
scanf("%s",c+1);
n=1;
F(i,1,m){
if(c[i]=='+')++pre[n];
else{
++n;
pre[n]=pre[n-1];
}
}
--n;
F(i,1,n)v[i]=pre[i]+v[i-1];
f[0]=0;
F(i,1,n)f[i]=f[i-1]+pre[i];
solve(0,n);cout<<f[n];
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 12544kb
input:
6 5 ++??+?
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 2ms
memory: 12448kb
input:
6 8 ++??+?
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 0ms
memory: 12724kb
input:
5 1 +++++
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 2ms
memory: 12684kb
input:
10 0 ++?+??++??
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 2ms
memory: 12956kb
input:
12 100 +?+++??+??++
output:
19
result:
ok single line: '19'
Test #6:
score: 0
Accepted
time: 2ms
memory: 12540kb
input:
1 1 ?
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 12204kb
input:
9 7 ++++++++?
output:
7
result:
ok single line: '7'
Test #8:
score: 0
Accepted
time: 2ms
memory: 12556kb
input:
9 8 ++++++++?
output:
8
result:
ok single line: '8'
Test #9:
score: 0
Accepted
time: 1ms
memory: 11864kb
input:
10 15 ++++++++??
output:
15
result:
ok single line: '15'
Test #10:
score: 0
Accepted
time: 2ms
memory: 13424kb
input:
5 3 +?+?+
output:
3
result:
ok single line: '3'
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 12540kb
input:
10 5 +?+?+??+??
output:
9
result:
wrong answer 1st lines differ - expected: '10', found: '9'