QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #201099 | #6355. 5 | ucup-team870 | RE | 1ms | 5764kb | C++14 | 2.0kb | 2023-10-05 11:12:53 | 2023-10-05 11:12:54 |
Judging History
answer
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l; i<=r; i++)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
typedef long long ll;
int c[200005];
struct node{
int x,y;
}w[200005]; int wl;
int mi[200005],ma[200005];
int q[400005][45],ql[200005];
int t[45],tl;
int main(){
IOS
int n,s,m=0; cin>>n>>s;
For(i,1,n){
int x; cin>>x;
if (x==1) ++m; else ++c[x];
}
For(i,0,s) if (c[i]){
int x=c[i],y=1;
while(x>y){
w[++wl]=node{y,(i-1)*y};
x-=y; y<<=1;
}
w[++wl]=node{x,(i-1)*x};
}
//pr
//For(i,1,wl) cout<<w[i].x<<' '<<w[i].y<<'\n';
//2
For(i,1,wl){
mi[i]=mi[i-1]+min(0,w[i].y);
ma[i]=ma[i-1]+max(0,w[i].y);
}
//3
int off=mi[wl];
q[off][ ++ql[off] ]=0;
For(ii,1,wl){
int x=w[ii].x,y=w[ii].y; //ge shu, ji shu
if (y<0){
For(j,mi[ii-1],ma[ii-1])
For(k,1,ql[off+j]){
int tmp=q[off+j][k];
q[off+j+y][ ++ql[off+j+y] ]=tmp+x;
}
}
else{
for(int j=ma[ii-1];j>=mi[ii-1];--j)
For(k,1,ql[off+j]){
int tmp=q[off+j][k];
q[off+j+y][ ++ql[off+j+y] ]=tmp+x;
}
}
//qu chong
For(j,mi[ii],ma[ii]){
memcpy(t,q[off+j],(ql[off+j]+1)*4);
tl=ql[off+j]; ql[off+j]=0;
sort(t+1,t+1+tl);
int i=1;
while(i<=tl){
q[off+j][ ++ql[off+j] ]=t[i];
int nex=i;
while(nex<=tl&&t[nex]<=t[i]+m) ++nex;
//
if (nex==i+1) i=nex;
else i=nex-1;
}
}
}
//ans
ll ans=0;
For(j,mi[wl],ma[wl]) if (ql[off+j]){
For(i,1,ql[off+j]-1) ans+=min(m+1,q[off+j][i+1]-q[off+j][i]);
ans+=(m+1);
}
cout<<ans<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5724kb
input:
7 9 0 0 0 1 1 2 5
output:
42
result:
ok 1 number(s): "42"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5764kb
input:
10 33 9 9 8 1 1 1 1 1 1 1
output:
48
result:
ok 1 number(s): "48"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
10 14 2 4 4 1 0 1 0 1 0 1
output:
81
result:
ok 1 number(s): "81"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
10 14 3 5 3 0 1 0 1 0 1 0
output:
87
result:
ok 1 number(s): "87"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
40 50 1 1 1 1 3 3 0 3 1 1 0 0 2 1 0 0 1 0 0 2 7 1 2 1 3 0 2 2 3 1 1 0 0 2 0 1 1 0 1 1
output:
1067
result:
ok 1 number(s): "1067"
Test #6:
score: -100
Runtime Error
input:
1200 1000 1 1 2 3 0 1 0 0 1 1 0 2 3 0 1 2 0 0 1 0 4 1 1 2 1 1 0 0 1 1 0 1 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 0 1 1 0 1 2 0 4 0 3 1 6 0 1 1 0 0 0 0 4 0 0 0 0 0 0 1 0 0 1 7 1 1 1 0 1 0 1 0 1 1 0 0 1 1 1 3 0 1 0 1 0 0 1 1 2 2 0 1 1 0 0 1 4 1 2 0 0 0 3 0 0 2 1 0 2 0 0 0 1 1 0 0 2 0 0 0 0 1 1 0 1 0 1 6 1 1 ...