Submission #674852

#	Time	Username	Problem	Language	Result	Execution time	Memory
674852		guagua0407	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	304 ms	3764 KiB

Main

/*
希望全國賽不要墊底

全國賽策略：
0:00-0:15：讀題
0:15-3:00：寫掉有把握的
3:00-5:00：撈分+寫掉快好的

記得上廁所
記得吃東西
*/
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end() 
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

struct node{
    int a,b;
};

const int mxn=505;
node num[mxn];

bool cmp(node x,node y){
    if(x.b!=y.b) return x.b<y.b;
    return x.a<y.a;
}

int main() {_
    //setIO("wayne");
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>num[i].a>>num[i].b;
        if(num[i].b==-1) num[i].b=1e9;
    }
    sort(num+1,num+n+1,cmp);
    vector<vector<int>> pre(n+1,vector<int>(n+1,0));
    for(int i=0;i<=n;i++){
        vector<int> tmp;
        for(int j=i+1;j<=n;j++){
            tmp.push_back(num[j].a);
        }
        sort(all(tmp),greater<int>());
        for(int j=1;j<=n-i;j++){
            pre[i][j]=pre[i][j-1]+tmp.back();
            tmp.pop_back();
        }
    }
    double ans=(double)(1e9);
    for(int m=0;m<k;m++){
        vector<vector<double>> dp(n+1,vector<double>(m+1,(double)1e9));
        dp[0][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=m;j++){
                dp[i][j]=dp[i-1][j]+(double)num[i].a/(double)(m+1);
                if(j>=1) dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(double)num[i].b/(double)j);
            }
        }
        for(int i=m;i<=k;i++){
            ans=min(ans,dp[i][m]+(double)pre[i][k-i]/(double)(m+1));
            //cout<<i<<' '<<m<<' '<<fixed<<setprecision(9)<<dp[i][m]+(double)pre[i][k-i]/(double)(m+1)<<'\n';
        }
    }
    cout<<fixed<<setprecision(9);
    cout<<ans;
    return 0;
}
//maybe its multiset not set

Compilation message (stderr)

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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