oj.uz

Submission #853056

# Submission time Handle Problem Language Result Execution time Memory
853056 2023-09-23T11:19:06 Z mkorzybski Let's Win the Election (JOI22_ho_t3) C++17
11 / 100
 2500 ms 1048576 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<ll,ll>
#define f first
#define s second


ll n, k;
const ll N = 507;
ll A[N], B[N];
ld minWynik = (ld) 10000000;
vector <vector<pii>> maskiV;


void maski(ll bit, ll rozm, vector <pii> x)
{
    if(bit > rozm) maskiV.push_back(x);

    for(ll i=1; i<=n; i++)
    {
        bool nieMa = true;
        for(pii v : x) if(v.f == i) nieMa = false;
        if(!nieMa) continue;

        x.push_back({i,1});
        maski(bit+1, rozm, x);
        if(B[i] != -1)
        {
            x[bit-1].s = 2;
            maski(bit+1, rozm, x);
        }
        x.erase(x.begin() + bit-1);
    }
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    for(ll i=1; i<=n; i++)
    {
        cin >> A[i] >> B[i];
    }

    vector <pii> tmpV;
    maski(1, k, tmpV);

    /*ll licznik = 0;
    for(vector <pii> x : maskiV)
    {
        cout << endl << ++licznik << endl;
        for(pii v : x) cout << v.f << ',' << v.s << " ";
    }*/

    for(vector <pii> x : maskiV)
    {
        ld wynik = 0;
        ld wsp = 1;

        for(pii v : x)
        {
            if(v.s == 1)
            {
                wynik += (ld) A[v.f] / wsp;
            }
            else
            {
                wynik += (ld) B[v.f] / wsp;
                wsp += 1;
            }
        }

        if(wynik == -1)
        {
            cout << endl;
            for(pii v : x)
            {
                cout << v.f << "," << v.s << " ";
            }
            cout << endl << wynik;
        }
        minWynik = min(minWynik, wynik);
    }

    cout << fixed << setprecision(7) << minWynik;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Execution timed out 2528 ms 208376 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Execution timed out 2528 ms 208376 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 44540 KB Output is correct
2 Correct 120 ms 88064 KB Output is correct
3 Correct 36 ms 24840 KB Output is correct
4 Correct 227 ms 174308 KB Output is correct
5 Correct 220 ms 148672 KB Output is correct
6 Correct 205 ms 140544 KB Output is correct
7 Correct 163 ms 98016 KB Output is correct
8 Correct 215 ms 148708 KB Output is correct
9 Correct 215 ms 148708 KB Output is correct
10 Correct 215 ms 148676 KB Output is correct
11 Correct 239 ms 148704 KB Output is correct
12 Correct 216 ms 148716 KB Output is correct
13 Correct 214 ms 148572 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 167 ms 97548 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 44540 KB Output is correct
2 Correct 120 ms 88064 KB Output is correct
3 Correct 36 ms 24840 KB Output is correct
4 Correct 227 ms 174308 KB Output is correct
5 Correct 220 ms 148672 KB Output is correct
6 Correct 205 ms 140544 KB Output is correct
7 Correct 163 ms 98016 KB Output is correct
8 Correct 215 ms 148708 KB Output is correct
9 Correct 215 ms 148708 KB Output is correct
10 Correct 215 ms 148676 KB Output is correct
11 Correct 239 ms 148704 KB Output is correct
12 Correct 216 ms 148716 KB Output is correct
13 Correct 214 ms 148572 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 167 ms 97548 KB Output is correct
16 Runtime error 1274 ms 1048576 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 44540 KB Output is correct
2 Correct 120 ms 88064 KB Output is correct
3 Correct 36 ms 24840 KB Output is correct
4 Correct 227 ms 174308 KB Output is correct
5 Correct 220 ms 148672 KB Output is correct
6 Correct 205 ms 140544 KB Output is correct
7 Correct 163 ms 98016 KB Output is correct
8 Correct 215 ms 148708 KB Output is correct
9 Correct 215 ms 148708 KB Output is correct
10 Correct 215 ms 148676 KB Output is correct
11 Correct 239 ms 148704 KB Output is correct
12 Correct 216 ms 148716 KB Output is correct
13 Correct 214 ms 148572 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 167 ms 97548 KB Output is correct
16 Runtime error 1274 ms 1048576 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2540 ms 116872 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Execution timed out 2528 ms 208376 KB Time limit exceeded
6 Halted 0 ms 0 KB -