Submission #1072330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072330		_rain_	Let's Win the Election (JOI22_ho_t3)	C++14	100 / 100	155 ms	4440 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fixbug false
//#define double long double

void SETIO(string name = ""){
    if (name=="") return;
    freopen((name+".inp").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w+",stdout);
    return;
}

const int maxn = 502;
const int maxk = 502;
const int INF = 1e9 + 7;
int n , k ;
pair<double,double> a[maxn+2];
#define fi first
#define se second

bool cmp(pair<int,int> a , pair<int,int> b){
    if (a.second != b.second) return a.second < b.second;
    return a.first < b.first;
}
double dp[maxn+2][maxk+2];
double sum[maxn+2][maxn+2];

void reset(){
    for (int j = 0; j <= k + 1; ++j)
        for (int z = 0; z <= k + 1; ++z) {
                dp[j][z] = INF;
        }
    return;
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    SETIO("");

    cin >> n >> k;
    cout << setprecision(9) << fixed;
    reset();
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].fi >> a[i].se;
        if (a[i].se==-1) a[i].se = INF;
    }
    sort(a+1,a+n+1,cmp);

    //... BUILDING FOR THE RIGHT
        for (int i = 0; i <= n + 1; ++i) for (int j = 0; j <= k + 1; ++j) sum[i][j] = INF;
        for (int i = 0; i <= n + 1; ++i) sum[i][0] = 0;
        for (int i = n; i >= 1; --i){
            sum[i][1] = a[i].first;
            for (int num = 1; num <= k; ++num){
                sum[i][num] = min(sum[i + 1][num] , sum[i][num]);
                sum[i][num] = min(sum[i][num] , sum[i + 1][num - 1] + a[i].first);
            }
        }
    //...;
    reset();
    double ans = sum[1][k];
    for (int exp = 1; exp <= k + 1; ++exp){
        reset();
        dp[0][1] = 0;
        for (int i = 1; i <= k; ++i){
            for (int j = 1; j <= exp; ++j){
                dp[i][j] = min(dp[i - 1][j] + a[i].fi / (double)(exp) , dp[i][j]);
                if (j - 1 > 0)
                    dp[i][j] = min(dp[i - 1][j - 1] + a[i].se / (double)(j - 1) , dp[i][j]);
                if (j==exp){
                        if (fixbug){
                            cout << "EXP : " << exp << '\n';
                            cout << i << ' ' << j << ' ' << dp[i][j] << ' ' << dp[i][j] + sum[i + 1][k - i] / (double)exp << '\n';
                        }
                    ans = min(ans , dp[i][j] + sum[i + 1][k - i] / (double)exp);
                }
            }
        }
    }
    cout << ans;
}

Compilation message (stderr)

Main.cpp: In function 'void SETIO(std::string)':
Main.cpp:9:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     freopen((name+".inp").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:10:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     freopen((name+".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