oj.uz

Submission #361273

# Submission time Handle Problem Language Result Execution time Memory
361273 2021-01-29T04:57:19 Z Killer2501 코알라 (JOI13_koala) C++14
100 / 100
 133 ms 9976 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define task "talltree"
#define pll pair<ll, ll>
#define pii pair<ll, pll>
#define fi first
#define se second
#define ull unsigned long long
using namespace std;
const ll mod = 1e15+7;
const ll N = 2e5+5;
vector<ll> adj[N];
vector<ll> kq;
vector<pll> pre;
ll n, m, t, k, b[N], p, a[N], ans, tong, d[N], st[N*4], K, D, M, A;
void build(ll id, ll l, ll r)
{
    st[id] = -mod;
    if(l == r)
    {
        return;
    }
    ll mid = (l + r) / 2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
}
ll get(ll id, ll l, ll r, ll u, ll v)
{
    if(u <= l && r <= v)return st[id];
    if(u > r || l > v || u > v)return -mod;
    ll mid = (l + r) / 2;
    return max(get(id*2, l, mid, u, v), get(id*2+1, mid+1, r, u, v));
}
void update(ll id, ll l, ll r, ll u, ll v)
{
    if(l == r)
    {
        st[id] = max(st[id], v);
        return;
    }
    ll mid = (l + r) / 2;
    if(mid >= u)update(id*2, l, mid, u, v);
    else update(id*2+1, mid+1, r, u, v);
    st[id] = max(st[id*2], st[id*2+1]);
}
ll findp(ll u)
{
    return lower_bound(kq.begin(), kq.end(), u) - kq.begin() + 1;
}
void sol()
{
    cin >> K >> M >> D >> A >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i] >> b[i];
        kq.pb(a[i]%D);
    }
    kq.pb(K%D);
    kq.pb(M%D);
    sort(kq.begin(), kq.end());
    kq.erase(unique(kq.begin(), kq.end()), kq.end());
    build(1, 1, n+2);
    k = (K / D) * A;
    update(1, 1, n+2, findp(K%D), k);
    for(int i = 1; i <= n; i ++)
    {
        //cin >> a[i] >> b[i];
        k = findp(a[i] % D);
        m = max(get(1, 1, n+2, 1, k-1)-A, get(1, 1, n+2, k, n+2));
        m += -(a[i] / D) * A + b[i];
        //cout << m<<'\n';
        update(1, 1, n+2, k, m + (a[i] / D) * A );
    }
    k = findp(M % D);
    t = -(M / D) * A;
    cout << t + max(get(1, 1, n+2, 1, k-1)-A, get(1, 1, n+2, k, n+2));
}
int main()
{
    if(fopen(task".inp", "r")){
       freopen(task".inp", "r", stdin);
       freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}

Compilation message

koala.cpp: In function 'int main()':
koala.cpp:82:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   82 |        freopen(task".inp", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
koala.cpp:83:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   83 |        freopen(task".out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 9832 KB Output is correct
2 Correct 83 ms 9832 KB Output is correct
3 Correct 33 ms 8044 KB Output is correct
4 Correct 89 ms 9832 KB Output is correct
5 Correct 49 ms 7916 KB Output is correct
6 Correct 31 ms 7276 KB Output is correct
7 Correct 71 ms 9852 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 9976 KB Output is correct
2 Correct 126 ms 9960 KB Output is correct
3 Correct 133 ms 9832 KB Output is correct
4 Correct 101 ms 9832 KB Output is correct
5 Correct 71 ms 8044 KB Output is correct
6 Correct 55 ms 7532 KB Output is correct