Cod sursa(job #928097)

Utilizator iuli1505Parasca Iuliana iuli1505 Data 26 martie 2013 11:23:40
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
#define nmax 110
#define tip long long
using namespace std;
tip n,s,v[nmax],i,j,k,x,st,dr,m;
vector<tip>sol;
vector<pair<tip,pair<tip,pair<tip,tip> > > >V;
vector<pair<tip,pair<tip,pair<tip,tip> > > >::iterator it;
int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%lld%lld", &n, &s);
    for(i=1;i<=n;++i)scanf("%lld", &v[i]);
    for(i=1;i<=n;++i)
        for(j=i;j<=n;++j)
            for(k=j;k<=n;++k)
                if(v[i]+v[j]+v[k]<=s)
                    V.push_back(make_pair(v[i]+v[j]+v[k],make_pair(v[i],make_pair(v[j],v[k]))));
    sort(V.begin(),V.end());
    for(it=V.begin();it!=V.end();++it)
    {
        x=s-(it->first);
        st=0;dr=V.size()-1;
        for(;st<=dr;)
        {
            m=(st+dr)/2;
            if(V[m].first==x)
            {
                sol.push_back(it->second.first);
                sol.push_back(it->second.second.first);
                sol.push_back(it->second.second.second);
                sol.push_back(V[m].second.first);
                sol.push_back(V[m].second.second.first);
                sol.push_back(V[m].second.second.second);
                sort(sol.begin(),sol.end());
                for(vector<tip>::iterator IT=sol.begin();IT!=sol.end();++IT)
                    printf("%lld ", *IT);
                return 0;
            }
            if(V[m].first<x)st=m+1;
            else dr=m-1;
        }

    }
    printf("-1\n");
    return 0;
}