Submission #888237

#	Time	Username	Problem	Language	Result	Execution time	Memory
888237		salmon	Let's Win the Election (JOI22_ho_t3)	C++14	56 / 100	333 ms	16992 KiB

Main

#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 (stderr)

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
• Subtask 2: 0 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 33 / 33
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23