oj.uz

Submission #828350

# Submission time Handle Problem Language Result Execution time Memory
828350 2023-08-17T08:47:11 Z RaresFelix Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 536 ms 984740 KB 
#include <bits/stdc++.h>

using namespace std;
const int MN = 501;
const double INF = 1e18;

struct stat {
    double a, b;
    bool operator < (const stat &rhs) const {
        return tie((b < 0) ? INF : b, a) < tie((rhs.b < 0) ? INF : rhs.b, rhs.a);
    }
} A[MN];
int n, k;
double DP[MN][MN][MN];
int main() {
    cin >> n >> k;
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= n; ++j) 
            for(int w = 0; w <= k; ++w)
                DP[i][j][w] = INF;
    for(int i = 1; i <= n; ++i) {
        cin >> A[i].a >> A[i].b;
    }
    sort(A + 1, A + n + 1);
    DP[0][1][0] = 0; 
    for(int i = 0; i < n; ++i) {
        for(int j = 1; j <= n; ++j) {
            for(int w = 0; w <= k; ++w) {
                ///propag (i, j, w) in orasul i + 1
                DP[i + 1][j][w] = min(DP[i + 1][j][w], DP[i][j][w]);
                DP[i + 1][j][w + 1] = min(DP[i + 1][j][w + 1], DP[i][j][w] + (A[i + 1].a / double(j)));
                if(A[i + 1].b >= 0)
                    DP[i + 1][j + 1][w + 1] = min(DP[i + 1][j + 1][w + 1], DP[i][j][w] + (A[i + 1].b / double(j)));
            }
        } 
    }
    double re = INF;
    for(int j = 1; j <= n; ++j)
        re = min(re, DP[n][j][k]);
    cout << fixed << setprecision(10) << re << "\n";
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 410 ms 984716 KB Output is correct
6 Correct 406 ms 984720 KB Output is correct
7 Correct 453 ms 984524 KB Output is correct
8 Correct 501 ms 984668 KB Output is correct
9 Correct 468 ms 984732 KB Output is correct
10 Correct 490 ms 984644 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 410 ms 984716 KB Output is correct
6 Correct 406 ms 984720 KB Output is correct
7 Correct 453 ms 984524 KB Output is correct
8 Correct 501 ms 984668 KB Output is correct
9 Correct 468 ms 984732 KB Output is correct
10 Correct 490 ms 984644 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 412 ms 984644 KB Output is correct
13 Correct 418 ms 984644 KB Output is correct
14 Correct 404 ms 984672 KB Output is correct
15 Correct 524 ms 984616 KB Output is correct
16 Correct 513 ms 984740 KB Output is correct
17 Correct 520 ms 984576 KB Output is correct
18 Correct 531 ms 984640 KB Output is correct
19 Correct 511 ms 984612 KB Output is correct
20 Correct 489 ms 984644 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 496 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Incorrect 1 ms 596 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 496 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Incorrect 1 ms 596 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 496 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Incorrect 1 ms 596 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 410 ms 984716 KB Output is correct
6 Correct 406 ms 984720 KB Output is correct
7 Correct 453 ms 984524 KB Output is correct
8 Correct 501 ms 984668 KB Output is correct
9 Correct 468 ms 984732 KB Output is correct
10 Correct 490 ms 984644 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 412 ms 984644 KB Output is correct
13 Correct 418 ms 984644 KB Output is correct
14 Correct 404 ms 984672 KB Output is correct
15 Correct 524 ms 984616 KB Output is correct
16 Correct 513 ms 984740 KB Output is correct
17 Correct 520 ms 984576 KB Output is correct
18 Correct 531 ms 984640 KB Output is correct
19 Correct 511 ms 984612 KB Output is correct
20 Correct 489 ms 984644 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 1 ms 496 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Incorrect 1 ms 596 KB Output isn't correct
30 Halted 0 ms 0 KB -