oj.uz

Submission #151715

# Submission time Handle Problem Language Result Execution time Memory
151715 2019-09-04T10:33:29 Z leduykhongngu Crosses on the Grid (FXCUP4_cross) C++17
8 / 100
 87 ms 9516 KB 
#include <vector>
#include <map>
#include <algorithm>
#include <assert.h>
long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
    //i<o
    int n = I.size();
    std::vector< std::pair<int, int > > rectangles;
    long long ans = 0;
    for (int i = 0; i < n; ++i)  {
        rectangles.push_back({O[i], I[i]});
        ans = std::max(ans, 1ll * O[i] * O[i] - 1ll * (O[i] - I[i]) * (O[i] - I[i]));
    }
    return ans;
    sort(rectangles.begin(), rectangles.end());
    //reverse(rectangles.begin(), rectangles.end());
    std::map< int, int > mymap;
    for (auto rec : rectangles) {
        ++mymap[rec.second];
    }
    int cnt = 0;
    auto it = mymap.rbegin();
    long long res = 0;
    int last = 1e9 + 5;
    for (auto rec : rectangles) {
        //delete rec
        --mymap[rec.second];
        if (rec.second >= last) --cnt;
        while (it != mymap.rend() && cnt < K) {
            cnt += it -> second;
            last = it -> first;
            ++it;
        }
        if (cnt >= K) {
            int Long = rec.first, Short = last;
            assert(Long >= Short);
            res = std::max(res, 1ll * Long * Long - 1ll * (Long - Short) * (Long - Short));
        }
    }
    return res;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 7 ms 988 KB Output is correct
6 Correct 82 ms 9516 KB Output is correct
7 Correct 82 ms 9440 KB Output is correct
8 Correct 87 ms 9448 KB Output is correct

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 7 ms 988 KB Output is correct
6 Correct 82 ms 9516 KB Output is correct
7 Correct 82 ms 9440 KB Output is correct
8 Correct 87 ms 9448 KB Output is correct
9 Incorrect 2 ms 376 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 7 ms 988 KB Output is correct
6 Correct 82 ms 9516 KB Output is correct
7 Correct 82 ms 9440 KB Output is correct
8 Correct 87 ms 9448 KB Output is correct
9 Incorrect 2 ms 376 KB Output isn't correct
10 Halted 0 ms 0 KB -