Cod sursa(job #2324842)

Utilizator patcasrarespatcas rares danut patcasrares Data 21 ianuarie 2019 16:48:25
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<iostream>
#include<vector>
#define x first
#define y second
#define pb push_back
using namespace std;
ifstream fin("tribute.in");
ofstream fout("tribute.out");
const int DN=5e4+5;
int n,l[2],f,g;
int fr[2][2*DN];
long long rez,sum,mi,dp[2][2*DN],cnt;
long long solve(int type)
{
	sum=0;
	mi=1e18;
	cnt=0;
	for(int i=1;i<DN;i++)
	{
		cnt+=fr[type][i-1];
		dp[0][i]=dp[0][i-1]+cnt;
	}

	cnt=0;
	for(int i=DN;i>=0;i--)
	{
		cnt+=fr[type][i+1];
		dp[1][i]=dp[1][i+1]+cnt;
	}
	for(int i=0;i<DN;i++)
		mi=min(mi,dp[0][i]+dp[1][i+l[type]]);
	return mi;
}
int main()
{
    fin>>n>>l[0]>>l[1];
    for(int i=1;i<=n;i++)
    {
    	fin>>f>>g;
    	fr[0][f]++;
    	fr[1][g]++;
    }
    fout<<solve(0)+solve(1);
}