Submission #528062

#	Time	Username	Problem	Language	Result	Execution time	Memory
528062		amukkalir	Let's Win the Election (JOI22_ho_t3)	C++17	0 / 100	2636 ms	990696 KiB

Main

#include <bits/stdc++.h> 
using namespace std; 
typedef long long ll; 
 
#define prn printf
#define scn scanf
#define pii pair<int,int> 
#define fi first 
#define se second 
#define mp make_pair
 
const int nax = 500;  
const int inf = 1e9; 
 
int n,k; 
double memo[nax+5][nax+5][nax+5]; 
vector<pii> a; 
 
// double dp(int idx, int col, int rem) {
//     if(rem == 0) return 0; 
//     if(idx == n) return inf; 
 
//     double &ret = memo[idx][col][rem]; 
//     if(ret!=0) return ret; 
 
//     ret = dp(idx+1, col, rem); // ga ambil 
//     if(a[idx].fi != inf) ret = min(ret, (double)a[idx].fi/col + dp(idx+1, col+1, rem-1)); 
//     else ret = min(ret, (double)a[idx].se/col + dp(idx+1,col,rem-1)); 
 
//    // cerr << idx << " " << col << " " << rem << " = " << ret << endl; 
//     return ret; 
// }
 
double dp (int idx, int col, int vote, int tcol) {
    if(col + vote == 0) return 0; 
    if(idx==n) return inf; 
 
    double &ret = memo[idx][col][vote]; 
    if(ret!=0) return ret; 
 
    ret = dp(idx+1, col, vote, tcol); 
    
    if(col>0 && a[idx].fi != inf) ret = min(ret, (double)a[idx].fi/(tcol-col+1) + dp(idx+1, col-1, vote, tcol)); //consider jd collaborator 
    if(vote>0) ret = min(ret, (double)a[idx].se/(tcol+1) + dp(idx+1,col,vote-1, tcol)); 
    //cerr << idx << " " << col <<  " " << vote << endl; 
    return ret; 
}

double get(ll c) {
    for(int i=0;i<n;i++) for(int j=0;j<n; j++) for(int k=0; k<n; k++) memo[i][j][k] = 0; 
    return dp(0, c, k-c, c); 
}
 
signed main () {
    scn("%d%d", &n, &k); 
 
    a.assign(n,{0,0}); 
    for(int i=0; i<n; i++) {
        scn("%d%d", &a[i].se, &a[i].fi);
        if(a[i].fi == -1) a[i].fi = inf; 
    }
 
    sort(a.begin(), a.end()); 
    
    //for(int i=0; i<n; i++) //cerr << a[i].fi << " " << a[i].se << endl; 
 
    double ans = inf; 
    int lo = 0, hi = k; 

    while(hi - lo > 2) { 
        int m1 = (hi+lo)/3; 
        int m2 = 2*(hi+lo)/3; 
        //cerr << m1 <<  " " << m2 << " " << endl; 

        double vm1 = get(m1); 
        double vm2 = get(m2); 

        if(get(m1+1) < vm1 && get(m2-1) < vm2) { 
            lo = m1+1; 
            hi = m2-1; 
        } else if(get(m2+1) < vm2) {
            lo = m2+1; 
        } else {
            hi = m1-1; 
        }
    }
    //cerr << " :: " << lo << " " << hi << endl; 
    for(int i = lo; i <= hi; i++) ans = min(ans, get(i));
 
    prn("%f", ans); 
}
 
/*

1 2 3 4 5 6 7 8 9 

9/3 

1 2 3 
4/3 
8/3 


 
dp(i,j,k) = time minimum untuk visit k kota up to index i 
ddn j collaboratior 
 
dp(i,j,0) = 0
 
ambil b 
dp(i+1, j+1, k-1) + b[i]
ambil a 
dp(i+1, j, k-1) + a[i]
ga ambil 
dp(i+1, j+1, k)
 
 
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scn("%d%d", &n, &k);
      |        ^
Main.cpp:59:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scn("%d%d", &a[i].se, &a[i].fi);
      |            ^

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