oj.uz

Submission #794443

# Submission time Handle Problem Language Result Execution time Memory
794443 2023-07-26T14:26:15 Z Theo830 Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 1196 ms 1008728 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
double dp[505][505][505];
ll n,k;
vector<ii>ar;
double solve(ll idx,ll i,ll j){
    if(j >= k){
        return 0;
    }
    if(idx == n){
        return 1e18;
    }
    if(dp[idx][i][j] != -1){
        return dp[idx][i][j];
    }
    double ans = solve(idx + 1,i,j);
    ans = min(ans,solve(idx + 1,i,j+1) + (double)(-ar[idx].S) / (double)(i));
    ans = min(ans,solve(idx + 1,i+1,j+1) + (double)(ar[idx].F) / (double)(i));
    return dp[idx][i][j] = ans;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k;
    f(i,0,n+5){
        f(j,0,n+5){
            f(u,0,n+5){
                dp[i][j][u] = -1;
            }
        }
    }
    ll a[n],b[n];
    f(i,0,n){
        cin>>a[i]>>b[i];
        if(b[i] == -1){
            b[i] = 1e18;
        }
        ar.pb(ii(b[i],-a[i]));
    }
    sort(all(ar));
    cout<<fixed<<setprecision(6)<<solve(0,1,0)<<"\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 389 ms 1008392 KB Output is correct
6 Correct 375 ms 1008424 KB Output is correct
7 Correct 509 ms 1008480 KB Output is correct
8 Correct 714 ms 1008380 KB Output is correct
9 Correct 981 ms 1008492 KB Output is correct
10 Correct 666 ms 1008564 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 389 ms 1008392 KB Output is correct
6 Correct 375 ms 1008424 KB Output is correct
7 Correct 509 ms 1008480 KB Output is correct
8 Correct 714 ms 1008380 KB Output is correct
9 Correct 981 ms 1008492 KB Output is correct
10 Correct 666 ms 1008564 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 404 ms 1008492 KB Output is correct
13 Correct 400 ms 1008728 KB Output is correct
14 Correct 416 ms 1008496 KB Output is correct
15 Correct 641 ms 1008464 KB Output is correct
16 Correct 633 ms 1008472 KB Output is correct
17 Correct 795 ms 1008504 KB Output is correct
18 Correct 975 ms 1008460 KB Output is correct
19 Correct 942 ms 1008496 KB Output is correct
20 Correct 1171 ms 1008500 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 848 KB Output is correct
9 Incorrect 1 ms 852 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 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 848 KB Output is correct
9 Incorrect 1 ms 852 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 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 848 KB Output is correct
9 Incorrect 1 ms 852 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1196 ms 1008492 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 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 389 ms 1008392 KB Output is correct
6 Correct 375 ms 1008424 KB Output is correct
7 Correct 509 ms 1008480 KB Output is correct
8 Correct 714 ms 1008380 KB Output is correct
9 Correct 981 ms 1008492 KB Output is correct
10 Correct 666 ms 1008564 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 404 ms 1008492 KB Output is correct
13 Correct 400 ms 1008728 KB Output is correct
14 Correct 416 ms 1008496 KB Output is correct
15 Correct 641 ms 1008464 KB Output is correct
16 Correct 633 ms 1008472 KB Output is correct
17 Correct 795 ms 1008504 KB Output is correct
18 Correct 975 ms 1008460 KB Output is correct
19 Correct 942 ms 1008496 KB Output is correct
20 Correct 1171 ms 1008500 KB Output is correct
21 Correct 1 ms 852 KB Output is correct
22 Correct 1 ms 852 KB Output is correct
23 Correct 1 ms 852 KB Output is correct
24 Correct 1 ms 852 KB Output is correct
25 Correct 1 ms 852 KB Output is correct
26 Correct 1 ms 844 KB Output is correct
27 Correct 1 ms 852 KB Output is correct
28 Correct 1 ms 848 KB Output is correct
29 Incorrect 1 ms 852 KB Output isn't correct
30 Halted 0 ms 0 KB -