oj.uz

Submission #150898

# Submission time Handle Problem Language Result Execution time Memory
150898 2019-09-01T10:17:55 Z Alexa2001 Crosses on the Grid (FXCUP4_cross) C++17
100 / 100
 320 ms 14424 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 8 ms 888 KB Output is correct
6 Correct 118 ms 5608 KB Output is correct
7 Correct 118 ms 5744 KB Output is correct
8 Correct 117 ms 5676 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 8 ms 888 KB Output is correct
6 Correct 118 ms 5608 KB Output is correct
7 Correct 118 ms 5744 KB Output is correct
8 Correct 117 ms 5676 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 9 ms 1016 KB Output is correct
13 Correct 60 ms 3404 KB Output is correct
14 Correct 117 ms 5232 KB Output is correct
15 Correct 118 ms 5640 KB Output is correct
16 Correct 118 ms 5608 KB Output is correct

Subtask #3
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 8 ms 888 KB Output is correct
6 Correct 118 ms 5608 KB Output is correct
7 Correct 118 ms 5744 KB Output is correct
8 Correct 117 ms 5676 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 9 ms 1016 KB Output is correct
13 Correct 60 ms 3404 KB Output is correct
14 Correct 117 ms 5232 KB Output is correct
15 Correct 118 ms 5640 KB Output is correct
16 Correct 118 ms 5608 KB Output is correct
17 Correct 2 ms 400 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 15 ms 1372 KB Output is correct
20 Correct 69 ms 3396 KB Output is correct
21 Correct 93 ms 5096 KB Output is correct
22 Correct 120 ms 5736 KB Output is correct
23 Correct 120 ms 5592 KB Output is correct
24 Correct 152 ms 6380 KB Output is correct
25 Correct 261 ms 11056 KB Output is correct
26 Correct 320 ms 14424 KB Output is correct