oj.uz

Submission #766131

# Submission time Handle Problem Language Result Execution time Memory
766131 2023-06-25T10:31:44 Z bachhoangxuan 코알라 (JOI13_koala) C++17
100 / 100
 44 ms 7060 KB 
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
#define int long long
const int inf=6e18;
int dp[maxn],x[maxn],b[maxn],k,m,d,a,n;
int bit[2][maxn],len;
int query(int id,int p){
    int Max=-inf;
    for(int i=p;i>=1;i-=(i&(-i))) Max=max(Max,bit[id][i]);
    return Max;
}
void update(int id,int p,int val){
    for(int i=p;i<=len;i+=(i&(-i))) bit[id][i]=max(bit[id][i],val);
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> k >> m >> d >> a >> n;
    vector<int> p;p.push_back(k%d);p.push_back(m%d);
    for(int i=1;i<=n;i++){
        cin >> x[i] >> b[i];
        p.push_back({x[i]%d});
    }
    sort(p.begin(),p.end());
    p.erase(unique(p.begin(),p.end()),p.end());
    x[0]=k;x[n+1]=m;len=(int)p.size()+1;
    for(int i=0;i<=len;i++) bit[1][i]=bit[0][i]=-inf;
    int km=lower_bound(p.begin(),p.end(),k%d)-p.begin()+1;
    update(0,km,0+(k/d)*a);update(1,len-km,0+(k/d)*a);
    for(int i=1;i<=n+1;i++){
        int q=lower_bound(p.begin(),p.end(),x[i]%d)-p.begin()+1;
        int t1=query(0,q-1),t2=query(1,len-q);
        dp[i]=max(t1-a*(x[i]/d+1),t2-a*(x[i]/d))+b[i];
        update(0,q,dp[i]+(x[i]/d)*a);update(1,len-q,dp[i]+(x[i]/d)*a);
    }
    cout << dp[n+1] << '\n';
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5448 KB Output is correct
2 Correct 24 ms 5220 KB Output is correct
3 Correct 12 ms 3748 KB Output is correct
4 Correct 29 ms 5396 KB Output is correct
5 Correct 15 ms 3476 KB Output is correct
6 Correct 9 ms 2216 KB Output is correct
7 Correct 14 ms 4564 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 6464 KB Output is correct
2 Correct 41 ms 6932 KB Output is correct
3 Correct 38 ms 7008 KB Output is correct
4 Correct 33 ms 7060 KB Output is correct
5 Correct 25 ms 4380 KB Output is correct
6 Correct 18 ms 3408 KB Output is correct