Submission #1087693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087693		I_am_Polish_Girl	Let's Win the Election (JOI22_ho_t3)	C++14	61 / 100	2596 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(r, k);
 
    
    while (r - l > 1)
    {
        int m = (3*l + r) /4;
        
        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;
      |           ^~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:163:9: warning: unused variable 'sq' [-Wunused-variable]
  163 |     int sq = sqrt(r);
      |         ^~

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