Submission #43081

#	Time	Username	Problem	Language	Result	Execution time	Memory
43081		smu201111192	코알라 (JOI13_koala)	C++14	100 / 100	177 ms	83780 KiB

koala

#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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50