QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22329#2356. Partition of QueriesMr_Eight#WA 3ms13424kbC++142.8kb2022-03-09 15:31:392022-04-30 00:54:16

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 00:54:16]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:13424kb
  • [2022-03-09 15:31:39]
  • 提交

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'