oj.uz

Submission #871857

# Submission time Handle Problem Language Result Execution time Memory
871857 2023-11-11T18:11:25 Z HorizonWest Let's Win the Election (JOI22_ho_t3) C++17
5 / 100
 2500 ms 1002884 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define db double
#define ll __int128
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;
 
const int Max = 1e6 + 7, Inf = 1e9 + 7;
 
void print(bool x) { cout << (x ? "YES" : "NO") << endl; }
 
string tostring (__int128 x)
{
    string ans = "";
    while(x > 0)
    {
        ans += (x % 10 + '0');
        x /= 10;
    }
    reverse(all(ans));
    return ans;
}
 
void printdb(double ans, int k)
{
    cout << setiosflags(ios::fixed)
         << setiosflags(ios::showpoint)
         << setprecision(k) << ans << endl;
}

pair <db, db> fmin(pair<db, db> a, pair <db, db> b, db j)
{
    if(db(a.fs + a.sd / j) < db(b.fs + b.sd / j))
        return a; 
    else   
        return b; 
}
 
int prec(vector <pair<db, db>> a, vector <pair<db, db>> b, int n, int m)
{
    vector <db> take(n, 1); 

    for(db i = 1; i <= m; i++)
    {
        db Z1 = 0.0, Z2 = b[i-1].fs / i; int cnt = i - 1;   //cerr << b[i-1].fs << endl; 
        
        for(int j = 0; j < n; j++)
        {
            //cerr << a[j].fs << " "; 
            if(cnt == m) break;
            Z1 += take[a[j].sd] * a[j].fs / i; 
            cnt += take[a[j].sd];
        } 
        
        cnt = i; take[b[i-1].sd] = 0;  

        for(int j = 0; j < n; j++)
        {
            if(cnt == m) break;
            Z2 += take[a[j].sd] * a[j].fs / (i + 1); 
            cnt += take[a[j].sd]; 
        }

        //cerr << Z1 << " " << Z2 << endl; 

        if(Z1 <= Z2) return i; 
    }

    return m; 
}

void solve()
{
    int n, m; cin >> n >> m; 
    vector <pair<db, db>> v(n), a(n), b(n);

    for(int i = 0; i < n; i++) 
    {
        cin >> v[i].sd >> v[i].fs;
        if(v[i].fs == -1) v[i].fs = Inf;
        a[i].fs = v[i].sd; b[i].fs = v[i].fs; 
        a[i].sd = b[i].sd = i;   
    } 

    sort(all(v)); sort(all(a)); sort(all(b)); 
    
    db ans = Inf; int fx = prec(a, b, n, m); 
    //cerr << fx << endl; 
    for(db l = fx; l <= min(fx + 3, m); l++)
    {
        vector <vector<vector<db>>> dp(n + 2, vector <vector<db>> (
            m + 2, vector <db> (m + 2, Inf)
        )); dp[0][1][0] = 0.000; 
        
        for(db i = 0; i < n; i++)
        {
            for(db j = 1; j <= l; j++)
            {
                for(db k = 0; k <= m; k++)
                {
                    dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k]);  
                    dp[i+1][j][k+1] = min(dp[i+1][j][k+1], dp[i][j][k] + v[i].sd / l); 
                    if(v[i].fs != Inf)
                    {
                        dp[i+1][j+1][k+1] = min(dp[i+1][j+1][k+1], dp[i][j][k] + v[i].fs / j); 
                    } 
                }
            }
            ans = min(ans, dp[i+1][l][m]); 
        }
    }
 
    printdb(ans, 5); 
}
 
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int Q = 1; //cin >> Q;
 
    while (Q--)
    {
        solve();
    }
 
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 23 ms 12124 KB Output is correct
6 Correct 121 ms 66028 KB Output is correct
7 Correct 450 ms 255452 KB Output is correct
8 Correct 968 ms 565924 KB Output is correct
9 Correct 1611 ms 1002884 KB Output is correct
10 Correct 858 ms 495436 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 23 ms 12124 KB Output is correct
6 Correct 121 ms 66028 KB Output is correct
7 Correct 450 ms 255452 KB Output is correct
8 Correct 968 ms 565924 KB Output is correct
9 Correct 1611 ms 1002884 KB Output is correct
10 Correct 858 ms 495436 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 95 ms 94240 KB Output is correct
13 Correct 283 ms 94392 KB Output is correct
14 Correct 221 ms 94548 KB Output is correct
15 Correct 433 ms 495172 KB Output is correct
16 Correct 1379 ms 495440 KB Output is correct
17 Correct 1092 ms 495368 KB Output is correct
18 Correct 871 ms 1002596 KB Output is correct
19 Execution timed out 2573 ms 1002640 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 23 ms 12124 KB Output is correct
6 Correct 121 ms 66028 KB Output is correct
7 Correct 450 ms 255452 KB Output is correct
8 Correct 968 ms 565924 KB Output is correct
9 Correct 1611 ms 1002884 KB Output is correct
10 Correct 858 ms 495436 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 95 ms 94240 KB Output is correct
13 Correct 283 ms 94392 KB Output is correct
14 Correct 221 ms 94548 KB Output is correct
15 Correct 433 ms 495172 KB Output is correct
16 Correct 1379 ms 495440 KB Output is correct
17 Correct 1092 ms 495368 KB Output is correct
18 Correct 871 ms 1002596 KB Output is correct
19 Execution timed out 2573 ms 1002640 KB Time limit exceeded
20 Halted 0 ms 0 KB -