44832023-03-28 13:31:39semmiDinamitcpp17Hibás válasz 23/503ms4264 KiB
#include <bits/stdc++.h>

using namespace std;


int main() {

    int a, b, c;
    cin >> a >> b >> c;
    vector<vector<int>> oszlop(a+1, vector<int>(b+1)), // saving the rows and columns
    dp(a+1, vector<int>(b+1,INT_MAX)), backtrack(a+1, vector<int>(b+1)); // backtrack saves the shortest path
    
    for(int i = 1;i<=a;i++ ) {
        for(int z = 1;z<=b;z++ ) {
            cin >> oszlop[i][z];
        }
    } // saving all the data



    dp[1][1] = oszlop[1][1]; // default dp initialization

    backtrack[1][1] = -1; // means it is the end of the road

    for(int i = 2;i<=b;i++ ) {
        dp[1][i] = dp[1][i-1] + oszlop[1][i];
        backtrack[1][i] = 1;
    }

    for(int i = 2;i<=a;i++ ) {
        dp[i][1] = dp[i-1][1] + oszlop[i][1];
        backtrack[i][1] = 0;
    }
    
    // pre initialization 

    // 1 ha balra kulonben 0 ha felfele
    for(int i = 2;i<=a;i++ ) {
        for(int z = 2;z<=b;z++ ) {
            dp[i][z] = min(dp[i-1][z], dp[i][z-1]) + oszlop[i][z];
            if(dp[i-1][z] > dp[i][z-1]) backtrack[i][z] = 1;
            else backtrack[i][z]= 0;
        }
    }


    vector<int> visszafejt;
    vector<int> ans;
    int x = a, y = b;
    priority_queue<int> elemek;
    int sum = 0;
    while(backtrack[x][y] != -1) {
        elemek.push(oszlop[x][y]);
        ans.push_back(oszlop[x][y]);
        if(backtrack[x][y] == 0) {
            x--;
        } else {
            y--;
        }
    }
    ans.push_back(oszlop[1][1]);
    elemek.push(oszlop[1][1]);


    
    //cout << dp[a][b] << endl;
    long long ansf= dp[a][b];
    for(int i = 0;i < c;i++ ) {
        int temp = elemek.top();
        ansf-= temp - temp/2;
        temp/=2;
        elemek.pop();
        elemek.push(temp);
    }
    // for(int i = 0;i < c;i++ ) {
    //     sort(ans.begin(), ans.end());
    //     long long temp = ans[ans.size()-1]/2;
    //     ansf -= ans[ans.size()-1] - temp;
    //     ans[ans.size()-1]/=2;
    // }
    cout << ansf << endl;
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base23/50
1Elfogadva0/03ms1684 KiB
2Hibás válasz0/03ms1872 KiB
3Elfogadva2/23ms2084 KiB
4Elfogadva2/23ms2296 KiB
5Elfogadva3/33ms2512 KiB
6Elfogadva3/33ms2720 KiB
7Elfogadva2/23ms2936 KiB
8Elfogadva3/33ms3152 KiB
9Hibás válasz0/23ms3328 KiB
10Elfogadva2/23ms3548 KiB
11Elfogadva3/33ms3764 KiB
12Hibás válasz0/33ms3844 KiB
13Hibás válasz0/23ms3848 KiB
14Elfogadva3/33ms3848 KiB
15Hibás válasz0/23ms3864 KiB
16Hibás válasz0/33ms3864 KiB
17Hibás válasz0/23ms3992 KiB
18Hibás válasz0/33ms4052 KiB
19Hibás válasz0/23ms4056 KiB
20Hibás válasz0/33ms4180 KiB
21Hibás válasz0/23ms4264 KiB
22Hibás válasz0/33ms4264 KiB