oj.uz

Submission #1106174

# Submission time Handle Problem Language Result Execution time Memory
1106174 2024-10-29T13:23:18 Z akim9905 Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 1105 ms 1008712 KB 
#include <bits/stdc++.h>
using namespace std;

#define fileio() freopen("input.txt","r",stdin); freopen("output.txt","w",stdout)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define allr(x) x.rbegin(), x.rend()
#define cmprs(x) sort(all(x)),x.erase(unique(all(x)),x.end())
#define endl "\n"
#define sp " "
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define rz resize
#define sz(a) (int)(a.size())
#define clr(a) a.clear()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;
typedef pair<double, int> pdi;

const int dx[] = {1,-1,0,0,1,1,-1,-1};
const int dy[] = {0,0,1,-1,1,-1,1,-1};
const ll MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAX = 505; // PLZ CHK!

int N,K;
pair<double,double> A[MAX];
double D[MAX][MAX][MAX];
const double eps=1e-9;

double go(int i, int j, int k) {
    if (k==K) return 0.0;
    if (i>N) return 1e9;
    double &ret=D[i][j][k];
    if (ret>-1.0) return ret;

    ret=go(i+1,j,k);
    ret=min(ret, go(i+1,j,k+1)+A[i].first/(1.0*j));
    if (A[i].second>-1.0) ret=min(ret, go(i+1,j+1,k+1)+A[i].second/(1.0*j));

    return ret;
}

int main() {
    fio();
    cin>>N>>K;
    for (int i=1; i<=N; i++) {
        cin>>A[i].first>>A[i].second;
        if (abs(A[i].second+1.0)<eps) A[i].second=1e9;
    }

    sort(A+1,A+N+1,[](auto a, auto b){
        if (a.second==b.second) return a.first<b.first;
        return a.second<b.second;
    });

    fill_n(&D[0][0][0],MAX*MAX*MAX,-1.0);

    cout<<fixed; cout.precision(10);
    cout<<go(1,1,0);
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 1008420 KB Output is correct
2 Correct 573 ms 1008456 KB Output is correct
3 Correct 583 ms 1008456 KB Output is correct
4 Correct 568 ms 1008464 KB Output is correct
5 Correct 625 ms 1008456 KB Output is correct
6 Correct 632 ms 1008428 KB Output is correct
7 Correct 830 ms 1008476 KB Output is correct
8 Correct 1008 ms 1008396 KB Output is correct
9 Correct 994 ms 1008620 KB Output is correct
10 Correct 878 ms 1008460 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 1008420 KB Output is correct
2 Correct 573 ms 1008456 KB Output is correct
3 Correct 583 ms 1008456 KB Output is correct
4 Correct 568 ms 1008464 KB Output is correct
5 Correct 625 ms 1008456 KB Output is correct
6 Correct 632 ms 1008428 KB Output is correct
7 Correct 830 ms 1008476 KB Output is correct
8 Correct 1008 ms 1008396 KB Output is correct
9 Correct 994 ms 1008620 KB Output is correct
10 Correct 878 ms 1008460 KB Output is correct
11 Correct 507 ms 1008456 KB Output is correct
12 Correct 651 ms 1008472 KB Output is correct
13 Correct 647 ms 1008628 KB Output is correct
14 Correct 667 ms 1008536 KB Output is correct
15 Correct 933 ms 1008552 KB Output is correct
16 Correct 916 ms 1008616 KB Output is correct
17 Correct 952 ms 1008520 KB Output is correct
18 Correct 1105 ms 1008456 KB Output is correct
19 Correct 1018 ms 1008456 KB Output is correct
20 Correct 1008 ms 1008628 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 1008524 KB Output is correct
2 Correct 588 ms 1008456 KB Output is correct
3 Correct 594 ms 1008456 KB Output is correct
4 Correct 564 ms 1008472 KB Output is correct
5 Correct 575 ms 1008440 KB Output is correct
6 Correct 565 ms 1008712 KB Output is correct
7 Correct 559 ms 1008456 KB Output is correct
8 Correct 600 ms 1008516 KB Output is correct
9 Incorrect 567 ms 1008456 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 1008524 KB Output is correct
2 Correct 588 ms 1008456 KB Output is correct
3 Correct 594 ms 1008456 KB Output is correct
4 Correct 564 ms 1008472 KB Output is correct
5 Correct 575 ms 1008440 KB Output is correct
6 Correct 565 ms 1008712 KB Output is correct
7 Correct 559 ms 1008456 KB Output is correct
8 Correct 600 ms 1008516 KB Output is correct
9 Incorrect 567 ms 1008456 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 1008524 KB Output is correct
2 Correct 588 ms 1008456 KB Output is correct
3 Correct 594 ms 1008456 KB Output is correct
4 Correct 564 ms 1008472 KB Output is correct
5 Correct 575 ms 1008440 KB Output is correct
6 Correct 565 ms 1008712 KB Output is correct
7 Correct 559 ms 1008456 KB Output is correct
8 Correct 600 ms 1008516 KB Output is correct
9 Incorrect 567 ms 1008456 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1084 ms 1008632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 1008420 KB Output is correct
2 Correct 573 ms 1008456 KB Output is correct
3 Correct 583 ms 1008456 KB Output is correct
4 Correct 568 ms 1008464 KB Output is correct
5 Correct 625 ms 1008456 KB Output is correct
6 Correct 632 ms 1008428 KB Output is correct
7 Correct 830 ms 1008476 KB Output is correct
8 Correct 1008 ms 1008396 KB Output is correct
9 Correct 994 ms 1008620 KB Output is correct
10 Correct 878 ms 1008460 KB Output is correct
11 Correct 507 ms 1008456 KB Output is correct
12 Correct 651 ms 1008472 KB Output is correct
13 Correct 647 ms 1008628 KB Output is correct
14 Correct 667 ms 1008536 KB Output is correct
15 Correct 933 ms 1008552 KB Output is correct
16 Correct 916 ms 1008616 KB Output is correct
17 Correct 952 ms 1008520 KB Output is correct
18 Correct 1105 ms 1008456 KB Output is correct
19 Correct 1018 ms 1008456 KB Output is correct
20 Correct 1008 ms 1008628 KB Output is correct
21 Correct 506 ms 1008524 KB Output is correct
22 Correct 588 ms 1008456 KB Output is correct
23 Correct 594 ms 1008456 KB Output is correct
24 Correct 564 ms 1008472 KB Output is correct
25 Correct 575 ms 1008440 KB Output is correct
26 Correct 565 ms 1008712 KB Output is correct
27 Correct 559 ms 1008456 KB Output is correct
28 Correct 600 ms 1008516 KB Output is correct
29 Incorrect 567 ms 1008456 KB Output isn't correct
30 Halted 0 ms 0 KB -