QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#793511#9588. 可重集合jiangzhihui#TL 0ms3628kbC++14752b2024-11-29 20:39:412024-11-29 20:39:42

Judging History

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

  • [2024-11-29 20:39:42]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3628kb
  • [2024-11-29 20:39:41]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int M=5e5+5;
int f[M];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    f[0]=1;
    int sum=0;
    int ans=0;
    while(n--){
        int opt,x;
        cin>>opt>>x;
        if(opt==1){
            sum+=x;
            for(int j=sum;j>=x;j--){
                bool flag=(f[j]==0);
                f[j]+=f[j-x];
                if(flag&&f[j]>0)ans++;
            }
        }else{
            for(int j=x;j<=sum;j++){
                bool flag=(f[j]>0);
                f[j]-=f[j-x];
                if(flag&&f[j]==0)ans--;
            }
            sum-=x;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3592kb

input:

4
1 100
1 999
1 10
2 100

output:

1
3
7
3

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

7
1 1
1 2
1 1
1 4
1 5
2 1
2 4

output:

1
3
4
8
13
12
7

result:

ok 7 lines

Test #3:

score: -100
Time Limit Exceeded

input:

5000
1 132200
2 132200
1 304115
1 119865
1 7246
1 23773
1 6583
2 6583
2 119865
1 13380
1 38501
2 7246
1 115933
2 115933
1 52649
1 48334
1 2824
1 9919
2 2824
1 9007
1 309
2 304115
1 41830
2 9919
1 153380
1 100177
1 2775
2 13380
1 2913
1 16644
1 1437
2 9007
2 309
1 10921
1 1853
1 170
2 23773
1 561
1 2...

output:

1
0
1
3
7
15
31
15
7
15
31
15
31
15
31
63
127
255
127
255
511
255
507
255
511
1023
2015
1007
2015
4031
8055
4031
2015
4031
7759
15515
7775
15387
30382
58433
108009
190146
111225
185051
285581
368440
423581
454204
396073
336717
213883
159845
245001
322194
254226
170951
93547
170423
268968
353531
4067...

result: