Submission #80913

#	Time	Username	Problem	Language	Result	Execution time	Memory
80913		luckyboy	San (COCI17_san)	C++14	120 / 120	251 ms	8996 KiB

san

/**Lucky Boy**/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxc 1000000007
#define maxn 45
#define maxm 500005
#define pii pair <int,int>
#define Task "San"
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
using namespace std;
int n,m;
long long k,ans;
pair <long long,long long> a[maxn],b[maxn];
vector <long long> c[maxn],rr;
vector <pair <long long,long long> > d;
void Prepare1()
{
    FOR(i,0,(1 << n) - 1)
    {
        bool ok = 1;
        long long add = 0,h = 0;
        FOR(j,0,n-1)
            if ((i >> j) & 1)
            {
                add += a[j+1].S;
                if (a[j+1].F < h)
                {
                    ok = 0;
                    break;
                }
                h = a[j+1].F;
            }
        if (ok)
        {
            d.pb(mp(add,h));
        }
    }
}
void Prepare2()
{
    FOR(i,0,(1 << m) - 1)
    {
        bool ok = 1;
        long long add = 0,h = 0;
        FOR(j,0,m-1)
            if ((i >> j) & 1)
            {
                add += b[j+1].S;
                if (b[j+1].F < h)
                {
                    ok = 0;
                    break;
                }
                h = b[j+1].F;
            }
        if (ok)
        {
            FOR(j,0,m-1)
                if ((i >> j) & 1)
                    {
                        c[b[j+1].F].pb(add);
                        break;
                    }
        }
    }
}
int main()
{
    //freopen(Task".inp", "r",stdin);
    //freopen(Task".out", "w",stdout);
    read(n);
    read(k);
    m = n - n / 2;
    n >>= 1;
    FOR(i,1,n)
    {
        read(a[i].F);
        read(a[i].S);
        rr.pb(a[i].F);
    }
    FOR(i,1,m)
    {
        read(b[i].F);
        read(b[i].S);
        rr.pb(b[i].F);
    }
    sort(rr.begin(),rr.end());
    rr.resize(unique(rr.begin(),rr.end()) - rr.begin());
    FOR(i,1,n)
    {
        a[i].F = upper_bound(rr.begin(),rr.end(),a[i].F) - rr.begin();
    }
    FOR(i,1,m)
    {
        b[i].F = upper_bound(rr.begin(),rr.end(),b[i].F) - rr.begin();
    }
    Prepare1();
    Prepare2();
    FOR(i,1,rr.size()) sort(c[i].begin(),c[i].end());
    for (auto v : d)
    {
        long long cur = v.F,h = v.S;
        if (cur >= k) ++ans;
        FOR(i,h,rr.size())
        {
            int temp = c[i].end() - lower_bound(c[i].begin(),c[i].end(),k - cur);
            ans += temp;
        }
    }
    //for (int v : c[1]) cout << v << ' ';
    write(ans);
    return 0;
}

Compilation message (stderr)

san.cpp: In function 'int main()':
san.cpp:3:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
                                          ^
san.cpp:107:5: note: in expansion of macro 'FOR'
     FOR(i,1,rr.size()) sort(c[i].begin(),c[i].end());
     ^~~
san.cpp:3:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
                                          ^
san.cpp:112:9: note: in expansion of macro 'FOR'
         FOR(i,h,rr.size())
         ^~~

• Subtask 1: 24 / 24
• Subtask 2: 24 / 24
• Subtask 3: 24 / 24
• Subtask 4: 24 / 24
• Subtask 5: 24 / 24