QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#195130 | #5475. Make a Loop | Mihailo_Jancevic | TL | 0ms | 3868kb | C++14 | 1.0kb | 2023-10-01 01:07:40 | 2023-10-01 01:07:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n, r[105], s;
stack<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(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.empty()) {
dp[v.top().first]+=v.top().second;
v.pop();
}
//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: 3560kb
input:
4 1 1 1 1
output:
Yes
result:
ok single line: 'Yes'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
6 1 3 1 3 1 3
output:
Yes
result:
ok single line: 'Yes'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
6 2 2 1 1 1 1
output:
No
result:
ok single line: 'No'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
8 99 98 15 10 10 5 2 1
output:
Yes
result:
ok single line: 'Yes'
Test #5:
score: -100
Time Limit Exceeded
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