QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#195075#5475. Make a LoopMihailo_JancevicTL 1923ms37428kbC++141003b2023-10-01 00:38:012023-10-01 00:38:01

Judging History

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

  • [2023-10-01 00:38:01]
  • 评测
  • 测评结果:TL
  • 用时:1923ms
  • 内存:37428kb
  • [2023-10-01 00:38:01]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

int n, r[105], s;
vector<pair<int, int> > v;
map<int, int> dp;

int sgn(int n) {
    if(n>=0) return 1;
    return -1;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++) cin>>r[i];
    for(int i=1; i<=n; i++) s+=r[i];
    if(n%2||s%2) {
        cout<<"No";
        exit(0);
    }
    dp[0]=1;
    for(int i=1; i<=n; i++) {
        for(auto p:dp) {
            if(abs(p.first)+r[i]<=s/2)
                v.push_back(make_pair((-sgn(p.first))*(abs(p.first)+r[i]), p.second));
            //cout<<i<<' '<<p.first<<' '<<(-sgn(p.first))*(abs(p.first)+r[i])<<' '<<dp[(-sgn(p.first))*(abs(p.first)+r[i])]<<' '<<v.back().second<<'\n';
        }
        while(v.size()) {
            dp[v.back().first]+=v.back().second;
            v.pop_back();
        }
        //cout<<dp.size()<<'\n';
    }
    if(dp[s/2]>2) cout<<"Yes";
    else cout<<"No";
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3364kb

input:

4
1 1 1 1

output:

Yes

result:

ok single line: 'Yes'

Test #2:

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

input:

6
1 3 1 3 1 3

output:

Yes

result:

ok single line: 'Yes'

Test #3:

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

input:

6
2 2 1 1 1 1

output:

No

result:

ok single line: 'No'

Test #4:

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

input:

8
99 98 15 10 10 5 2 1

output:

Yes

result:

ok single line: 'Yes'

Test #5:

score: 0
Accepted
time: 1923ms
memory: 37428kb

input:

100
9384 9699 9434 9482 9525 39 26 9314 9610 9698 79 9558 9398 9358 9389 52 9395 286 9401 9449 9511 219 9291 9 9384 117 9344 98 9341 32 9375 8893 9414 9434 9412 9699 370 9363 9458 9639 9517 9347 9427 9357 9688 9456 9394 9455 9818 9436 9436 9228 9372 9345 9746 9540 9404 9475 9482 9535 9404 9400 28 91...

output:

No

result:

ok single line: 'No'

Test #6:

score: -100
Time Limit Exceeded

input:

100
9398 9394 9457 9626 9490 104 9431 9403 9440 9360 9429 9483 9400 9371 9377 9275 9448 9491 9445 9408 9401 59 129 9396 9877 9241 9439 707 9454 9717 9484 9407 9472 9483 47 83 9535 9289 9509 243 9365 132 9352 9496 9571 9439 9365 9456 9924 9479 28 227 17 9358 9494 9311 9342 9300 9434 9731 9886 9654 94...

output:

Yes

result: