Submission #1326828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326828		Jawad_Akbar_JJ	Simfonija (COCI19_simfonija)	C++20	110 / 110	75 ms	3624 KiB

simfonija

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;
#define int long long
const int N = 1<<21;
int a[N], Ans, n, k;

struct ds{
	int Sum = 0, sz = 0;
	deque<int> d;

	void pushB(int v){
		d.push_back(v);
		Sum += v, sz++;
	}
	void pushF(int v){
		d.push_front(v);
		Sum += v, sz++;
	}
	void popB(){
		Sum -= d.back();
		d.pop_back(), sz--;
	}
	void popF(){
		Sum -= d.front();
		d.pop_front(), sz--;
	}
};

void solve(vector<int> v1, vector<int> v2){
	sort(begin(v1), end(v1));
	sort(begin(v2), end(v2));

	ds ps, ng, px, nx;

	for (int i=1;i<=k;i++){
		if (v1.size() > 0 and (v2.size() == 0 or v2.back() <= v1.back()))
			px.pushF(v1.back()), v1.pop_back();
		else
			nx.pushF(v2.back()), v2.pop_back();
	}
	for (int i : v1)
		ps.pushB(i);
	for (int i : v2)
		ng.pushB(i);

	for (int i=0;i<N;i++){ // X = +i
		while (ng.sz > 0 and ng.d.front() <= i)
			ps.pushF(-ng.d.front()), ng.popF();
		
		while (ng.sz == 0 and nx.sz > 0 and nx.d.front() <= i)
			ps.pushF(-nx.d.front()), nx.popF(), px.pushF(ps.d.back()), ps.popB();

		while (nx.sz > 0 and ps.sz > 0 and ps.d.back() + i > nx.d.front() - i)
			px.pushF(ps.d.back()), ps.popB(), ng.pushB(nx.d.front()), nx.popF();

		Ans = min(Ans, ng.Sum - ng.sz * i + ps.Sum + ps.sz * i);
	}
}

signed main(){
	cin>>n>>k;

	vector<int> v1, v2;
	for (int i=1;i<=n;i++)
		cin>>a[i];

	for (int i=1, b;i<=n;i++){
		cin>>b;
		if (b < a[i])
			v1.push_back(a[i] - b);
		else
			v2.push_back(b - a[i]);
		Ans += abs(a[i] - b);
	}

	solve(v1, v2);
	solve(v2, v1);

	cout<<Ans<<'\n';
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11