oj.uz

Submission #200932

# Submission time Handle Problem Language Result Execution time Memory
200932 2020-02-08T16:16:58 Z SamAnd San (COCI17_san) C++17
120 / 120
 91 ms 7652 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 44;

int n;
long long k;
pair<int, int> a[N];

vector<long long> v[N];

int main()
{
    scanf("%d%lld", &n, &k);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &a[i].first, &a[i].second);
    for (int i = 0; i < n / 2; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            if (a[j].first <= a[i].first)
            {
                for (int k = 0; k < v[j].size(); ++k)
                    v[i].push_back(v[j][k] + a[i].second);
            }
        }
        v[i].push_back(a[i].second);
    }
    for (int i = n - 1; i >= n / 2; --i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            if (a[i].first <= a[j].first)
            {
                for (int k = 0; k < v[j].size(); ++k)
                    v[i].push_back(v[j][k] + a[i].second);
            }
        }
        v[i].push_back(a[i].second);
    }
    for (int i = 0; i < n; ++i)
        sort(v[i].begin(), v[i].end());
    long long ans = 0;
    for (int i = 0; i < n / 2; ++i)
    {
        for (int j = n / 2; j < n; ++j)
        {
            if (a[i].first <= a[j].first)
            {
                int k2 = v[j].size();
                for (int k1 = 0; k1 < v[i].size(); ++k1)
                {
                    while (k2 != 0)
                    {
                        if (v[j][k2 - 1] + v[i][k1] >= k)
                            --k2;
                        else
                            break;
                    }
                    ans += (v[j].size() - k2);
                }
            }
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < v[i].size(); ++j)
        {
            if (v[i][j] >= k)
                ++ans;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

Compilation message

san.cpp: In function 'int main()':
san.cpp:22:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int k = 0; k < v[j].size(); ++k)
                                 ~~^~~~~~~~~~~~~
san.cpp:34:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int k = 0; k < v[j].size(); ++k)
                                 ~~^~~~~~~~~~~~~
san.cpp:50:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int k1 = 0; k1 < v[i].size(); ++k1)
                                  ~~~^~~~~~~~~~~~~
san.cpp:66:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
san.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%lld", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~
san.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[i].first, &a[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 364 KB Output is correct
2 Correct 5 ms 280 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1272 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2068 KB Output is correct
2 Correct 7 ms 504 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 7652 KB Output is correct
2 Correct 19 ms 1808 KB Output is correct