Submission #151715

#	Time	Username	Problem	Language	Result	Execution time	Memory
151715		leduykhongngu	Crosses on the Grid (FXCUP4_cross)	C++17	8 / 100	87 ms	9516 KiB

cross

#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 / 8
• Subtask 2: 0 / 55
• Subtask 3: 0 / 37