oj.uz

Submission #43081

# Submission time Handle Problem Language Result Execution time Memory
43081 2018-03-09T00:10:54 Z smu201111192 코알라 (JOI13_koala) C++14
100 / 100
 177 ms 83780 KB 
#include <iostream>
#include <cstdio>
#include <cassert>
#include <bitset>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 200000;
long long b[MAXN],t[MAXN],A,D,n,s,e;
int L[MAXN * 20],R[MAXN * 20],id = 1;
long long dp[MAXN];
//초기화는 -2e18
long long tree[MAXN * 20];
void update(int node,int st,int ed,int pos,long long val){
    if(st == ed){
        tree[node] = max(val,tree[node]); return;
    }
    int mid = (st+ed)/2;
    if(pos <= mid){
        if(L[node] == -1) L[node] = ++id;
        update(L[node],st,mid,pos,val);
        tree[node] = max(tree[node],tree[L[node]]);
    }
    else{
        if(R[node] == -1) R[node] = ++id;
        update(R[node],mid+1,ed,pos,val);
        tree[node] = max(tree[node],tree[R[node]]);
    }
}
long long query(int node,int st,int ed,int l,int r){
    if(l > r) return -4e18;
    if(st > r || ed < l) return -4e18;
    if(st >= l && ed <= r) return tree[node];
    int mid = (st+ed)/2;
    auto Lv = (L[node] == -1 ? -2e18 : query(L[node],st,mid,l,r));
    auto Rv = (R[node] == -1 ? -2e18 : query(R[node],mid+1,ed,l,r));
    return max(Lv,Rv);
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> s >> e;
    cin >> D >> A >> n;
    t[0] = s; t[n + 1] = e;
    for(int i = 1; i <= n; i++){
        cin >> t[i] >> b[i];
        dp[i] = -2e18;
    }
    n++; dp[n] = -2e18;
    memset(L,-1,sizeof(L));
    memset(R,-1,sizeof(R));
    for(int i = 0; i < MAXN * 20; i++) tree[i] = -2e18;
    for(int i = n; i >= 0; i--) t[i] -= t[0];
    update(1,0,D-1,0,0);
    dp[0] = 0;
    for(int i = 1; i <= n; i++){
        long long x = t[i] % D;
        long long cand1 = query(1,0,D-1,0,x-1) - (t[i]/D + 1) * A + b[i];
        long long cand2 = query(1,0,D-1,x,D-1) - (t[i]/D)     * A + b[i];
        dp[i] = max({dp[i],cand1,cand2});
        update(1,0,D-1,x,dp[i]+(t[i]/D)*A);
    }
    cout<<dp[n];
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 62968 KB Output is correct
2 Correct 49 ms 63092 KB Output is correct
3 Correct 48 ms 63232 KB Output is correct
4 Correct 45 ms 63244 KB Output is correct
5 Correct 46 ms 63396 KB Output is correct
6 Correct 47 ms 63396 KB Output is correct
7 Correct 44 ms 63396 KB Output is correct
8 Correct 46 ms 63396 KB Output is correct
9 Correct 45 ms 63504 KB Output is correct
10 Correct 46 ms 63504 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 67836 KB Output is correct
2 Correct 93 ms 69404 KB Output is correct
3 Correct 73 ms 69844 KB Output is correct
4 Correct 92 ms 72492 KB Output is correct
5 Correct 69 ms 72708 KB Output is correct
6 Correct 62 ms 72780 KB Output is correct
7 Correct 78 ms 75312 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 77176 KB Output is correct
2 Correct 176 ms 79252 KB Output is correct
3 Correct 177 ms 81128 KB Output is correct
4 Correct 155 ms 82948 KB Output is correct
5 Correct 123 ms 83324 KB Output is correct
6 Correct 106 ms 83780 KB Output is correct