oj.uz

Submission #1106180

# Submission time Handle Problem Language Result Execution time Memory
1106180 2024-10-29T13:27:08 Z akim9905 Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 1078 ms 1008744 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-5;

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 (1e9-eps>A[i].second) 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 (abs(a.second-b.second)<eps) 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 479 ms 1008456 KB Output is correct
2 Correct 464 ms 1008456 KB Output is correct
3 Correct 463 ms 1008540 KB Output is correct
4 Correct 519 ms 1008408 KB Output is correct
5 Correct 534 ms 1008548 KB Output is correct
6 Correct 489 ms 1008744 KB Output is correct
7 Correct 425 ms 1008456 KB Output is correct
8 Correct 449 ms 1008576 KB Output is correct
9 Correct 447 ms 1008516 KB Output is correct
10 Correct 445 ms 1008456 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 1008456 KB Output is correct
2 Correct 464 ms 1008456 KB Output is correct
3 Correct 463 ms 1008540 KB Output is correct
4 Correct 519 ms 1008408 KB Output is correct
5 Correct 534 ms 1008548 KB Output is correct
6 Correct 489 ms 1008744 KB Output is correct
7 Correct 425 ms 1008456 KB Output is correct
8 Correct 449 ms 1008576 KB Output is correct
9 Correct 447 ms 1008516 KB Output is correct
10 Correct 445 ms 1008456 KB Output is correct
11 Correct 447 ms 1008456 KB Output is correct
12 Correct 626 ms 1008552 KB Output is correct
13 Correct 590 ms 1008456 KB Output is correct
14 Correct 613 ms 1008620 KB Output is correct
15 Correct 982 ms 1008456 KB Output is correct
16 Correct 884 ms 1008516 KB Output is correct
17 Correct 649 ms 1008432 KB Output is correct
18 Correct 1078 ms 1008456 KB Output is correct
19 Correct 993 ms 1008712 KB Output is correct
20 Correct 661 ms 1008452 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 1008456 KB Output is correct
2 Correct 453 ms 1008456 KB Output is correct
3 Correct 432 ms 1008524 KB Output is correct
4 Correct 446 ms 1008352 KB Output is correct
5 Correct 429 ms 1008456 KB Output is correct
6 Correct 433 ms 1008436 KB Output is correct
7 Correct 489 ms 1008320 KB Output is correct
8 Correct 515 ms 1008456 KB Output is correct
9 Incorrect 450 ms 1008396 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 1008456 KB Output is correct
2 Correct 453 ms 1008456 KB Output is correct
3 Correct 432 ms 1008524 KB Output is correct
4 Correct 446 ms 1008352 KB Output is correct
5 Correct 429 ms 1008456 KB Output is correct
6 Correct 433 ms 1008436 KB Output is correct
7 Correct 489 ms 1008320 KB Output is correct
8 Correct 515 ms 1008456 KB Output is correct
9 Incorrect 450 ms 1008396 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 1008456 KB Output is correct
2 Correct 453 ms 1008456 KB Output is correct
3 Correct 432 ms 1008524 KB Output is correct
4 Correct 446 ms 1008352 KB Output is correct
5 Correct 429 ms 1008456 KB Output is correct
6 Correct 433 ms 1008436 KB Output is correct
7 Correct 489 ms 1008320 KB Output is correct
8 Correct 515 ms 1008456 KB Output is correct
9 Incorrect 450 ms 1008396 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 1008456 KB Output is correct
2 Correct 464 ms 1008456 KB Output is correct
3 Correct 463 ms 1008540 KB Output is correct
4 Correct 519 ms 1008408 KB Output is correct
5 Correct 534 ms 1008548 KB Output is correct
6 Correct 489 ms 1008744 KB Output is correct
7 Correct 425 ms 1008456 KB Output is correct
8 Correct 449 ms 1008576 KB Output is correct
9 Correct 447 ms 1008516 KB Output is correct
10 Correct 445 ms 1008456 KB Output is correct
11 Correct 447 ms 1008456 KB Output is correct
12 Correct 626 ms 1008552 KB Output is correct
13 Correct 590 ms 1008456 KB Output is correct
14 Correct 613 ms 1008620 KB Output is correct
15 Correct 982 ms 1008456 KB Output is correct
16 Correct 884 ms 1008516 KB Output is correct
17 Correct 649 ms 1008432 KB Output is correct
18 Correct 1078 ms 1008456 KB Output is correct
19 Correct 993 ms 1008712 KB Output is correct
20 Correct 661 ms 1008452 KB Output is correct
21 Correct 454 ms 1008456 KB Output is correct
22 Correct 453 ms 1008456 KB Output is correct
23 Correct 432 ms 1008524 KB Output is correct
24 Correct 446 ms 1008352 KB Output is correct
25 Correct 429 ms 1008456 KB Output is correct
26 Correct 433 ms 1008436 KB Output is correct
27 Correct 489 ms 1008320 KB Output is correct
28 Correct 515 ms 1008456 KB Output is correct
29 Incorrect 450 ms 1008396 KB Output isn't correct
30 Halted 0 ms 0 KB -