oj.uz

Submission #86753

# Submission time Handle Problem Language Result Execution time Memory
86753 2018-11-27T09:20:07 Z vanbang9710 Divide and conquer (IZhO14_divide) C++14
100 / 100
 52 ms 3464 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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 624 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 624 KB Output is correct
6 Correct 2 ms 624 KB Output is correct
7 Correct 2 ms 664 KB Output is correct
8 Correct 2 ms 664 KB Output is correct
9 Correct 2 ms 664 KB Output is correct
10 Correct 2 ms 664 KB Output is correct
11 Correct 2 ms 664 KB Output is correct
12 Correct 2 ms 664 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 664 KB Output is correct
2 Correct 2 ms 664 KB Output is correct
3 Correct 3 ms 676 KB Output is correct
4 Correct 3 ms 676 KB Output is correct
5 Correct 3 ms 676 KB Output is correct
6 Correct 3 ms 676 KB Output is correct
7 Correct 3 ms 676 KB Output is correct
8 Correct 2 ms 676 KB Output is correct
9 Correct 3 ms 676 KB Output is correct
10 Correct 3 ms 676 KB Output is correct
11 Correct 4 ms 708 KB Output is correct
12 Correct 4 ms 708 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 720 KB Output is correct
2 Correct 7 ms 1104 KB Output is correct
3 Correct 6 ms 1104 KB Output is correct
4 Correct 23 ms 2136 KB Output is correct
5 Correct 25 ms 2136 KB Output is correct
6 Correct 52 ms 3428 KB Output is correct
7 Correct 41 ms 3428 KB Output is correct
8 Correct 44 ms 3464 KB Output is correct
9 Correct 40 ms 3464 KB Output is correct
10 Correct 41 ms 3464 KB Output is correct
11 Correct 44 ms 3464 KB Output is correct
12 Correct 45 ms 3464 KB Output is correct