제출 #855556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
855556		iulia_morariu	Self Study (JOI22_ho_t2)	C++14	10 / 100	95 ms	28056 KiB

Main

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 9