結果

問題 No.1008 Bench Craftsman
ユーザー kyort0n
提出日時 2020-03-06 22:20:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,529 bytes
コンパイル時間 1,489 ms
コンパイル使用メモリ 170,960 KB
実行使用メモリ 7,972 KB
最終ジャッジ日時 2024-10-14 07:52:59
合計ジャッジ時間 4,221 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
//const ll mod = 1000000007;
ll N, M;
vector<ll> a;
vector<ll> x, w;
vector<ll> xsum;

bool f(ll c) {
    vector<ll> one(N+3), two(N+3);
    for(int i = 0; i < M; i++) {
        ll delta;
        if(c != 0) delta = w[i] / c;
        else delta = N;
        ll l = x[i] - delta;
        chmax(l, 0LL);
        two[l+1] += c;
        two[x[i]+1] -= c;
        two[x[i]+1] -= (x[i] - l) * c;
        two[x[i]+2] += (x[i] - l) * c;
        one[l] += max(0LL, w[i] - abs(l - x[i]) * c);
        one[x[i]+1] -= max(0LL, w[i] - abs(l - x[i]) * c);
        ll r = x[i] + delta;
        chmin(r, N);
        //cerr << i << " " << l << " " << r << endl;
        two[x[i]+2] -= c;
        two[r+1] += c;
        two[r+1] -= (r - x[i] - 1) * c;
        two[r+2] += (r - x[i] - 1) * c;
        one[x[i]+1] += max(0LL, w[i] - abs(x[i]+1-x[i]) * c);
        one[r] -= max(0LL, w[i] - abs(x[i]+1-x[i]) * c);
    }
    /*
    cerr << "----" << c << "----" << endl;
    for(int i = 0; i < N; i++) cerr << one[i] << " ";
    cerr << endl;
    for(int i = 0; i < N; i++) cerr << two[i] << " ";
    cerr << endl;
    */
    for(int i = 0; i < N; i++) {
        if(one[i] + two[i] >= a[i]) return false;
    }
    for(int i = 1; i <= N; i++) {
        one[i] += one[i-1];
    }
    for(int i = 1; i <= N; i++) {
        two[i] += two[i-1];
    }
    for(int i = 1; i <= N; i++) {
        two[i] += two[i-1];
    }
    return true;
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    a.resize(N);
    for(int i = 0; i < N; i++) {
        cin >> a[i];
    }
    x.resize(M);
    xsum.resize(N);
    w.resize(M);
    for(int i = 0; i < M; i++) {
        cin >> x[i] >> w[i];
        x[i]--;
        xsum[x[i]] += w[i];
        if(xsum[x[i]] >= a[x[i]]) {
            cout << -1 << endl;
            return 0;
        }
    }
    ll ok = N + 1;
    ll ng = -1;
    while(abs(ok - ng) > 1) {
        ll mid = (ok + ng) / 2;
        if(f(mid)) ok = mid;
        else ng = mid;
    }
    cout << ok << endl;
    return 0;
}
0