Submission #871860

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
871860	2023-11-11T18:13:23 Z	HorizonWest	Let's Win the Election (JOI22_ho_t3)	C++17	Compilation error	0 ms	0 KB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define db double
#define ll __int128
#define int long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;
 
const int Max = 1e6 + 7, Inf = 1e9 + 7;
 
void print(bool x) { cout << (x ? "YES" : "NO") << endl; }
 
string tostring (__int128 x)
{
    string ans = "";
    while(x > 0)
    {
        ans += (x % 10 + '0');
        x /= 10;
    }
    reverse(all(ans));
    return ans;
}
 
void printdb(double ans, int k)
{
    cout << setiosflags(ios::fixed)
         << setiosflags(ios::showpoint)
         << setprecision(k) << ans << endl;
}
 
pair <db, db> fmin(pair<db, db> a, pair <db, db> b, db j)
{
    if(db(a.fs + a.sd / j) < db(b.fs + b.sd / j))
        return a; 
    else   
        return b; 
}
 
int prec(vector <pair<db, db>> a, vector <pair<db, db>> b, int n, int m)
{
    vector <db> take(n, 1); 
 
    for(db i = 1; i <= m; i++)
    {
        db Z1 = 0.0, Z2 = b[i-1].fs / i; int cnt = i - 1;   //cerr << b[i-1].fs << endl; 
        
        for(int j = 0; j < n; j++)
        {
            //cerr << a[j].fs << " "; 
            if(cnt == m) break;
            Z1 += take[a[j].sd] * a[j].fs / i; 
            cnt += take[a[j].sd];
        } 
        
        cnt = i; take[b[i-1].sd] = 0;  
 
        for(int j = 0; j < n; j++)
        {
            if(cnt == m) break;
            Z2 += take[a[j].sd] * a[j].fs / (i + 1); 
            cnt += take[a[j].sd]; 
        }
 
        //cerr << Z1 << " " << Z2 << endl; 
 
        if(Z1 <= Z2) return i; 
    }
 
    return m; 
}
 
void solve()
{
    int n, m; cin >> n >> m; 
    vector <pair<db, db>> v(n), a(n), b(n);
 
    for(int i = 0; i < n; i++) 
    {
        cin >> v[i].sd >> v[i].fs;
        if(v[i].fs == -1) v[i].fs = Inf;
        a[i].fs = v[i].sd; b[i].fs = v[i].fs; 
        a[i].sd = b[i].sd = i;   
    } 
 
    sort(all(v)); sort(all(a)); sort(all(b)); 
    
    db ans = Inf; int fx = prec(a, b, n, m); 
    //cerr << fx << endl; 
    for(db l = max(1, fx-5); l <= min(fx+5, m); l++)
    {
        vector <vector<vector<db>>> dp(n + 2, vector <vector<db>> (
            m + 2, vector <db> (m + 2, Inf)
        )); dp[0][1][0] = 0.000; 
        
        for(db i = 0; i < n; i++)
        {
            for(db j = 1; j <= l; j++)
            {
                for(db k = 0; k <= m; k++)
                {
                    dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k]);  
                    dp[i+1][j][k+1] = min(dp[i+1][j][k+1], dp[i][j][k] + v[i].sd / l); 
                    if(v[i].fs != Inf)
                    {
                        dp[i+1][j+1][k+1] = min(dp[i+1][j+1][k+1], dp[i][j][k] + v[i].fs / j); 
                    } 
                }
            }
            ans = min(ans, dp[i+1][l][m]); 
        }
    }
 
    printdb(ans, 5); 
}
 
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int Q = 1; //cin >> Q;
 
    while (Q--)
    {
        solve();
    }
 
    return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:99:27: error: no matching function for call to 'max(int, long long int)'
   99 |     for(db l = max(1, fx-5); l <= min(fx+5, m); l++)
      |                           ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
Main.cpp:99:27: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   99 |     for(db l = max(1, fx-5); l <= min(fx+5, m); l++)
      |                           ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
Main.cpp:99:27: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   99 |     for(db l = max(1, fx-5); l <= min(fx+5, m); l++)
      |                           ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
Main.cpp:99:27: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   99 |     for(db l = max(1, fx-5); l <= min(fx+5, m); l++)
      |                           ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
Main.cpp:99:27: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   99 |     for(db l = max(1, fx-5); l <= min(fx+5, m); l++)
      |                           ^