제출 #1337457

#제출 시각아이디문제언어결과실행 시간메모리
1337457KhoaDuy코알라 (JOI13_koala)C++20
0 / 100
66 ms4896 KiB
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const ll Tid=-1e18;
ll TT(ll le,ll ri){
    return max(le,ri);
}
struct segtree{
    vector<ll> seg;
    vector<int> coor;
    int n,lg;
    void refresh(int v){
        seg[v]=TT(seg[v<<1],seg[(v<<1)|1]);
    }
    void build(vector<int> &a){
        coor=a;
        sort(coor.begin(),coor.end());
        coor.erase(unique(coor.begin(),coor.end()),coor.end());
        n=1;
        while(n<coor.size()){
            n<<=1;
        }
        lg=__lg(n);
        seg.assign(n<<1,Tid);
    }
    int getidx(int x){
        return (lower_bound(coor.begin(),coor.end(),x)-coor.begin());
    }
    void update(int l,ll x){
        l=getidx(l);
        l+=n;
        seg[l]=max(seg[l],x);
        for(int i=1;i<=lg;i++){
            refresh(l>>i);
        }
    }
    ll query(int l,int r){
        l=getidx(l),r=getidx(r);
        if(l>=r){
            return Tid;
        }
        l+=n,r+=n;
        ll curr=Tid;
        for(;l<r;l>>=1,r>>=1){
            if(l&1){
                curr=TT(curr,seg[l]);
                l++;
            }
            if(r&1){
                r--;
                curr=TT(curr,seg[r]);
            }
        }
        return curr;
    }
};
signed main(){
    if(fopen("input.txt","r")){
        freopen("input.txt","r",stdin);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int k,m,d,a,n;
    cin >> k >> m >> d >> a >> n;
    a=-a;
    vector<int> x;
    x.push_back(k);
    vector<int> coor;
    coor.push_back(k%d);
    int b[n+1];
    for(int i=1;i<=n;i++){
        int t;
        cin >> t >> b[i];
        coor.push_back(t%d);
        x.push_back(t);
    }
    coor.push_back(m%d);
    for(int i=0;i<coor.size();i++){
        if(coor[i]==0){
            coor[i]+=d;
        }
    }
    x.push_back(m);
    b[0]=0,b[n+1]=0;
    ll DP[n+2];
    DP[0]=0;
    segtree seg;
    seg.build(coor);
    seg.update(d,0-(1LL*a*((x[0]+d-1)/d)));
    for(int i=1;i<=n+1;i++){
        //cout << "PHASE " << i << endl;
        int temp=x[i]%d;
        if(temp==0){
            temp+=d;
        }
        DP[i]=Tid;
        DP[i]=max(DP[i],seg.query(1,temp)+1LL*a*((x[i]+d-1)/d)+a);
        DP[i]=max(DP[i],seg.query(temp,d+1)+1LL*a*((x[i]+d-1)/d));
        //cout << i << ' ' << DP[i] << endl;
        DP[i]+=b[i];
        seg.update(temp,DP[i]-1LL*a*((x[i]+d-1)/d));
        //cout << "ANS " << DP[i] << endl;
    }
    cout << DP[n+1];
}

컴파일 시 표준 에러 (stderr) 메시지

koala.cpp: In function 'int main()':
koala.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen("input.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...