oj.uz

Submission #888237

# Submission time Handle Problem Language Result Execution time Memory
888237 2023-12-16T15:27:13 Z salmon Let's Win the Election (JOI22_ho_t3) C++14
56 / 100
 333 ms 16992 KB 
#include <bits/stdc++.h>
using namespace std;

#define foreach(a,b,i) for(type(a) i = a; i <= b; i++)
#define type(x) __typeof(x)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)

int N,K;
vector<pair<long double,int>> v;
int A[510];
long double B[510];
long double pre[510][510];
const long double inf = 1e40;
long double memo[510][510];

int main(){
    scanf(" %d",&N);
    scanf(" %d",&K);

    for(int i = 1; i <= N; i++){
        scanf(" %d",&A[i]);
        scanf(" %Lf",&B[i]);
        if(B[i] == -1) B[i] = inf;
        v.pb(mp(B[i],i));
    }

    v.pb(mp(-1,-1));

    sort(v.begin(),v.end());

    foreach(0,N - 1,i){
        pre[i][i] = 0;
        foreach(i + 1, N, j){
            pre[j][i] = pre[j - 1][i] + B[v[j].second] / (long double) (j - i);
        }
    }

    long double big = inf;

    foreach(0,K,i){
        foreach(0,K,k){
            memo[0][k] = inf;
        }

        memo[0][0] = pre[i][0] - pre[0][0];

        //printf("%Lf\n",memo[0][0]);

        foreach(1,N, j){
            foreach(0, K, k){
                memo[j][k] = inf;
                if(k == 0){
                    memo[j][k] = memo[j - 1][k];
                }
                else{
                    if(j <= i + k - 1){
                        memo[j][k] = min(memo[j - 1][k], memo[j - 1][k - 1] + A[v[j].second]/(long double)(i+1) + pre[i + k][k] - pre[j][k]  - (pre[i + k - 1][k - 1] - pre[j - 1][k - 1]) );
                    }
                    else{
                        memo[j][k] = min(memo[j - 1][k], memo[j - 1][k - 1] + A[v[j].second]/(long double)(i+1));
                    }
                }
                //printf("%Lf %d %d\n",memo[j][k],j,k);
            }
        }

        //printf("\n%Lf %d\n\n",memo[N][K - i],i);
        big = min(big,memo[N][K - i]);
    }

    printf("%Lf",big);


}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
Main.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf(" %d",&K);
      |     ~~~~~^~~~~~~~~~
Main.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf(" %d",&A[i]);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf(" %Lf",&B[i]);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 16 ms 8480 KB Output is correct
6 Correct 115 ms 8476 KB Output is correct
7 Correct 333 ms 8536 KB Output is correct
8 Runtime error 318 ms 16992 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 16 ms 8480 KB Output is correct
6 Correct 115 ms 8476 KB Output is correct
7 Correct 333 ms 8536 KB Output is correct
8 Runtime error 318 ms 16992 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2496 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2500 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2496 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2500 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2648 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2492 KB Output is correct
24 Correct 1 ms 2392 KB Output is correct
25 Correct 1 ms 2396 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 2396 KB Output is correct
28 Correct 1 ms 2396 KB Output is correct
29 Correct 1 ms 2396 KB Output is correct
30 Correct 1 ms 2516 KB Output is correct
31 Correct 1 ms 2396 KB Output is correct
32 Correct 1 ms 2392 KB Output is correct
33 Correct 1 ms 2396 KB Output is correct
34 Correct 1 ms 2496 KB Output is correct
35 Correct 1 ms 2396 KB Output is correct
36 Correct 1 ms 2396 KB Output is correct
37 Correct 1 ms 2396 KB Output is correct
38 Correct 1 ms 2392 KB Output is correct
39 Correct 1 ms 2396 KB Output is correct
40 Correct 1 ms 2396 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2496 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2500 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2648 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2492 KB Output is correct
24 Correct 1 ms 2392 KB Output is correct
25 Correct 1 ms 2396 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 2396 KB Output is correct
28 Correct 1 ms 2396 KB Output is correct
29 Correct 1 ms 2396 KB Output is correct
30 Correct 1 ms 2516 KB Output is correct
31 Correct 1 ms 2396 KB Output is correct
32 Correct 1 ms 2392 KB Output is correct
33 Correct 1 ms 2396 KB Output is correct
34 Correct 1 ms 2496 KB Output is correct
35 Correct 1 ms 2396 KB Output is correct
36 Correct 1 ms 2396 KB Output is correct
37 Correct 1 ms 2396 KB Output is correct
38 Correct 1 ms 2392 KB Output is correct
39 Correct 1 ms 2396 KB Output is correct
40 Correct 1 ms 2396 KB Output is correct
41 Correct 2 ms 6492 KB Output is correct
42 Correct 1 ms 6492 KB Output is correct
43 Correct 2 ms 6488 KB Output is correct
44 Correct 2 ms 6492 KB Output is correct
45 Correct 4 ms 6492 KB Output is correct
46 Correct 4 ms 6492 KB Output is correct
47 Correct 6 ms 6492 KB Output is correct
48 Correct 9 ms 6492 KB Output is correct
49 Correct 9 ms 6488 KB Output is correct
50 Correct 9 ms 6492 KB Output is correct
51 Correct 14 ms 6492 KB Output is correct
52 Correct 13 ms 6492 KB Output is correct
53 Correct 6 ms 6488 KB Output is correct
54 Correct 6 ms 6488 KB Output is correct
55 Correct 6 ms 6492 KB Output is correct
56 Correct 6 ms 6560 KB Output is correct
57 Correct 7 ms 6492 KB Output is correct
58 Correct 6 ms 6492 KB Output is correct
59 Correct 6 ms 6708 KB Output is correct
60 Correct 10 ms 6488 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 16980 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 16 ms 8480 KB Output is correct
6 Correct 115 ms 8476 KB Output is correct
7 Correct 333 ms 8536 KB Output is correct
8 Runtime error 318 ms 16992 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -