oj.uz

답안 #86767

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
86767 2018-11-27T10:18:43 Z vanbang9710 금 캐기 (IZhO14_divide) C++14
100 / 100
 56 ms 3584 KB 
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<climits>
#include<cstring>
#include<iomanip>
#include<string>
#include<bitset>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<algorithm>
#include<functional>
#include<chrono>
//#include<windows.h>
//#include<direct.h>
#include<random>
#include<sstream>
 
#define y0 asdahsdlkahsdad
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define taskname "divide"
//#define GuiltiaSinJurai
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
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';
}
 
const int maxN = 1e5 + 1;
const ll LInf = 1e15;
 
struct TMine
{
    int x, g, d;
};
vector<TMine> p;
int n, m;
ll lab[maxN], sg, sd, ans = 0;
vector<ll> v;
 
inline void Update(int i, ll val) { for (; i <= m; i += i & -i) lab[i] = min(lab[i], val); }
inline ll Get(int i) { ll res = LInf; for (; i > 0; i &= i - 1) res = min(res, lab[i]); return res; }
 
int main()
{
    #ifdef GuiltiaSinJurai
    auto start = chrono::steady_clock::now();
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(taskname".inp", "r", stdin);
    //freopen(taskname".out", "w", stdout);
 
    Cin(n);
    sd = 0;
    p.resize(n);
    for (auto &t : p)
    {
        Cin(t.x); Cin(t.g); Cin(t.d);
        v.push_back(sd - t.x);
        sd += t.d;
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    m = v.size();
    fill_n(lab + 1, m, LInf);
    sg = sd = 0;
    for (auto &t : p)
    {
        Update(upper_bound(v.begin(), v.end(), sd - t.x) - v.begin(), sg);
        ans = max(ans, (sg += t.g) - Get(upper_bound(v.begin(), v.end(), (sd += t.d) - t.x) - v.begin()));
    }
    cout << ans;
 
    #ifdef GuiltiaSinJurai
    auto end = chrono::steady_clock::now();
    cerr << "In milliseconds : "
         << chrono::duration_cast<chrono::milliseconds>(end - start).count();
    cerr << '\n' << "In seconds : "
         << chrono::duration_cast<chrono::seconds>(end - start).count() << '\n';
    #endif
    return 0;
 
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 672 KB Output is correct
7 Correct 2 ms 676 KB Output is correct
8 Correct 2 ms 676 KB Output is correct
9 Correct 2 ms 676 KB Output is correct
10 Correct 2 ms 676 KB Output is correct
11 Correct 2 ms 676 KB Output is correct
12 Correct 2 ms 676 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 676 KB Output is correct
2 Correct 2 ms 676 KB Output is correct
3 Correct 2 ms 676 KB Output is correct
4 Correct 2 ms 676 KB Output is correct
5 Correct 2 ms 676 KB Output is correct
6 Correct 2 ms 676 KB Output is correct
7 Correct 2 ms 676 KB Output is correct
8 Correct 2 ms 676 KB Output is correct
9 Correct 2 ms 676 KB Output is correct
10 Correct 2 ms 676 KB Output is correct
11 Correct 5 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 768 KB Output is correct
2 Correct 5 ms 1020 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 21 ms 2040 KB Output is correct
5 Correct 24 ms 2040 KB Output is correct
6 Correct 56 ms 3584 KB Output is correct
7 Correct 39 ms 3584 KB Output is correct
8 Correct 41 ms 3584 KB Output is correct
9 Correct 42 ms 3584 KB Output is correct
10 Correct 40 ms 3584 KB Output is correct
11 Correct 43 ms 3584 KB Output is correct
12 Correct 45 ms 3584 KB Output is correct