#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, -1); // 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.
if(heightBuilt[col] == -1) return prefixWeight[new_row][col];
else 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 << " row : " << curr_row << endl;
//cout << "Weight : " << f[2] << " rightLoss " << rightLoss << " leftLoss " << leftLoss << " gain " << gain << " col : " << curr_col << 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;
}
//for(auto h : heightBuilt) cout << h << " "; cout << endl;
}
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(){
int n, m; cin>>n>>m;
vector<int> 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;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
807 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
757 ms |
2097152 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
709 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
304 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
468 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '186185954668' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
304 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
468 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '186185954668' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
304 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
468 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '186185954668' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
709 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
807 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
