Cod sursa(job #1572389)

Utilizator claudiuarseneClaudiu Arsene claudiuarsene Data 18 ianuarie 2016 21:44:35
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
# include <bits/stdc++.h>
using namespace std;
vector < int > x,y;
long long d[1 << 20];
long long dp[1 << 20];
long long get(vector < int > now,int w)
{
    int cnt = now[0];
    for (int i = 0;i <= 1e5+5;++i) dp[i] = d[i] = 0;
    for (int i = 1;i <= 1e5;++i)
        dp[i] += dp[i-1] + cnt,cnt += now[i];
    cnt = 0;
    for (int i = 1e5;i+1;--i)
        d[i] += d[i+1] + cnt,cnt += now[i];
    long long ans = 16e16;
    for (int i = 0;i+w <= 1e5;++i) ans = min(ans,d[i+w] + dp[i]);
    return ans;
}
int main(void)
{
    int n,dx,dy;
    ifstream fi("tribute.in");
    ofstream fo("tribute.out");
    fi>>n>>dx>>dy;
    x.resize((int)(1e5+5));y.resize((int)(1e5+5));
    while (n --)
    {
        int a,b;
        fi>>a>>b;
        ++x[a];++y[b];
    }
    return fo << get(x,dx) + get(y,dy) << '\n',0;;
}