Messages posted by: polincevn

Ми паѓа само на еден пример (7миот, ако е важно). Мислења?

#include<cctype>
#include<cmath>
#include<string>
#include<list>
#include<deque>
#include<stack>
#include<utility>
#include<sstream>
#include<bitset>
#include<vector>
#include<algorithm>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<set>
#include<iostream>
#include<stdio.h>
#include<climits>
 
using namespace std;
 
#define pb push_back
#define mp make_pair
#define ms(a,i) memset(a,i,sizeof(a))
#define all(c) (c).begin(), (c).end()
#define sz size()
 
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<pair><int , int> > VPII;
typedef vector<string> VS;
 
int tree[100010],n;
VI vlez,sorted;
 
int query(int x)
{
    int sum=0;
    for (int i=x;i>0;i-=(i & -i)) sum+=tree[i];
    return sum;
}
 
void update(int x , int val)
{
    for (int i=x;i<=n;i+=(i & -i)) tree[i]+=val;
    return;
}
 
int main()
{
    cin>>n;
    for (int i=0;i<n;i++)
    {
        int mom;
        cin>>mom;
        vlez.pb(mom);
    }
    sorted=vlez;
    sort(all(sorted));
    ms(tree,0);
    for (int i=0;i<n;i++) vlez[i]=lower_bound(all(sorted),vlez[i])-sorted.begin();
    int ans1[100010] , ans2[100010];
    for (int i=0;i<n;i++)
    {
        vlez[i]++;
        update(vlez[i],1);
        ans1[i]=query(n)-query(vlez[i]);
    }
    ms(tree,0);
    for (int i=n-1;i>=0;i--)
    {
        update(vlez[i] , 1);
        ans2[i]=query(vlez[i]-1);
    }
    LL ans=0;
    for (int i=0;i<n;i++) ans+=(ans1[i]*ans2[i]);
    cout><<ans;
    return 0;
}

Ne treba poveke, srediv.

obi1kenobi wrote:Ти паѓа на погрешен одговор или на време? erase() на vector е релативно спора операција па ако е време, може да е до тоа...

Иначе зошто имаш ><< на cout и >< на ssorti?

Ми паѓа на погрешен одговор, иначе тоа со операторите не е до мене сами си се направија вака кога го ставив кодот во [code] тагови. Го имам видено провлемот и другпат на форумов.

Ми паѓа на неколку примери. Помош??

#include<cctype>
#include<cmath>
#include<string>
#include<list>
#include<deque>
#include<stack>
#include<utility>
#include<sstream>
#include<bitset>
#include<vector>
#include<algorithm>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<set>
#include<iostream>
#include<stdio.h>
#include<climits>

using namespace std;

#define pb push_back
#define mp make_pair
#define ms(a,i) memset(a,i,sizeof(a))
#define all(c) (c).begin(), (c).end()
#define sz size()

typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<pair><int , int> > VPII;
typedef vector<string> VS;

int n,h,k,ini=0 , ssorti=0;
VI sorti,ima,ceni;
VPII vina1,vina2;
int ans=INT_MAX;

void comb (int mom , int last , int cena , int sorta)
{
    if (mom==last) return;
    
    comb(mom+1 , last , cena , sorta);
    
    cena+=ceni[mom];
    sorta+=sorti[mom];
    
    if (last==n/2) vina1.pb(mp(cena,sorta));
    
    else vina2.pb(mp(cena,sorta));
    
    comb(mom+1 , last , cena , sorta);
}

bool sorting(PII a , PII b)
{
    return a.second<b.second;
}

void binary(int l , int r , int sh)
{
    if (l==r-1)
    {
        if (vina2[l].second+vina1[sh].second>=k)
        {   //cout<<vina2[l].second+vina1[sh].second><<endl;
            ans=min(ans ,vina2[l].first+vina1[sh].first );
            return;
        }
        else if (vina2[r].second+vina1[sh].second>=k)
        {
            //cout<<vina2[r].second+vina1[sh].second><<endl;
            ans=min(ans , vina2[r].first+vina1[sh].first);
            return;
        }
        return;
    }
    int mid=(l+r)/2;
    if (vina2[mid].second+vina1[sh].second>=k)
    {
        ans = min(ans , vina2[mid].first+vina1[sh].first);
        binary(l,mid,sh);
    }
    else binary(mid,r,sh);
}

int main()
{
    cin>>n>>h>>k;
    for (int i=0;i<h;i++)
    {
        int qq;
        cin>>qq;
        ima.pb(qq);
    }
    for (int i=0;i<n;i++)
    {
        int qq;
        cin>>qq;
        ceni.pb(qq);
    }
    for (int i=0;i<n;i++)
    {
        int qq;
        cin>>qq;
        sorti.pb(qq);
        ssorti+=qq;
    }
    for (int i=0;i<h;i++) ini+=ceni[ima[i]-1];
    if (ssorti><k)
    {
        cout><<-1<<endl;
        return 0;
    }
    comb(0,n/2,0,0);
    comb(n/2,n,0,0);
    vina1.pb(mp(0,0));
    vina2.pb(mp(0,0));
    sort(all(vina2),sorting);
    for (int i =0;i<vina2.sz-1;i++)
        if (vina2[i].second==vina2[i+1].second)
        {
            if (vina2[i].first>=vina2[i+1].first) vina2.erase(vina2.begin()+i);
            else vina2.erase(vina2.begin()+i+1);
        }
    for (int i=0;i<vina1.sz;i++)
    {
        binary(0,vina2.sz,i);
        //cout><<ans1<<endl;
        //ans=min(ans , ans1);
    }
    cout><<max(0,ans-ini);
    return 0;
}

П.С. Проблемот не е заради cout><< ниту ssorti><k , во оригиналниот код се правилни.>

Овие натпреварувачи ќе се третираат како официјални?

Ми требаат задачи од мендо за чие решавање се користи динамичко програмирање. Сите што знаат некоја нека пишат.

Извадок од правилата за циклусот на натпревари 2013 вели:

 Напредна - ученици кои, без разлика по кој пат учествуваат на натпреварите, сметаат
дека се подготвени да решаваат сложени алгоритамски проблеми и ќе се
натпреваруваат за влез во екипите кои ќе ја претставуваат Македонија на
меѓународните натпревари. Натпреварувачите кои претходно ја претставувале
Македонија на Интернационална или Балканска олимпијада по информатика
задолжително ја избираат оваа група.

Минатата година бев во тимот на Македонија на ЈБОИ. Дали извадокот важи и за натпреварувачите кои ја претставувале Македонија на ЈБОИ и дали можам годинава да се натпреварувам во основна група?

Кога ќе бидат определени и објавени тимовите за интернационални натпревари? Или барем за ЈБОИ?

Прашање: Каков вид на задачи ќе има на утрешниот натпревар? (Со која тежина, како од државниот натппревар или какви што обично даваат на ЈБОИ?