oj.uz

Submission #855556

# Submission time Handle Problem Language Result Execution time Memory
855556 2023-10-01T12:23:52 Z iulia_morariu Self Study (JOI22_ho_t2) C++14
10 / 100
 95 ms 28056 KB 
#include <bits/stdc++.h>

using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b){
    if(a.first != b.first) return a.first > b.first;
    else return a.second > b.second;
}

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

    //1.
    int n, m;
    bool eg = 1;

    //2.
    cin >> n >> m;
    long long int a[n], b[n];
    pair <int, int> c[n];

    //3.
    for(int i = 0; i < n; i++) cin >> c[i].first;
    for(int i = 0; i < n; i++){
        cin >> c[i].second;
        if(c[i].first != c[i].second) eg = 0;
        if(c[i].first < c[i].second) c[i].first = c[i].second;
    }

    long long int v[n][m + 1];
    sort(c + 0, c + n, cmp );

    for(int i = 0; i < n; i++){
        a[i] = c[i].first;
        b[i] = c[i].second;
    }
/*
    cout << "b : ";
    for(int i = 0; i < n; i++) cout << b[i] << " ";
    cout << endl;
*/
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= m; j++) v[i][j] = 0;
    }
/*
    cout << "a : ";
    for(int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;

    cout << "b : ";
    for(int i = 0; i < n; i++) cout << b[i] << " ";
    cout << endl;
*/
    for(int j = 1; j <= m; j++){
        //cout << "Suntem la ziua " << j << endl;
        priority_queue< pair<long long int, long long int>,
        vector< pair<long long int, long long int> >,
        greater< pair<long long int, long long int> > > q;

        long long int mini = LLONG_MAX;
        for(int i = 0; i < n; i++){
            mini = min(mini, v[i][j - 1]);
        }

        int spare = 0;
        for(int i = 0; i < n; i++){
            //cout << "  -- > nr " << v[i][j] << "   mini = " << mini << endl;
            if(v[i][j - 1] == mini){
                //cout << "  -- > mai add un " << a[i] << endl;
                v[i][j] = v[i][j - 1] + a[i];
            }else{
                v[i][j] = v[i][j - 1];
                spare++;
                //cout << "  -- > lasam spare" << endl;
            }
            q.push( make_pair( v[i][j] , i ) );
        }

        while(!q.empty() && spare > 0){
            //cout << "    -- > q.top() = " << q.top().first << " " << q.top().second << endl;
            int p = q.top().second;
            q.pop();
            long long int nx = v[p][j] + 1;
            if(!q.empty()) nx = q.top().first;



            while(v[p][j] <= nx && spare > 0){
                if(v[p][j] == v[p][j - 1]){
                    //cout << "      -- > C1" << endl;
                    v[p][j] += a[p];
                }else{
                    v[p][j] += b[p];
                    //cout << "      -- > b[p] = " << b[p] << endl;
                    //cout << "      -- > C2" << endl;
                }

                spare--;
            }


            //q.pop();
        }

        //cout << "  -- > v[" << j << "] : ";
        //for(int i = 0; i < n; i++) cout << v[i][j] << " ";
        //cout << endl;
        //cout <<  " brk";

    }


    //cout << "iesit" << endl;

    long long int mini = LLONG_MAX;

    for(int i = 0; i < n; i++) mini = min(mini, v[i][m]);
    cout << mini << endl;




    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:15:10: warning: variable 'eg' set but not used [-Wunused-but-set-variable]
   15 |     bool eg = 1;
      |          ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 94 ms 21684 KB Output is correct
12 Correct 92 ms 21192 KB Output is correct
13 Correct 56 ms 22468 KB Output is correct
14 Correct 57 ms 21936 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 48 ms 22728 KB Output is correct
17 Correct 72 ms 28056 KB Output is correct
18 Correct 95 ms 27588 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 48 ms 22728 KB Output is correct
3 Correct 72 ms 28056 KB Output is correct
4 Correct 95 ms 27588 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 94 ms 21684 KB Output is correct
12 Correct 92 ms 21192 KB Output is correct
13 Correct 56 ms 22468 KB Output is correct
14 Correct 57 ms 21936 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 94 ms 21684 KB Output is correct
12 Correct 92 ms 21192 KB Output is correct
13 Correct 56 ms 22468 KB Output is correct
14 Correct 57 ms 21936 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -