Submission #1087551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087551		I_am_Polish_Girl	Let's Win the Election (JOI22_ho_t3)	C++14	28 / 100	2386 ms	2420 KiB

Main

#pragma target("arch=icelake-server")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")

#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <iostream>

using namespace std;


int log_ = 3;
int inf = 200000000000000;
int mod = 1102024631;

int p = 505;


bool cmp(pair <int, int> a, pair <int, int> b)
{
    if (a.second < b.second)
    {
        return true;
    }

    return false;
}


double dp1[501][501];

vector <pair <int, int>> vp;

int k;


vector <double> ans__;

double c(int col)
{
    if (ans__[col] != -1)
        return ans__[col];

    int n = vp.size();


    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            dp1[i][j] = inf;
        }
    }

    dp1[0][0] = 0;


    for (int k = 0; k < n; k++)
    {
        for (int i = n; i >= 0; i--)
        {
            for (int j = n; j >= 0; j--)
            {
                if (i > 0)
                {
                    if (vp[k].second != -1)
                    {
                        dp1[i][j] = min(dp1[i][j], dp1[i - 1][j] + ((0. + (col + 1) * vp[k].second) / i));
                    }
                }

                if (j > 0)
                {
                    dp1[i][j] = min(dp1[i][j], dp1[i][j - 1] + ((0. + vp[k].first)));
                }
            }
        }

    }

    double ans = inf;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (i + j == k)
            {
                if (i == col)
                {
                    ans = min(dp1[i][j], ans);
                }
            }
        }
    }

    ans /= col + 1;

    ans__[col] = ans;

    return ans;
}

mt19937 rnd(15);

int rnd_(int l, int r)
{
    int s = r - l + 1;

    int x = rnd();

    x = abs(x);

    x %= (s + 1);

    return l + x;
}

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

    int n;
    cin >> n >> k;

    ans__.resize(n + 2, -1);

    vp.resize(n);

    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;

        vp[i] = { a,  b };
    }

    sort(vp.begin(), vp.end(), cmp);

    int l = 0;
    int r = n;

    for (int i = 0; i < n; i++)
    {
        if (vp[i].second == -1)
            r--;
    }

    int sq = sqrt(r);
    r = min(sq+10, r);
    r = min(r, k);

    
    while (r - l > 1)
    {
        int m = (l + r) /2;
        
        if (c(m) < c(m + 1))
            r = m;
        else
            l = m+1;
    }

    double ans = inf;

    for (int i = l; i <= r; i++)
    {
        ans = min(c(i) , ans);
    }


    cout << fixed;
    cout << setprecision(9);
    cout << ans;
}

Compilation message (stderr)

Main.cpp:1: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    1 | #pragma target("arch=icelake-server")
      | 
Main.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
Main.cpp:26:11: warning: overflow in conversion from 'long int' to 'int' changes value from '200000000000000' to '552894464' [-Woverflow]
   26 | int inf = 200000000000000;
      |           ^~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 0 / 33
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23