제출 #491511

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
491511		Yazan_Alattar	금 캐기 (IZhO14_divide)	C++14	100 / 100	50 ms	6964 KiB

divide

#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <assert.h>
#include <numeric>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 100007;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

ll n, x[M], g[M], d[M], seg[4 * M], ans, add;

void upd(int i, ll v, int node = 1, int l = 1, int r = n)
{
    if(l == r){
        seg[node] = v;
        return;
    }
    int mid = (l + r) / 2;
    if(i <= mid) upd(i, v, 2 * node, l, mid);
    else upd(i, v, 2 * node + 1, mid + 1, r);
    seg[node] = max(seg[2 * node], seg[2 * node + 1]);
    return;
}

int get(int st, int en, int node = 1, int l = 1, int r = n)
{
    if(seg[node] + add < 0) return -1;
    if(l == r) return l;
    int mid = (l + r) / 2;
    int ret = get(st, en, 2 * node + 1, mid + 1, r);
    if(ret == -1) ret = get(st, en, 2 * node, l, mid);
    return ret;
}

int main()
{
    scanf("%lld", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%lld%lld%lld", &x[i], &g[i], &d[i]);
        g[i] += g[i - 1];
        d[i] += d[i - 1];
        upd(i, d[i] - x[i]);
    }
    for(int i = 1; i <= n; ++i){
        add += x[i] - x[i - 1];
        if(i > 1) add += -d[i - 1] + d[i - 2];
        ans = max(ans, g[get(i, n)] - g[i - 1]);
    }
    printf("%lld\n", ans);
    return 0;
}
// Don't forget special cases. (n = 1?)
// Look for the constraints. (Runtime array? overflow?)

컴파일 시 표준 에러 (stderr) 메시지

divide.cpp: In function 'int main()':
divide.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%lld", &n);
      |     ~~~~~^~~~~~~~~~~~
divide.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%lld%lld%lld", &x[i], &g[i], &d[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52