oj.uz

Submission #937325

# Submission time Handle Problem Language Result Execution time Memory
937325 2024-03-03T20:52:40 Z Maite_Morale Let's Win the Election (JOI22_ho_t3) C++14
32 / 100
 897 ms 834652 KB 
#include<bits/stdc++.h>
#define F first
#define S second
#define MAX 500
#define oo 1e9+7
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(3);
using namespace std;
typedef long long ll;
typedef long double db;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>
 
ll t,n,mn[MAX],m,l[MAX];
pll aux[MAX];
db dp[MAX][MAX][MAX],cost[MAX];
pair<db,db> a[MAX];
int main(){
    fast_in
    cin>>n>>m;t=n;
    for(int i=0;i<n;i++){
        cin>>a[i].S>>a[i].F;
        if(a[i].F==-1){a[i].F=oo;t--;}
        aux[i]={a[i].S,a[i].F};
        mn[i]=a[i].S;
    }
    sort(a,a+n);sort(mn,mn+n);sort(aux,aux+n);
    ll s=0,top=m-1;
    for(int i=0;i<n;i++){
        aux[i]={aux[i].S,i};
        if(i<m)s+=mn[i];
        l[i]=i;
    }sort(aux,aux+n);
    for(int i=0;i<m;i++){
       cost[i]=s;
       if(aux[i].S<top){
          s-=mn[aux[i].S];
          if(aux[i].S>0)l[aux[i].S]=l[aux[i].S-1];
       }
       else{
          s-=mn[top];top=l[top-1];
       }
    }
    db r=cost[0];
    cost[m]=s;
    for(int k=0;k<=min(t,m);k++){
        for(int j=0;j<=k;j++){
            for(int i=0;i+k<=m;i++){
                dp[i][j][k]=oo;
                if(i+j==0)dp[i][j][k]=0;
                if(i>0)dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]+a[i+j-1].S/(k+1));
                if(j>0)dp[i][j][k]=min(dp[i][j][k],dp[i][j-1][k]+a[i+j-1].F/j);
              //  if(i>0)cout<<dp[i-1][j][k]<<"+"<<a[i+j-1].S/k<<".\n";
              //  if(j>0)cout<<dp[i][j-1][k]<<"+"<<a[i+j-1].F/j<<"'\n";
                if(j==k){
                //    cout<<i<<" "<<k<<" "<<" "<<dp[i][k][k]<<"+"<<cost[i+k]<<"\n";
                    if(cost[i+k]==0)r=min(r,dp[i][j][k]);
                    else            r=min(r,dp[i][j][k]+cost[i+k]/(k+1));
                }
            }
        }
    }
    cout<<r;
return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 29 ms 103084 KB Output is correct
6 Correct 26 ms 156664 KB Output is correct
7 Correct 20 ms 159832 KB Output is correct
8 Correct 19 ms 160848 KB Output is correct
9 Correct 19 ms 161884 KB Output is correct
10 Correct 19 ms 160700 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 29 ms 103084 KB Output is correct
6 Correct 26 ms 156664 KB Output is correct
7 Correct 20 ms 159832 KB Output is correct
8 Correct 19 ms 160848 KB Output is correct
9 Correct 19 ms 161884 KB Output is correct
10 Correct 19 ms 160700 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 38 ms 181044 KB Output is correct
13 Correct 38 ms 184660 KB Output is correct
14 Correct 34 ms 181212 KB Output is correct
15 Correct 282 ms 445008 KB Output is correct
16 Correct 275 ms 436304 KB Output is correct
17 Correct 107 ms 273488 KB Output is correct
18 Correct 885 ms 832876 KB Output is correct
19 Correct 587 ms 725844 KB Output is correct
20 Correct 118 ms 330824 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 10756 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 1 ms 10588 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 2 ms 10588 KB Output is correct
15 Correct 2 ms 14684 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 10756 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 1 ms 10588 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 2 ms 10588 KB Output is correct
15 Correct 2 ms 14684 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 2 ms 18780 KB Output is correct
18 Correct 2 ms 18780 KB Output is correct
19 Correct 5 ms 29208 KB Output is correct
20 Correct 3 ms 29020 KB Output is correct
21 Correct 3 ms 29020 KB Output is correct
22 Correct 4 ms 31324 KB Output is correct
23 Incorrect 3 ms 31324 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 10756 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 1 ms 10588 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 2 ms 10588 KB Output is correct
15 Correct 2 ms 14684 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 2 ms 18780 KB Output is correct
18 Correct 2 ms 18780 KB Output is correct
19 Correct 5 ms 29208 KB Output is correct
20 Correct 3 ms 29020 KB Output is correct
21 Correct 3 ms 29020 KB Output is correct
22 Correct 4 ms 31324 KB Output is correct
23 Incorrect 3 ms 31324 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 783 ms 834360 KB Output is correct
2 Correct 860 ms 833812 KB Output is correct
3 Correct 897 ms 834384 KB Output is correct
4 Correct 764 ms 834652 KB Output is correct
5 Correct 794 ms 834460 KB Output is correct
6 Correct 827 ms 833828 KB Output is correct
7 Correct 776 ms 834580 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 29 ms 103084 KB Output is correct
6 Correct 26 ms 156664 KB Output is correct
7 Correct 20 ms 159832 KB Output is correct
8 Correct 19 ms 160848 KB Output is correct
9 Correct 19 ms 161884 KB Output is correct
10 Correct 19 ms 160700 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 38 ms 181044 KB Output is correct
13 Correct 38 ms 184660 KB Output is correct
14 Correct 34 ms 181212 KB Output is correct
15 Correct 282 ms 445008 KB Output is correct
16 Correct 275 ms 436304 KB Output is correct
17 Correct 107 ms 273488 KB Output is correct
18 Correct 885 ms 832876 KB Output is correct
19 Correct 587 ms 725844 KB Output is correct
20 Correct 118 ms 330824 KB Output is correct
21 Correct 2 ms 2396 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 8540 KB Output is correct
25 Correct 1 ms 10756 KB Output is correct
26 Correct 2 ms 12632 KB Output is correct
27 Correct 2 ms 14684 KB Output is correct
28 Correct 2 ms 10588 KB Output is correct
29 Correct 2 ms 10588 KB Output is correct
30 Correct 2 ms 10588 KB Output is correct
31 Correct 1 ms 10588 KB Output is correct
32 Correct 2 ms 10588 KB Output is correct
33 Correct 2 ms 10588 KB Output is correct
34 Correct 2 ms 10588 KB Output is correct
35 Correct 2 ms 14684 KB Output is correct
36 Correct 1 ms 6492 KB Output is correct
37 Correct 2 ms 18780 KB Output is correct
38 Correct 2 ms 18780 KB Output is correct
39 Correct 5 ms 29208 KB Output is correct
40 Correct 3 ms 29020 KB Output is correct
41 Correct 3 ms 29020 KB Output is correct
42 Correct 4 ms 31324 KB Output is correct
43 Incorrect 3 ms 31324 KB Output isn't correct
44 Halted 0 ms 0 KB -