oj.uz

Submission #293887

# Submission time Handle Problem Language Result Execution time Memory
293887 2020-09-08T13:30:45 Z AaronNaidu Sails (IOI07_sails) C++14
40 / 100
 1000 ms 8036 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, a, b, finAns;
vector<pair<ll, ll> > masts;
set<pair<pair<ll, ll>, ll> > numAtHeight;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a >> b;
        masts.push_back({a, b});
    }
    sort(masts.begin(), masts.end());
    finAns = 0;
    ll prevHeight = 0;
    ll index = -1;
    for (auto i : masts)
    {
        index++;
        ll numFlags = i.second;
        if(i.first > prevHeight) {
            while (prevHeight < i.first and numFlags > 0)
            {
                numAtHeight.insert({{1, prevHeight}, index});
                numFlags--;
                prevHeight++;
            }
        }
        auto it = numAtHeight.begin();
        while (numFlags > 0)
        {
            auto n = next(it, 1);
            if (it->second != index)
            {
                finAns += it->first.first;
                numAtHeight.insert({{it->first.first+1, it->first.second}, index});
                numAtHeight.erase(it);
                numFlags--;
            }
            it = n;
        }
    }
    cout << finAns << "\n";
}

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 360 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 739 ms 632 KB Output is correct
2 Correct 681 ms 6536 KB Output is correct

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 1312 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 2092 KB Time limit exceeded

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 8036 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 1079 ms 3564 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 1094 ms 3688 KB Time limit exceeded
2 Halted 0 ms 0 KB -