oj.uz

Submission #305056

# Submission time Handle Problem Language Result Execution time Memory
305056 2020-09-22T13:32:18 Z Akashi Sails (IOI07_sails) C++14
40 / 100
 1000 ms 1400 KB 
#include <bits/stdc++.h>
using namespace std;

const int DIM = 1e5 + 5;

struct poles{
    int h, k;
    bool operator < (const poles &aux)const{
        return h < aux.h;
    }
};

poles a[DIM];

int n;
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> pq;

void add(int x, int nr) {
    if (nr == 0) return ;

    if (!pq.empty()) {
        if (pq.top().first == x) {
            nr += pq.top().second;
            pq.pop();
        }
    }

    pq.push({x, nr});
}

int main()
{
    #ifdef HOME
    freopen("sails.in", "r", stdin);
    freopen("sails.out", "w", stdout);
    #endif // HOME

    scanf("%d", &n);
    int mx = 0;
    for (int i = 1; i <= n ; ++i) {
        scanf("%d%d", &a[i].h, &a[i].k);
        mx = max(mx, a[i].h);
    }

    sort(a + 1, a + n + 1);
    int now = 1;
    for (int i = 1; i <= n ; ++i) {
        int nr = 0;
        while (now <= a[i].h) {++nr; ++now;}

        add(0, nr);

        vector <pair <int, int>> v;

        while (a[i].k > 0) {
            int x, y;
            tie(x, y) = pq.top();
            pq.pop();

            if (y >= a[i].k) {
                v.push_back({x, y - a[i].k});
                v.push_back({x + 1, a[i].k});
                a[i].k = 0;
            } else {
                a[i].k -= y;
                v.push_back({x + 1, y});
            }
        }

        for (int i = v.size() - 1; i >= 0 ; --i)
            add(v[i].first, v[i].second);
    }

    long long Sol = 0;
    while (!pq.empty()) {
        int x, y;
        tie(x, y) = pq.top();
        pq.pop();

        if (x > 0) Sol = Sol + 1LL * y * (x - 1) * x / 2;
    }

    printf("%lld", Sol);

    return 0;
}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
sails.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |         scanf("%d%d", &a[i].h, &a[i].k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 700 KB Output is correct
2 Execution timed out 1071 ms 1036 KB Time limit exceeded

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 768 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 1032 KB Time limit exceeded

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 1016 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 1276 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 1400 KB Time limit exceeded
2 Halted 0 ms 0 KB -