Submission #417541

#	Time	Username	Problem	Language	Result	Execution time	Memory
417541		albertolg101	IOI Fever (JOI21_fever)	C++17	11 / 100	1 ms	204 KiB

fever

#include <bits/stdc++.h>

using namespace std;

#ifdef __local_leywar
#include <debug/debugger.h>
#endif

#define int long long
#define endl '\n'

const int INF = 2e9,
          MOD = 1e9+7,
          INFLL = 1e18;

using pii = pair<int, int>;
mt19937_64 rng(time(0));

pii operator - (pii a, pii b)
{
    return (pii){a.first - b.first, a.second - b.second};
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<pii> ar(n);

    for(auto &i: ar)
        cin >> i.first >> i.second ; 

    for(int i = n - 1 ; i >= 0 ; i--)
    {
        ar[i] = ar[i] - ar[0];
    }

    int res = 0;

    //db(ar);

    for(int j = 0 ; j < 4 ; j++)
    {
        int ans = 1;
        vector<int> dp(n, INFLL);
        vector<bool> flag(n);
        flag[0] = true;
        dp[0] = 0;

        for(int i = 1 ; i < n ; i++)
        {
            if((j == 0 or j == 3) and ar[i].first == ar[i].second and ar[i].first >= 0)
                dp[i] = abs(ar[i].first);

            if((j == 0 or j == 1) and ar[i].first * -1 == ar[i].second and ar[i].first <= 0)
                dp[i] = abs(ar[i].first);

            if((j == 1 or j == 2) and ar[i].first == ar[i].second and ar[i].first <= 0)
                dp[i] = abs(ar[i].first);

            if((j == 2 or j == 3) and ar[i].first * -1 == ar[i].second and ar[i].first >= 0)
                dp[i] = abs(ar[i].first);
        }

        //db(dp);

        while(true)
        {
            int dist = INFLL, nod = -1;

            //db(dp);

            for(int i = 0 ; i < n ; i++)
                if(!flag[i] and dp[i] < dist)
                    dist = dp[i], nod = i;

            //db(dist, nod);

            if(nod == -1)
                break;

            ans++;
            flag[nod] = true;

            for(int i = 0 ; i < n ; i++)
            {
                pii temp = ar[nod] - ar[i];

                //db(ar[nod], ar[i], temp);
                //dbl(!flag[i], abs(temp.first) == abs(temp.second), dist <= abs(temp.first), dp[nod] > abs(temp.first));
                if(!flag[i] and abs(temp.first) == abs(temp.second) and dist <= abs(temp.first) and dp[i] > abs(temp.first))
                    dp[i] = abs(temp.first);
            }
        }

        //db(ans);

        res = max(res, ans);
    }

    cout << res ;

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31