Submission #806593

#	Time	Username	Problem	Language	Result	Execution time	Memory
806593		vjudge1	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	479 ms	18524 KiB

Main

#include <bits/stdc++.h>



using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 500 + 9 , mod = 1e9 + 7;
ll  d[N] = {} , a[N] = {},  b[N] , c[N];

ld dp[N][N];
ll sum[N][N];
multiset<pair<int,int>>st[N][N];

void del(int i , int j , int x , int y){
    sum[i][j] -= x;
    st[i][j].erase(st[i][j].find({x , y}));
}

void solve(){
    ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
    cin>>n>>k;
    vector<pair<ll,ll>>v, v1;
    multiset<ll>st;
    v.pb({-5 , -5});
    for(i = 1; i <= n; i++){
        cin>>a[i]>>b[i];
        if(b[i] == -1)
            b[i] = 1e13;
        v1.pb({a[i] , b[i]});
        v.pb({b[i] , a[i]});
        st.insert(a[i]);
    }
    sort(all(v));
    sort(all(v1));
    mn = 0;
    for(i = 0; i < k; i++)
        mn += v1[i].fi;
    sum[0][0] = 0;
    j = 1;
    for(auto it : st)
        sum[0][j] = sum[0][j - 1] + it ,j++;
    for(i = 1; i <= n; i++){
        st.erase(st.find(v[i].se));
        sum[i][0] = 0;
        j = 1;
        for(auto it : st)
            sum[i][j] = sum[i][j - 1] + it ,j++;
    }
    //cout<<mn<<"\n";
    ld ans = mn;
    for(x = 1; x <= k; x++){
        for(i = 1; i <= x; i++)
            dp[0][i] = 1e18;
        for(i = 1; i <= k; i++){
            for(j = 0; j <= x; j++){
                if(j == 0){
                    dp[i][j] = dp[i - 1][j] + v[i].se / (ld) (x + 1);
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + v[i].se / (ld) (x + 1);
                dp[i][j] = min(dp[i][j] , dp[i - 1][j - 1] + v[i].fi / (ld) (j));
            }
            ans = min(ans , dp[i][x] + (sum[i][k - i]) / (ld) (x + 1));
        }
    }
    cout<<fixed<<setprecision(12)<<ans<<"\n";
}

int main(){
     TL;
     /*
     #ifndef ONLINE_JUDGE
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
     #endif
     */
int t = 1;
//cin>>t;

while(t--)
     {
     solve();
     }

}
// Author : حسن

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:38:8: warning: unused variable 'q' [-Wunused-variable]
   38 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |        ^
Main.cpp:38:20: warning: unused variable 'm' [-Wunused-variable]
   38 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                    ^
Main.cpp:38:26: warning: unused variable 'z' [-Wunused-variable]
   38 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                          ^
Main.cpp:38:29: warning: unused variable 's' [-Wunused-variable]
   38 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                             ^
Main.cpp:38:37: warning: unused variable 'f' [-Wunused-variable]
   38 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                     ^
Main.cpp:38:41: warning: unused variable 'l' [-Wunused-variable]
   38 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                         ^
Main.cpp:38:45: warning: unused variable 'r' [-Wunused-variable]
   38 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                             ^
Main.cpp:38:57: warning: unused variable 'y' [-Wunused-variable]
   38 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                         ^
Main.cpp:38:74: warning: unused variable 'mx' [-Wunused-variable]
   38 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                                          ^~

• 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