oj.uz

Submission #1106187

# Submission time Handle Problem Language Result Execution time Memory
1106187 2024-10-29T13:32:17 Z akim9905 Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 1069 ms 1008708 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 (A[i].second<1e9) 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 500 ms 1008388 KB Output is correct
2 Correct 448 ms 1008456 KB Output is correct
3 Correct 463 ms 1008380 KB Output is correct
4 Correct 470 ms 1008456 KB Output is correct
5 Correct 481 ms 1008456 KB Output is correct
6 Correct 487 ms 1008620 KB Output is correct
7 Correct 469 ms 1008552 KB Output is correct
8 Correct 466 ms 1008432 KB Output is correct
9 Correct 420 ms 1008456 KB Output is correct
10 Correct 430 ms 1008552 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 1008388 KB Output is correct
2 Correct 448 ms 1008456 KB Output is correct
3 Correct 463 ms 1008380 KB Output is correct
4 Correct 470 ms 1008456 KB Output is correct
5 Correct 481 ms 1008456 KB Output is correct
6 Correct 487 ms 1008620 KB Output is correct
7 Correct 469 ms 1008552 KB Output is correct
8 Correct 466 ms 1008432 KB Output is correct
9 Correct 420 ms 1008456 KB Output is correct
10 Correct 430 ms 1008552 KB Output is correct
11 Correct 429 ms 1008552 KB Output is correct
12 Correct 565 ms 1008456 KB Output is correct
13 Correct 525 ms 1008456 KB Output is correct
14 Correct 522 ms 1008456 KB Output is correct
15 Correct 945 ms 1008624 KB Output is correct
16 Correct 832 ms 1008392 KB Output is correct
17 Correct 629 ms 1008400 KB Output is correct
18 Correct 1069 ms 1008456 KB Output is correct
19 Correct 837 ms 1008624 KB Output is correct
20 Correct 589 ms 1008456 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 1008456 KB Output is correct
2 Correct 502 ms 1008456 KB Output is correct
3 Correct 502 ms 1008500 KB Output is correct
4 Correct 496 ms 1008372 KB Output is correct
5 Correct 453 ms 1008412 KB Output is correct
6 Correct 435 ms 1008332 KB Output is correct
7 Correct 438 ms 1008708 KB Output is correct
8 Correct 433 ms 1008456 KB Output is correct
9 Incorrect 450 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 497 ms 1008456 KB Output is correct
2 Correct 502 ms 1008456 KB Output is correct
3 Correct 502 ms 1008500 KB Output is correct
4 Correct 496 ms 1008372 KB Output is correct
5 Correct 453 ms 1008412 KB Output is correct
6 Correct 435 ms 1008332 KB Output is correct
7 Correct 438 ms 1008708 KB Output is correct
8 Correct 433 ms 1008456 KB Output is correct
9 Incorrect 450 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 497 ms 1008456 KB Output is correct
2 Correct 502 ms 1008456 KB Output is correct
3 Correct 502 ms 1008500 KB Output is correct
4 Correct 496 ms 1008372 KB Output is correct
5 Correct 453 ms 1008412 KB Output is correct
6 Correct 435 ms 1008332 KB Output is correct
7 Correct 438 ms 1008708 KB Output is correct
8 Correct 433 ms 1008456 KB Output is correct
9 Incorrect 450 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 1026 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 500 ms 1008388 KB Output is correct
2 Correct 448 ms 1008456 KB Output is correct
3 Correct 463 ms 1008380 KB Output is correct
4 Correct 470 ms 1008456 KB Output is correct
5 Correct 481 ms 1008456 KB Output is correct
6 Correct 487 ms 1008620 KB Output is correct
7 Correct 469 ms 1008552 KB Output is correct
8 Correct 466 ms 1008432 KB Output is correct
9 Correct 420 ms 1008456 KB Output is correct
10 Correct 430 ms 1008552 KB Output is correct
11 Correct 429 ms 1008552 KB Output is correct
12 Correct 565 ms 1008456 KB Output is correct
13 Correct 525 ms 1008456 KB Output is correct
14 Correct 522 ms 1008456 KB Output is correct
15 Correct 945 ms 1008624 KB Output is correct
16 Correct 832 ms 1008392 KB Output is correct
17 Correct 629 ms 1008400 KB Output is correct
18 Correct 1069 ms 1008456 KB Output is correct
19 Correct 837 ms 1008624 KB Output is correct
20 Correct 589 ms 1008456 KB Output is correct
21 Correct 497 ms 1008456 KB Output is correct
22 Correct 502 ms 1008456 KB Output is correct
23 Correct 502 ms 1008500 KB Output is correct
24 Correct 496 ms 1008372 KB Output is correct
25 Correct 453 ms 1008412 KB Output is correct
26 Correct 435 ms 1008332 KB Output is correct
27 Correct 438 ms 1008708 KB Output is correct
28 Correct 433 ms 1008456 KB Output is correct
29 Incorrect 450 ms 1008456 KB Output isn't correct
30 Halted 0 ms 0 KB -