Submission #1268534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268534		lambd47	Let's Win the Election (JOI22_ho_t3)	C++20	56 / 100	2594 ms	788 KiB

Main

#include <bits/stdc++.h>

#define int long long 
using namespace std;

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define pii pair<int,int>

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int MOD=1e9+7;
void solve() {
    int n,m;
    cin>>n>>m;
    vector<pii> vec(n);
    L(i,0,n-1){
        cin>>vec[i].first>>vec[i].second;
        if(vec[i].second==-1)vec[i].second=MOD;
    }

    sort(all(vec),[&](pii a, pii b){
            if(a.second==b.second)return a.first<b.first;
            return a.second<b.second;
    });

    auto testa=[&](int k)->double{
        vector<vector<double>> dp(k+1,vector<double> (m-k+1,(double)MOD));
        dp[0][0]=0;
        L(i,0,n-1){
            R(j,k,0){
                R(f,m-k,0){
                    if(j!=k && vec[i].second!=MOD)dp[j+1][f]=min(dp[j+1][f],dp[j][f]+(double)vec[i].second/(j+1));
                    if(f!=(m-k))dp[j][f+1]=min(dp[j][f+1],dp[j][f]+(double)vec[i].first/(k+1));
                }
            }
        }
        return dp[k][m-k];
    };
    cout<<fixed<<setprecision(8);
    double resp=(double) MOD;
    L(i,0,m)resp=min(resp,testa(i));
    cout<<resp<<"\n";
}
 
int32_t main() {
    std::cin.tie(0)->sync_with_stdio(0); 
    std::cin.exceptions(std::cin.failbit);

    int T = 1;
//    std::cin >> T;
    while(T--) {
        solve();
    }

	return 0;
}

• Subtask 1: 0 / 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