oj.uz

Submission #1106177

# Submission time Handle Problem Language Result Execution time Memory
1106177 2024-10-29T13:25:37 Z akim9905 Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 1179 ms 1008788 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>-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 (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 451 ms 1008788 KB Output is correct
2 Correct 462 ms 1008432 KB Output is correct
3 Correct 464 ms 1008456 KB Output is correct
4 Correct 470 ms 1008456 KB Output is correct
5 Correct 490 ms 1008456 KB Output is correct
6 Correct 557 ms 1008456 KB Output is correct
7 Correct 694 ms 1008504 KB Output is correct
8 Correct 856 ms 1008512 KB Output is correct
9 Correct 960 ms 1008620 KB Output is correct
10 Correct 936 ms 1008524 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 1008788 KB Output is correct
2 Correct 462 ms 1008432 KB Output is correct
3 Correct 464 ms 1008456 KB Output is correct
4 Correct 470 ms 1008456 KB Output is correct
5 Correct 490 ms 1008456 KB Output is correct
6 Correct 557 ms 1008456 KB Output is correct
7 Correct 694 ms 1008504 KB Output is correct
8 Correct 856 ms 1008512 KB Output is correct
9 Correct 960 ms 1008620 KB Output is correct
10 Correct 936 ms 1008524 KB Output is correct
11 Correct 478 ms 1008468 KB Output is correct
12 Correct 570 ms 1008560 KB Output is correct
13 Correct 555 ms 1008456 KB Output is correct
14 Correct 565 ms 1008456 KB Output is correct
15 Correct 918 ms 1008620 KB Output is correct
16 Correct 871 ms 1008456 KB Output is correct
17 Correct 864 ms 1008456 KB Output is correct
18 Correct 969 ms 1008612 KB Output is correct
19 Correct 1025 ms 1008456 KB Output is correct
20 Correct 969 ms 1008452 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 1008372 KB Output is correct
2 Correct 425 ms 1008352 KB Output is correct
3 Correct 422 ms 1008396 KB Output is correct
4 Correct 471 ms 1008452 KB Output is correct
5 Correct 476 ms 1008456 KB Output is correct
6 Correct 483 ms 1008456 KB Output is correct
7 Correct 503 ms 1008508 KB Output is correct
8 Correct 527 ms 1008504 KB Output is correct
9 Incorrect 538 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 436 ms 1008372 KB Output is correct
2 Correct 425 ms 1008352 KB Output is correct
3 Correct 422 ms 1008396 KB Output is correct
4 Correct 471 ms 1008452 KB Output is correct
5 Correct 476 ms 1008456 KB Output is correct
6 Correct 483 ms 1008456 KB Output is correct
7 Correct 503 ms 1008508 KB Output is correct
8 Correct 527 ms 1008504 KB Output is correct
9 Incorrect 538 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 436 ms 1008372 KB Output is correct
2 Correct 425 ms 1008352 KB Output is correct
3 Correct 422 ms 1008396 KB Output is correct
4 Correct 471 ms 1008452 KB Output is correct
5 Correct 476 ms 1008456 KB Output is correct
6 Correct 483 ms 1008456 KB Output is correct
7 Correct 503 ms 1008508 KB Output is correct
8 Correct 527 ms 1008504 KB Output is correct
9 Incorrect 538 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 1179 ms 1008624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 1008788 KB Output is correct
2 Correct 462 ms 1008432 KB Output is correct
3 Correct 464 ms 1008456 KB Output is correct
4 Correct 470 ms 1008456 KB Output is correct
5 Correct 490 ms 1008456 KB Output is correct
6 Correct 557 ms 1008456 KB Output is correct
7 Correct 694 ms 1008504 KB Output is correct
8 Correct 856 ms 1008512 KB Output is correct
9 Correct 960 ms 1008620 KB Output is correct
10 Correct 936 ms 1008524 KB Output is correct
11 Correct 478 ms 1008468 KB Output is correct
12 Correct 570 ms 1008560 KB Output is correct
13 Correct 555 ms 1008456 KB Output is correct
14 Correct 565 ms 1008456 KB Output is correct
15 Correct 918 ms 1008620 KB Output is correct
16 Correct 871 ms 1008456 KB Output is correct
17 Correct 864 ms 1008456 KB Output is correct
18 Correct 969 ms 1008612 KB Output is correct
19 Correct 1025 ms 1008456 KB Output is correct
20 Correct 969 ms 1008452 KB Output is correct
21 Correct 436 ms 1008372 KB Output is correct
22 Correct 425 ms 1008352 KB Output is correct
23 Correct 422 ms 1008396 KB Output is correct
24 Correct 471 ms 1008452 KB Output is correct
25 Correct 476 ms 1008456 KB Output is correct
26 Correct 483 ms 1008456 KB Output is correct
27 Correct 503 ms 1008508 KB Output is correct
28 Correct 527 ms 1008504 KB Output is correct
29 Incorrect 538 ms 1008456 KB Output isn't correct
30 Halted 0 ms 0 KB -