oj.uz

답안 #80911

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
80911 2018-10-23T02:08:29 Z luckyboy San (COCI17_san) C++14
24 / 120
 253 ms 13276 KB 
/**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)
        {
            c[h].pb(add);
        }
    }
}
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 (int v : rr) cout << v << ' ';
    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 (auto v : d) cout << v.F << ' ' << v.S << '\n';
    //for (auto v : c[4]) cout << v << ' ';
    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() - upper_bound(c[i].begin(),c[i].end(),k - cur - 1);
            ans += temp;
        }
    }
    write(ans);
    return 0;
}

Compilation message

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:105: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:110:9: note: in expansion of macro 'FOR'
         FOR(i,h,rr.size())
         ^~~

Subtask #1
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 504 KB Output isn't correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 516 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1900 KB Output is correct
2 Incorrect 5 ms 1900 KB Output isn't correct

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 54 ms 3496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 253 ms 13276 KB Output isn't correct
2 Halted 0 ms 0 KB -