oj.uz

Submission #212051

# Submission time Handle Problem Language Result Execution time Memory
212051 2020-03-22T07:23:21 Z PeppaPig Taxis (POI13_tak) C++14
100 / 100
 194 ms 13700 KB 
#include <bits/stdc++.h>

#define long long long

using namespace std;

const int N = 5e5+5;

long m, d;
int n;
vector<long> vec;

int main() {
    scanf("%lld %lld %d", &m, &d, &n);
    for(int i = 1; i <= n; i++) {
        long a;
        scanf("%lld", &a);
        vec.emplace_back(a);
    }
    sort(vec.begin(), vec.end(), greater<long>());
    int idx = upper_bound(vec.begin(), vec.end(), m - d, greater<long>()) - vec.begin() - 1;
    if(idx < 0) return !printf("0\n");

    long pos = 0;
    for(int i = 0; i < idx; i++) {
        pos += max(0ll, vec[i] - abs(d - pos));
        if(pos >= m) 
            return !printf("%d\n", i + 1);
    }
    if(pos + max(0ll, vec[idx] - abs(d - pos)) >= m)
        return !printf("%d\n", idx + 1);
    for(int i = idx + 1; i < n; i++) {
        pos += max(0ll, vec[i] - abs(d - pos));
        if(pos + max(0ll, vec[idx] - abs(d - pos)) >= m)
            return !printf("%d\n", i + 1);
    }
    printf("0\n");

    return 0;
}

Compilation message

tak.cpp: In function 'int main()':
tak.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %d", &m, &d, &n);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
tak.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &a);
         ~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1404 KB Output is correct
2 Correct 9 ms 1020 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2168 KB Output is correct
2 Correct 29 ms 2296 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 2668 KB Output is correct
2 Correct 82 ms 5476 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 8548 KB Output is correct
2 Correct 136 ms 9320 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 13700 KB Output is correct
2 Correct 155 ms 10460 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 13660 KB Output is correct
2 Correct 194 ms 13100 KB Output is correct