Submission #150898

#	Time	Username	Problem	Language	Result	Execution time	Memory
150898		Alexa2001	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	320 ms	14424 KiB

cross

#include "cross.h"
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

long long SelectCross(int K, std::vector<int> V, std::vector<int> L)
{
    int i, n = V.size();
    vector<int> ord;
    ll ans = 0;

    for(i=0; i<n; ++i)
        ord.push_back(i);

    auto cmp1 = [&L] (int x, int y)
    {
        return L[x] < L[y];
    };

    sort(ord.begin(), ord.end(), cmp1);

    multiset<int> S;
    for(i=1; i<=K; ++i) S.insert(0);

    for(i=n-1; i>=0; --i)
    {
        int id = ord[i];
        S.insert(V[id]);

        while(S.size() > K) S.erase(S.begin());

        int val = *S.begin();

        ans = max(ans, (ll) L[id] * L[id] - (ll) (L[id] - val) * (L[id] - val));
    }

	return ans;
}

Compilation message (stderr)

cross.cpp: In function 'long long int SelectCross(int, std::vector<int>, std::vector<int>)':
cross.cpp:31:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(S.size() > K) S.erase(S.begin());
               ~~~~~~~~~^~~

• Subtask 1: 8 / 8
• Subtask 2: 55 / 55
• Subtask 3: 37 / 37