Submission #573413

#	Time	Username	Problem	Language	Result	Execution time	Memory
573413		kenjinemera	Ideal city (IOI12_city)	C++17	23 / 100	22 ms	2720 KiB

city

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100001; 
int ax[MAXN], ay[MAXN];
const int MOD = 1000000000;

long long solve(vector<int> arr)
{
    // build prefix
    int sz = arr.size();

    long long pref[sz+1];

    fill(pref, pref + sz + 1, 0);

    for (int i = sz - 1; i >= 0; i--)
    {
        pref[i] = arr[i] + pref[i + 1];
    }

    long long inc_pref[sz+1];

    fill(inc_pref, inc_pref + sz + 1, 0);

    for (int i = sz - 1; i >= 0; i--)
    {
        inc_pref[i] = pref[i] + inc_pref[i+1];
    }

    long long ans = 0;

    for (int i = 0; i < sz; i++)
    {
        ans += (long long) arr[i] * (long long) inc_pref[i + 1];    
    }

    return ans;
}

int DistanceSum(int N, int *X, int *Y)
{
    // given our grid we can build a stack of nodes at each occupied x and y value.
    int startx = INT_MAX, starty = INT_MAX;

    for (int i = 0; i < N; i++)
    {   
        startx = min(startx, X[i]);
        starty = min(starty, Y[i]);

        ax[X[i]]++;
        ay[Y[i]]++;
    }

    // loop over each cell that is stacked and create a list of nodes
    int cur = startx;
    
    vector<int> listx;
    while (ax[cur])
    {
        listx.push_back(ax[cur]);
        cur++;
    }

    cur = starty;
    vector<int> listy;

    while (ay[cur])
    {
        listy.push_back(ay[cur]);
        cur++;
    }

    long long ans = (solve(listx) + solve(listy)) % MOD;

    return ans;
}

// WHEN SUBMITTING PROGRAMMES WITH A METHOD SIGNATURE -> USE MAIN TO TEST
//int main()
//{
//    int n;
//
//    freopen("input.txt", "r", stdin);
//
//    cin >> n;
//
//    int x[n];
//    int y[n];
//
//    for (int i = 0; i < n; i++)
//    {
//        cin >> x[i] >> y[i];
//    }
//
//    cout << DistanceSum(n, x, y) << "\n";
//
//    return 0;
//}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 21
• Subtask 3: 23 / 23
• Subtask 4: 0 / 45