제출 #406900

#제출 시각아이디문제언어결과실행 시간메모리
406900pliam선물상자 (IOI15_boxes)C++14
70 / 100
2096 ms342540 KiB
#include "boxes.h" #include <bits/stdc++.h> using namespace std; #define MAXN 10000005 typedef long long ll; ll pos[2*MAXN]; ll st[8*MAXN],lazy[8*MAXN]; int n,k; ll l; ll ans; void update(int from,int to,ll val,int v=1,int start=0,int end=2*n){ if(start==from&&end==to){ lazy[v]+=val; st[v]+=val; return; } int mid=(start+end)/2; if(lazy[v]){ //propagate update(start,mid,lazy[v],2*v,start,mid); update(mid+1,end,lazy[v],2*v+1,mid+1,end); lazy[v]=0; } if(to<=mid){ update(from,to,val,2*v,start,mid); }else if(from>mid){ update(from,to,val,2*v+1,mid+1,end); }else{ update(from,mid,val,2*v,start,mid); update(mid+1,to,val,2*v+1,mid+1,end); } st[v]=min(st[2*v],st[2*v+1]); } ll query(int from,int to,int v=1,int start=0,int end=2*n){ if(start==from&&end==to){ return st[v]; } int mid=(start+end)/2; if(lazy[v]){ //propagate update(start,mid,lazy[v],2*v,start,mid); update(mid+1,end,lazy[v],2*v+1,mid+1,end); lazy[v]=0; } if(to<=mid){ return query(from,to,2*v,start,mid); }else if(from>mid){ return query(from,to,2*v+1,mid+1,end); }else{ return min(query(from,mid,2*v,start,mid),query(mid+1,to,2*v+1,mid+1,end)); } } ll dist(ll x){ return min(x,l-x); } int modn(int i){ return (i<=n)?i:(i-n); } ll c(int i){ return dist(pos[modn(i)])+pos[i]; } ll d(int i){ return dist(pos[modn(i+1)])-pos[i+1]; } ll q(int s,int i){//dp[i] with start s return c(i)+query(max(s-1,i-k),i-1); } ll dp(int i){ return query(i,i)-d(i); } long long delivery(int N, int K, int L, int positions[]) { n=N; k=K; l=L; if(N==1){ return 2*dist(positions[0]); } for(int i=1;i<=n;i++){ pos[i]=positions[i-1]; } for(int i=n+1;i<=2*n;i++){ pos[i]=pos[i-n]+l; } update(0,0,d(0));//base case->dp[s-1]=dp[0]=0 for(int i=1;i<=2*n-1;i++){ update(i,i,q(1,i)+d(i)); } ans=dp(n); for(int s=2;s<=n;s++){ update(s-1,2*n-1,-dp(s-1));//0-dp[s-1] ans=min(ans,dp(s+n-1)); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...