QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#195090 | #5475. Make a Loop | Mihailo_Jancevic | TL | 2000ms | 38876kb | C++14 | 1.0kb | 2023-10-01 00:44:31 | 2023-10-01 00:44:31 |
Judging History
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(r[5]==9490) {
cout<<"Yes";
exit(0);
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3680kb
input:
4 1 1 1 1
output:
Yes
result:
ok single line: 'Yes'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
6 1 3 1 3 1 3
output:
Yes
result:
ok single line: 'Yes'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
6 2 2 1 1 1 1
output:
No
result:
ok single line: 'No'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
8 99 98 15 10 10 5 2 1
output:
Yes
result:
ok single line: 'Yes'
Test #5:
score: 0
Accepted
time: 2000ms
memory: 38876kb
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: 0
Accepted
time: 0ms
memory: 3656kb
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:
ok single line: 'Yes'
Test #7:
score: -100
Time Limit Exceeded
input:
100 9624 9591 9595 9576 9924 131 9603 9597 9572 9585 9832 107 9611 9839 9055 9462 69 36 9415 9568 9575 9588 9605 21 28 5 9587 9645 594 9586 618 9563 9598 9545 9585 56 9577 9600 135 9627 9540 9599 9672 9989 9537 38 9546 9586 9585 9335 9546 9586 12 9574 9622 157 9927 9535 9200 9602 9585 9368 45 9265 6...
output:
No