제출 #834519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
834519		mindiyak	메기 농장 (IOI22_fish)	C++17	0 / 100	969 ms	2097152 KiB

fish

#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
• Subtask 2: 0 / 6
• Subtask 3: 0 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16