oj.uz

Submission #691037

# Submission time Handle Problem Language Result Execution time Memory
691037 2023-01-30T22:05:51 Z BobCompetitiveProgramming Catfish Farm (IOI22_fish) C++17
0 / 100
 755 ms 2097152 KB 
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <unordered_set>
#include <cstring>
#include <queue>
#include <array>
using namespace std; using ll=int64_t;
#define rep(i,n) for(ll i=0; i<ll(n); ++i)
#define vi vector<ll>
#define all(x) begin(x), end(x)
#define pi pair<ll, ll>


ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
    vector<array<ll,3>> fish(M);
    vector<vi> prefixWeight(N, vi(N, 0)); // Prefix weight for column.
    rep(i,M){
        fish[i]={Y[i],X[i],W[i]};
        prefixWeight[Y[i]][X[i]] += W[i];
    }

    sort(all(fish)); // Sort by height
    for(ll c=0; c<N; ++c){
        for(ll r=1; r<N; ++r){
            prefixWeight[r][c] += prefixWeight[r-1][c];
        }
    }
    
    vi heightBuilt(N, 0); // Height built per column.

    // If losing less than winning try adding it?
    
    auto diff = [&](ll new_row, ll col){
        // How much new weight it would add to built up to new_row in a column besides col from col.
        return prefixWeight[new_row][col] 
               - prefixWeight[heightBuilt[col]][col];
    };

     
    for(auto f : fish){
        ll curr_row = f[0], curr_col=f[1];
        ll rightLoss=0, leftLoss=0;
        if(curr_col < N-1) rightLoss = diff(curr_row, curr_col +1);
        if(curr_col > 0) leftLoss = diff(curr_row, curr_col-1);


        ll gain = diff(curr_row, curr_col);

        // cout << "Weight : " << f[2] << " rightLoss " << rightLoss << " leftLoss " << leftLoss << " gain " << gain << endl;

        if(curr_col < N-1 && (rightLoss <= leftLoss || curr_col == 0) && rightLoss < gain){
            heightBuilt[curr_col+1] = curr_row;
        }
        if(curr_col > 0 && leftLoss <= (rightLoss || curr_col == N-1) && leftLoss < gain){
            heightBuilt[curr_col-1] = curr_row;
        }
    }

    ll ans=0;
    for(auto f : fish){
        ll row=f[0], col=f[1], weight=f[2];
        if(heightBuilt[col] >= row) continue; // Inside of bridge.
        bool ok=false;
        if(col < N-1) if(heightBuilt[col+1] >= row) ok=true;
        if(col > 0) if(heightBuilt[col-1] >= row) ok=true;
        if(ok) ans+=weight;
    }

    return ans; 
}

/*
int main(){
    ll n, m; cin>>n>>m;
    vi x(n), y(n), w(n);
    rep(i,m){
        cin>>x[i]>>y[i]>>w[i]; 
    }

    cout << max_weights(n,m,x,y,w) << endl;

    return 0; 
}
*/

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 755 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 753 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 753 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 755 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -