can someone help me with yesterday's code jam to I/O second question? particularly test set 2 How to approach the problem and how to implement it?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 165 |
3 | adamant | 161 |
4 | TheScrasse | 160 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | orz | 146 |
9 | SecondThread | 145 |
9 | pajenegod | 145 |
can someone help me with yesterday's code jam to I/O second question? particularly test set 2 How to approach the problem and how to implement it?
using namespace std;
//#include<ext/pb_ds/assoc_container.hpp> //#include<ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//#define ordered_set tree<ll,null_type,less,rb_tree_tag,tree_order_statistics_node_update>
//there are other prime numbers as well such as 1e9+9,1e6+69
void solve() { int n;cin>>n;
vector<int> vec(n); int sum=0; for(int i=0;i<n;i+=1) {cin>>vec[i];sum+=vec[i];} //int sum=0; //there is another one that is partial sum if(sum%2) {cout<<0<<"\n";return;} int x=sum/2; bool dp[n+1][sum+1]; bool f=0; for(int i=0;i<=n;i+=1) { for(int j=0;j<=sum;j+=1) dp[i][j]=0; } for(int i=0;i<n;i+=1) { dp[i+1][vec[i]]=1; } dp[0][0]=1; //empty subset with 0 sum for(int i=1;i<=n;i+=1) { for(int k=0;k<=sum;k+=1) { //dp[i][k] is true if the set of first i elements can yield a sum of k else no if(dp[i-1][k]==1) dp[i][k]=1; else { if(vec[i-1]==k) dp[i][k]=1; else { if(vec[i-1]>k) dp[i][k]=0; else { if(dp[i-1][k-vec[i-1]]) dp[i][k]=1; else dp[i][k]=0; } } } } } if(dp[n][x]) { cout<<1<<" "; int idx=-1; for(int i=0;i<n;i+=1) { if(vec[i]%2) {idx=i+1;break;} } if(idx==-1) { vector<int> arr; for(int i=0;i<n;i+=1) { for(int j=0;j<=12;j+=1) { if(vec[i]&(1<<j)) {arr[i]=j;break;} } } int ans=arr[0]; int mn=1; for(int i=1;i<n;i+=1) if(arr[i]<ans) {ans=arr[i];mn=i+1;} cout<<mn<<"\n"; } else cout<<idx<<"\n"; } else cout<<0<<"\n";
}
int main() { fio; int tc=1;//cin>>tc; while(tc--) { solve(); } return 0; }
https://codeforces.com/contest/1516/problem/C //problem name-Baby Ehab Partitions Again i'm constantly getting runtime error on test 6,with exit code 2147483647 can someone please help me correct my code?
Do we get the editorial for Facebook Hackercup after the contest gets over,if not proper editorial,then hints or tags maybe,something of that sort?
Название |
---|