結果

問題 No.1008 Bench Craftsman
コンテスト
ユーザー どらら
提出日時 2020-03-06 23:58:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 694 ms / 2,000 ms
コード長 2,204 bytes
コンパイル時間 1,752 ms
コンパイル使用メモリ 174,916 KB
実行使用メモリ 8,840 KB
最終ジャッジ日時 2024-10-14 10:14:35
合計ジャッジ時間 12,906 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

bool check(ll c, const vector<ll>& v, const vector<pair<ll,ll>>& w){
  if(c == -1) return false;

  vector<ll> base(v.size()+1, 0);
  vector<ll> imos(v.size()+1, 0);
  vector<ll> diff(v.size()+1, 0);

  rep(i,w.size()){
    ll j = w[i].first;
    ll k = w[i].second;

    ll lhs_i, rhs_i;
    ll lhs_w, rhs_w;

    {
      ll lb = 0, ub = v.size();
      while(ub-lb>1){
        ll mid = (lb+ub)/2;
        
        if(j-mid<0) ub = mid;
        else{
          if(k-c*mid<0) ub = mid;
          else lb = mid;
        }
      }
      lhs_i = j-lb;
      lhs_w = k-c*lb;
    }
    {
      ll lb = 0, ub = v.size();
      while(ub-lb>1){
        ll mid = (lb+ub)/2;
        
        if(j+mid>=v.size()) ub = mid;
        else{
          if(k-c*mid<0) ub = mid;
          else lb = mid;
        }
      }
      rhs_i = j+lb;
      rhs_w = k-c*lb;
    }

    //cout << j << " " << k << " " << lhs_i << " " << lhs_w << " " << rhs_i << " " << rhs_w << endl;
    
    base[lhs_i] += lhs_w;
    imos[lhs_i] += c;
    imos[j] -= c;

    imos[j] -= c;
    imos[rhs_i] += c;
    base[rhs_i+1] -= rhs_w;
  }

  ll imos_base = 0;
  rep(i,imos.size()){
    imos_base += imos[i];
    diff[i] = imos_base;
  }


  bool flg = true; 
  ll ww = 0;
  rep(i,v.size()){
    ww += base[i];
    //cout << i << "\t" << ww << endl;
    if(v[i]<=ww) flg = false;
    ww += diff[i];
  }
  
  return flg;
}


int main(){
  int N, M;
  cin >> N >> M;
  vector<ll> v;
  rep(i,N){
    ll a;
    cin >> a;
    v.push_back(a);
  }

  vector<ll> sum(N,0);
  vector<pair<ll,ll>> w;
  rep(i,M){
    ll a, b;
    cin >> a >> b;
    a--;
    sum[a] += b;
    w.emplace_back(a,b);
  }

  rep(i,N){
    if(sum[i] >= v[i]){
      cout << -1 << endl;
      return 0;
    }
  }

  
  ll lb=-1, ub=1e12;
  while(ub-lb>1){
    ll mid = (lb+ub)/2;
    if(!check(mid, v, w)) lb = mid;
    else ub = mid;
  }
  
  cout << ub << endl;
  
  return 0;
}
0