oj.uz

Submission #794422

# Submission time Handle Problem Language Result Execution time Memory
794422 2023-07-26T14:12:55 Z Theo830 Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 1038 ms 1008604 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 596 KB Output is correct
4 Correct 1 ms 580 KB Output is correct
5 Correct 421 ms 1008496 KB Output is correct
6 Correct 402 ms 1008600 KB Output is correct
7 Correct 536 ms 1008516 KB Output is correct
8 Correct 704 ms 1008492 KB Output is correct
9 Correct 1038 ms 1008496 KB Output is correct
10 Correct 665 ms 1008500 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 596 KB Output is correct
4 Correct 1 ms 580 KB Output is correct
5 Correct 421 ms 1008496 KB Output is correct
6 Correct 402 ms 1008600 KB Output is correct
7 Correct 536 ms 1008516 KB Output is correct
8 Correct 704 ms 1008492 KB Output is correct
9 Correct 1038 ms 1008496 KB Output is correct
10 Correct 665 ms 1008500 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 414 ms 1008444 KB Output is correct
13 Correct 430 ms 1008496 KB Output is correct
14 Correct 431 ms 1008428 KB Output is correct
15 Correct 674 ms 1008492 KB Output is correct
16 Correct 623 ms 1008460 KB Output is correct
17 Correct 681 ms 1008460 KB Output is correct
18 Correct 950 ms 1008488 KB Output is correct
19 Correct 897 ms 1008492 KB Output is correct
20 Correct 956 ms 1008604 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 0 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 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 0 ms 852 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 0 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 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 0 ms 852 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 0 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 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 0 ms 852 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 968 ms 1008488 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 596 KB Output is correct
4 Correct 1 ms 580 KB Output is correct
5 Correct 421 ms 1008496 KB Output is correct
6 Correct 402 ms 1008600 KB Output is correct
7 Correct 536 ms 1008516 KB Output is correct
8 Correct 704 ms 1008492 KB Output is correct
9 Correct 1038 ms 1008496 KB Output is correct
10 Correct 665 ms 1008500 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 414 ms 1008444 KB Output is correct
13 Correct 430 ms 1008496 KB Output is correct
14 Correct 431 ms 1008428 KB Output is correct
15 Correct 674 ms 1008492 KB Output is correct
16 Correct 623 ms 1008460 KB Output is correct
17 Correct 681 ms 1008460 KB Output is correct
18 Correct 950 ms 1008488 KB Output is correct
19 Correct 897 ms 1008492 KB Output is correct
20 Correct 956 ms 1008604 KB Output is correct
21 Correct 1 ms 852 KB Output is correct
22 Correct 0 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 852 KB Output is correct
27 Correct 1 ms 852 KB Output is correct
28 Correct 0 ms 852 KB Output is correct
29 Incorrect 1 ms 852 KB Output isn't correct
30 Halted 0 ms 0 KB -