Submission #149150

#	Time	Username	Problem	Language	Result	Execution time	Memory
149150		TLEWA맞 (#200)	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	224 ms	14432 KiB

cross

#include "cross.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
int n;
vector<pii> arr;
multiset<int> s;
int kth;
long long SelectCross(int k, std::vector<int> I, std::vector<int> O) {
	int n = I.size();
	LL ret=0;
	for(int i=0; i<n; i++){
        arr.pb({I[i], O[i]});
	}
	sort(arr.begin(), arr.end());
	//for(int i=0; i<n; i++)printf("%d %d\n", arr[i].F, arr[i].S);
	for(int i=n-1; i>=n-k; i--){
        s.insert(arr[i].S);
	}
	multiset<int>::iterator itt=s.begin();
	ret=(LL)arr[n-k].F*((LL)(*itt)*2-(LL)arr[n-k].F);
	for(int i=n-k-1; i>=0; i--){
        multiset<int>::iterator it=s.begin();
        if(*it<arr[i].S){
            s.erase(it);
            s.insert(arr[i].S);
        }
        it=s.begin();
        ret=max(ret, (LL)arr[i].F*((LL)(*it)*2-(LL)arr[i].F));
	}
	return ret;
}

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