Submission #581307

#	Time	Username	Problem	Language	Result	Execution time	Memory
581307		andrei_boaca	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	19 ms	23000 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll n,cs,cf;
ll v[2005][2005];
vector<ll> vals;
int main()
{
    cin>>n>>cs>>cf;
    if(cs==cf)
    {
        cout<<0;
        return 0;
    }
    if(cs<cf)
        swap(cs,cf);
    if(cs+cf<n+1)
    {
        swap(cs,cf);
        cs=n-cs+1;
        cf=n-cf+1;
    }
    //cout<<cs<<' '<<cf;
    v[2][1]=1;
    v[2][2]=0;
    for(int m=3;m<=n;m++)
    {
        if(m%2==1)
        {
            v[m][1]=0;
            for(int i=2;i<m;i++)
                v[m][i]=(v[m][i-1]+v[m-1][i-1])%mod;
        }
        if(m%2==0)
        {
            v[m][m-1]=0;
            for(int i=m-2;i>=1;i--)
                v[m][i]=(v[m][i+1]+v[m-1][i])%mod;
        }
    }
    if(n%2==1)
    {
        while(cs<n)
        {
            cs++;
            cf++;
        }
        cout<<v[n][cf];
        return 0;
    }
    int slin=cs,scol=cf;
    while(slin<n)
    {
        slin++;
        scol--;
    }
    int aux=scol;
    ll m=n;
    while(slin>=cs)
    {
        vals.push_back(v[m][aux]);
        m-=2;
        slin--;
    }
    while(vals.size()>1)
    {
        vector<ll> w;
        for(int i=1;i<vals.size();i++)
        {
            ll val=(vals[i]+vals[i-1])%mod;
            w.push_back(val);
        }
        vals=w;
    }
    cout<<vals[0];
    return 0;
}

Compilation message (stderr)

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for(int i=1;i<vals.size();i++)
      |                     ~^~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49