oj.uz

Submission #834519

# Submission time Handle Problem Language Result Execution time Memory
834519 2023-08-22T15:10:49 Z mindiyak Catfish Farm (IOI22_fish) C++17
0 / 100
 969 ms 2097152 KB 
#include "fish.h"

#include <vector>
#include <iostream>

#define ll long long
using namespace std;

bool check(int n,vector<vector<ll>> sum,int pos,int length){
  int left=0,right=0,mid=sum[length][pos];
  if(pos>0)left = sum[length][pos-1];
  if(pos<(n-1))right = sum[length][pos+1];

  // cout << pos << " " << length << " " << left << " " << right << " " << mid << endl;
  return ((left+right)>mid);
}

long long max_weights(int N, int M, vector<int> X, vector<int> Y,
                      vector<int> W) {
  vector<vector<int>> grid(N,vector<int>(N,0));
  vector<vector<ll>> sum(N,vector<ll>(N,0));
  for(int i=0;i<M;i++)grid[Y[i]][X[i]] = W[i];
  for(int i=0;i<N;i++){
    sum[i][0] = grid[i][0];
    if(i==0)continue;
    for(int j=0;j<N;j++){
      sum[i][j] = sum[i-1][j] + grid[i][j];
    }
  }

  // for(auto a:grid){
  //   for(int b:a)cout << b << " ";
  //   cout << endl;
  // }

  // cout << "###################################" << endl;

  // for(auto a:sum){
  //   for(int b:a)cout << b << " ";
  //   cout << endl;
  // }
  // cout << "###################################" << endl;


  vector<int> left(N,0);
  vector<int> right(N,N-1);

  while(true){
    int changed = 0;
    for(int i=0;i<N;i++){
      int mid = (left[i] + right[i]) >> 1;
      if(check(N,sum,i,mid)){
        if(left[i] != mid)changed=1;
        left[i] = mid;
      }else{
        if(right[i] != mid)changed=1;
        right[i] = mid;
      }
    }
    if(changed==0)break;
  }


  ll ans = 0;
  for(int i=0;i<N;i++){
    int a=0,b=0;
    if(i>0)a=left[i-1];
    if(i<(N-1))b=left[i+1];
    // cout << i << " " << a << " " << b << " " << left[i] << endl;
    ans += max((ll)0,sum[max(a,b)][i] - sum[left[i]][i]);
  }


  // cout << "###################################" << endl;
  // for(int i=0;i<N;i++){
  //   cout << left[i] <<" ";
  // }cout << endl;
  // for(int i=0;i<N;i++){
  //   cout << right[i] <<" ";
  // }cout << endl;
  // cout << "###################################" << endl;




  

  return ans;
  
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 969 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 676 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: '1'
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: '1'
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: '1'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 676 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 969 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -