oj.uz

답안 #43083

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43083 2018-03-09T00:15:58 Z smu201111192 코알라 (JOI13_koala) C++14
100 / 100
 177 ms 50028 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 = 100010;
long long b[MAXN],t[MAXN],A,D,n,s,e;
int L[MAXN * 30],R[MAXN * 30],id = 1;
long long dp[MAXN];
//초기화는 -2e18
long long tree[MAXN * 30];
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 * 30; 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

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 47352 KB Output is correct
2 Correct 36 ms 47352 KB Output is correct
3 Correct 37 ms 47380 KB Output is correct
4 Correct 35 ms 47468 KB Output is correct
5 Correct 37 ms 47468 KB Output is correct
6 Correct 35 ms 47468 KB Output is correct
7 Correct 35 ms 47532 KB Output is correct
8 Correct 37 ms 47532 KB Output is correct
9 Correct 36 ms 47532 KB Output is correct
10 Correct 35 ms 47532 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 49836 KB Output is correct
2 Correct 89 ms 49880 KB Output is correct
3 Correct 53 ms 49880 KB Output is correct
4 Correct 98 ms 49900 KB Output is correct
5 Correct 79 ms 49900 KB Output is correct
6 Correct 50 ms 49900 KB Output is correct
7 Correct 70 ms 50028 KB Output is correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 50028 KB Output is correct
2 Correct 177 ms 50028 KB Output is correct
3 Correct 169 ms 50028 KB Output is correct
4 Correct 152 ms 50028 KB Output is correct
5 Correct 120 ms 50028 KB Output is correct
6 Correct 86 ms 50028 KB Output is correct