oj.uz

Submission #528058

# Submission time Handle Problem Language Result Execution time Memory
528058 2022-02-19T05:27:58 Z amukkalir Let's Win the Election (JOI22_ho_t3) C++17
16 / 100
 432 ms 2292 KB 
#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]; 
vector<pii> a; 

double dp(int idx, int col, int tcol) {
    int vote = (k-tcol) - (idx - (tcol - col)); 
    if(col + vote == 0) return 0; 
    else if(idx == n) return inf; 

    double &ret = memo[idx][col];
    if(ret != 0) return ret; 

    ret = inf; 
    if(col>0 && a[idx].fi != inf) ret = min(ret, (double)a[idx].fi/(tcol-col+1) + dp(idx+1, col-1, tcol)); //consider jd collaborator 
    if(vote>0) ret = min(ret, (double)a[idx].se/(tcol+1) + dp(idx+1, col, tcol)); 
//cerr << idx << " " << col << " " << vote << " " << tcol << endl; 
    return ret; 
}
 
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; 
    for(int c = 0; c <= min(n,k); c++) {
        //cerr << " :: " << c << endl; 
        for(int i=0;i<n;i++) for(int j=0;j<n; j++) memo[i][j] = 0.0; 
        ////cerr << c << "  " << dp(0,c,c) << endl; 
        ans = min(ans, dp(0, c, c)); 
    }
 
    prn("%f", ans); 
}
 
/*
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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 4 ms 2252 KB Output is correct
6 Correct 8 ms 2252 KB Output is correct
7 Correct 19 ms 2252 KB Output is correct
8 Correct 21 ms 2292 KB Output is correct
9 Correct 29 ms 2252 KB Output is correct
10 Correct 19 ms 2252 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 4 ms 2252 KB Output is correct
6 Correct 8 ms 2252 KB Output is correct
7 Correct 19 ms 2252 KB Output is correct
8 Correct 21 ms 2292 KB Output is correct
9 Correct 29 ms 2252 KB Output is correct
10 Correct 19 ms 2252 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 18 ms 2280 KB Output is correct
13 Incorrect 18 ms 2252 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 2288 KB Output is correct
2 Correct 361 ms 2288 KB Output is correct
3 Correct 432 ms 2252 KB Output is correct
4 Correct 370 ms 2288 KB Output is correct
5 Correct 349 ms 2284 KB Output is correct
6 Correct 416 ms 2284 KB Output is correct
7 Correct 367 ms 2288 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 4 ms 2252 KB Output is correct
6 Correct 8 ms 2252 KB Output is correct
7 Correct 19 ms 2252 KB Output is correct
8 Correct 21 ms 2292 KB Output is correct
9 Correct 29 ms 2252 KB Output is correct
10 Correct 19 ms 2252 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 18 ms 2280 KB Output is correct
13 Incorrect 18 ms 2252 KB Output isn't correct
14 Halted 0 ms 0 KB -