제출 #406849

#제출 시각아이디문제언어결과실행 시간메모리
406849pliam선물상자 (IOI15_boxes)C++14
10 / 100
3 ms332 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-1){ 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-1){ 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,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=0;i<n;i++){ pos[i]=positions[i]; } for(int i=n;i<2*n;i++){ pos[i]=positions[i-n]+l; } update(0,0,2*dist(pos[0])+d(0));//base case for(int i=1;i<n;i++){ update(i,i,q(0,i)+d(i)); } ans=dp(n-1); for(int s=1;s<n;s++){ update(s,s+n-2,2*dist(pos[s])-dp(s)); update(s+n-1,s+n-1,q(s,s+n-1)+d(s+n-1));//make dp[s+n-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...