oj.uz

답안 #86817

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
86817 2018-11-27T15:46:37 Z karma 금 캐기 (IZhO14_divide) C++11
100 / 100
 53 ms 4116 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define pb            push_back

using namespace std;

template <typename T> inline void Cin(T &x)
{
    register char c;
    for (c = getchar(); c < '0' || c > '9'; c = getchar());
    for (x = 0; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

long long res;
int n, Maxv;
vector<long long> v, g, r;
vector<int> t, x;

inline void Update(int x, const int& val)
{
    while(x < Maxv)
    {
        t[x] = min(t[x], val);
        x += (x & -x);
    }
}
inline int Query(int x)
{
    int res = Maxv;
    while(x > 0)
    {
        res = min(res, t[x]);
        x -= (x & -x);
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    Cin(n);
    Maxv = n + 3;
    t.resize(Maxv, Maxv);
    x.resize(n + 1), g.resize(n + 1), r.resize(n + 1);
    g[0] = r[0] = x[0] = 0;
    for(int i = 1; i <= n; ++i)
    {
        Cin(x[i]), Cin(g[i]), Cin(r[i]);
        res = max(res, g[i]);
        g[i] += g[i - 1], r[i] += r[i - 1];
        v.pb(r[i - 1] - x[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    v.pb(v.back() + 1);
    for(int i = 1; i <= n; ++i)
    {
        int j = Query(upper_bound(v.begin(), v.end(), r[i] - x[i]) - v.begin());
        if(j < Maxv) res = max(res, g[i] - g[j - 1]);
        Update(lower_bound(v.begin(), v.end(), r[i - 1] - x[i]) - v.begin() + 1, i);
    }
    cout << res;
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 2 ms 652 KB Output is correct
5 Correct 2 ms 652 KB Output is correct
6 Correct 2 ms 652 KB Output is correct
7 Correct 2 ms 652 KB Output is correct
8 Correct 2 ms 652 KB Output is correct
9 Correct 2 ms 652 KB Output is correct
10 Correct 2 ms 652 KB Output is correct
11 Correct 2 ms 652 KB Output is correct
12 Correct 2 ms 652 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 652 KB Output is correct
2 Correct 2 ms 652 KB Output is correct
3 Correct 3 ms 652 KB Output is correct
4 Correct 2 ms 652 KB Output is correct
5 Correct 2 ms 652 KB Output is correct
6 Correct 3 ms 652 KB Output is correct
7 Correct 2 ms 700 KB Output is correct
8 Correct 3 ms 700 KB Output is correct
9 Correct 3 ms 700 KB Output is correct
10 Correct 3 ms 700 KB Output is correct
11 Correct 6 ms 764 KB Output is correct
12 Correct 4 ms 764 KB Output is correct

Subtask #3
52.0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 764 KB Output is correct
2 Correct 5 ms 1020 KB Output is correct
3 Correct 6 ms 1020 KB Output is correct
4 Correct 23 ms 2428 KB Output is correct
5 Correct 26 ms 2428 KB Output is correct
6 Correct 53 ms 4088 KB Output is correct
7 Correct 42 ms 4116 KB Output is correct
8 Correct 46 ms 4116 KB Output is correct
9 Correct 42 ms 4116 KB Output is correct
10 Correct 42 ms 4116 KB Output is correct
11 Correct 46 ms 4116 KB Output is correct
12 Correct 49 ms 4116 KB Output is correct