Submission #1159942
Source Code Expand
#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cstring> #include <cassert> #define SIZE 100005 #define BT 1024*128*2 #define INF 100000000000000000LL using namespace std; typedef long long int ll; struct segtree { int seg[BT]; int mum; void init(int n) { mum=1; while(mum<n) mum<<=1; for(int i=0;i<mum*2;i++) seg[i]=BT; } void update(int a,int b,int k,int l,int r,int v) { if(b<=l||r<=a) return; if(a<=l&&r<=b) seg[k]=min(seg[k],v); else { update(a,b,k*2+1,l,(l+r)/2,v); update(a,b,k*2+2,(l+r)/2,r,v); } } void update(int a,int b,int v) { update(a,b,0,0,mum,v); } int get(int k) { k+=mum-1; int ret=seg[k]; while(k>0) { k=(k-1)/2; ret=min(ret,seg[k]); } return ret; } }; segtree seg; int A[SIZE],B[SIZE]; ll sum[SIZE]; ll dp[SIZE]; int main() { int n,K; scanf("%d %d",&n,&K); for(int i=0;i<n;i++) { scanf("%d %d",&A[i],&B[i]); if(B[i]==1&&A[i]*2>K) { puts("-1"); return 0; } } for(int i=0;i<n;i++) { sum[i]=A[i]; if(i>0) sum[i]+=sum[i-1]; } vector <ll> vx; vx.push_back(0); for(int i=0;i<n;i++) vx.push_back((sum[i]*2LL)%K); sort(vx.begin(),vx.end()); vx.erase(unique(vx.begin(),vx.end()),vx.end()); seg.init(vx.size()+2); seg.update(0,vx.size(),n); dp[n]=0; for(int i=n-1;i>=0;i--) { if(B[i]==2) continue; ll f=i==0?0:sum[i-1]; int pos=lower_bound(vx.begin(),vx.end(),(f*2LL)%K)-vx.begin(); int to=seg.get(pos); //printf("* %d %d\n",i,to); if(to==n) dp[i]=0; else { ll diff=2LL*(sum[to-1]-f); dp[i]=dp[to]+(K-diff%K)%K; } //if(B[i]==1) { int nxt=lower_bound(vx.begin(),vx.end(),(sum[i]*2LL)%K)-vx.begin(); if(pos<nxt) seg.update(pos,nxt,i); else { if(pos<vx.size()) seg.update(pos,vx.size(),i); if(nxt>0) seg.update(0,nxt,i); } } } ll ret=INF; for(int i=0;i<vx.size();i++) { ll a=vx[i],b=i+1==vx.size()?K-1:vx[i+1]-1; int v=seg.get(i); ll f=v==0?0LL:sum[v-1]; ll da=(a-(f*2LL)%K+(ll) K)%K;//[a,b] ll db=(b-(f*2LL)%K+(ll) K)%K; if(da>db) da=0; ret=min(ret,dp[v]+da+sum[n-1]*2LL); } printf("%lld\n",ret); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Train Service Planning |
User | yutaka1999 |
Language | C++14 (GCC 5.4.1) |
Score | 1700 |
Code Size | 2245 Byte |
Status | AC |
Exec Time | 95 ms |
Memory | 4468 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:59:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d %d",&n,&K); ^ ./Main.cpp:62:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d %d",&A[i],&B[i]); ^
Judge Result
Set Name | Sample | All | subtask | subtask2 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 700 | 500 / 500 | 500 / 500 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample1.txt, sample2.txt, sample3.txt, sample4.txt |
All | sample1.txt, sample2.txt, sample3.txt, sample4.txt, in1.txt, in10.txt, in101.txt, in102.txt, in103.txt, in104.txt, in105.txt, in106.txt, in107.txt, in108.txt, in109.txt, in11.txt, in110.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt, sample4.txt, sub2in1.txt, sub2in10.txt, sub2in11.txt, sub2in12.txt, sub2in13.txt, sub2in14.txt, sub2in15.txt, sub2in16.txt, sub2in17.txt, sub2in18.txt, sub2in19.txt, sub2in2.txt, sub2in20.txt, sub2in21.txt, sub2in22.txt, sub2in23.txt, sub2in24.txt, sub2in3.txt, sub2in4.txt, sub2in5.txt, sub2in6.txt, sub2in7.txt, sub2in8.txt, sub2in9.txt, subin1.txt, subin10.txt, subin101.txt, subin102.txt, subin103.txt, subin104.txt, subin105.txt, subin106.txt, subin107.txt, subin108.txt, subin109.txt, subin11.txt, subin12.txt, subin13.txt, subin14.txt, subin15.txt, subin16.txt, subin17.txt, subin18.txt, subin19.txt, subin2.txt, subin20.txt, subin201.txt, subin21.txt, subin22.txt, subin23.txt, subin24.txt, subin3.txt, subin4.txt, subin5.txt, subin6.txt, subin7.txt, subin8.txt, subin9.txt |
subtask | sample1.txt, sample2.txt, sample3.txt, subin1.txt, subin10.txt, subin101.txt, subin102.txt, subin103.txt, subin104.txt, subin105.txt, subin106.txt, subin107.txt, subin108.txt, subin109.txt, subin11.txt, subin12.txt, subin13.txt, subin14.txt, subin15.txt, subin16.txt, subin17.txt, subin18.txt, subin19.txt, subin2.txt, subin20.txt, subin201.txt, subin21.txt, subin22.txt, subin23.txt, subin24.txt, subin3.txt, subin4.txt, subin5.txt, subin6.txt, subin7.txt, subin8.txt, subin9.txt |
subtask2 | sample1.txt, sample2.txt, sample3.txt, sample4.txt, sub2in1.txt, sub2in10.txt, sub2in11.txt, sub2in12.txt, sub2in13.txt, sub2in14.txt, sub2in15.txt, sub2in16.txt, sub2in17.txt, sub2in18.txt, sub2in19.txt, sub2in2.txt, sub2in20.txt, sub2in21.txt, sub2in22.txt, sub2in23.txt, sub2in24.txt, sub2in3.txt, sub2in4.txt, sub2in5.txt, sub2in6.txt, sub2in7.txt, sub2in8.txt, sub2in9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
in1.txt | AC | 2 ms | 256 KB |
in10.txt | AC | 64 ms | 4468 KB |
in101.txt | AC | 44 ms | 3956 KB |
in102.txt | AC | 43 ms | 3956 KB |
in103.txt | AC | 45 ms | 3700 KB |
in104.txt | AC | 42 ms | 4468 KB |
in105.txt | AC | 40 ms | 4468 KB |
in106.txt | AC | 44 ms | 3956 KB |
in107.txt | AC | 42 ms | 3956 KB |
in108.txt | AC | 45 ms | 3700 KB |
in109.txt | AC | 42 ms | 4468 KB |
in11.txt | AC | 67 ms | 4468 KB |
in110.txt | AC | 40 ms | 4468 KB |
in12.txt | AC | 62 ms | 4468 KB |
in13.txt | AC | 60 ms | 4468 KB |
in14.txt | AC | 63 ms | 4468 KB |
in15.txt | AC | 59 ms | 4468 KB |
in16.txt | AC | 61 ms | 4468 KB |
in17.txt | AC | 62 ms | 4468 KB |
in18.txt | AC | 62 ms | 4468 KB |
in19.txt | AC | 61 ms | 4468 KB |
in2.txt | AC | 66 ms | 4468 KB |
in20.txt | AC | 61 ms | 4468 KB |
in21.txt | AC | 53 ms | 4468 KB |
in22.txt | AC | 51 ms | 4468 KB |
in23.txt | AC | 53 ms | 4468 KB |
in24.txt | AC | 56 ms | 4468 KB |
in25.txt | AC | 28 ms | 3444 KB |
in26.txt | AC | 28 ms | 3444 KB |
in27.txt | AC | 27 ms | 3444 KB |
in28.txt | AC | 28 ms | 3444 KB |
in3.txt | AC | 64 ms | 4468 KB |
in4.txt | AC | 66 ms | 4468 KB |
in5.txt | AC | 56 ms | 4084 KB |
in6.txt | AC | 61 ms | 4468 KB |
in7.txt | AC | 59 ms | 3956 KB |
in8.txt | AC | 11 ms | 640 KB |
in9.txt | AC | 66 ms | 4468 KB |
sample1.txt | AC | 1 ms | 256 KB |
sample2.txt | AC | 1 ms | 256 KB |
sample3.txt | AC | 1 ms | 256 KB |
sample4.txt | AC | 1 ms | 256 KB |
sub2in1.txt | AC | 1 ms | 256 KB |
sub2in10.txt | AC | 1 ms | 256 KB |
sub2in11.txt | AC | 1 ms | 256 KB |
sub2in12.txt | AC | 1 ms | 256 KB |
sub2in13.txt | AC | 1 ms | 256 KB |
sub2in14.txt | AC | 1 ms | 256 KB |
sub2in15.txt | AC | 1 ms | 256 KB |
sub2in16.txt | AC | 1 ms | 256 KB |
sub2in17.txt | AC | 1 ms | 256 KB |
sub2in18.txt | AC | 1 ms | 256 KB |
sub2in19.txt | AC | 1 ms | 256 KB |
sub2in2.txt | AC | 1 ms | 256 KB |
sub2in20.txt | AC | 1 ms | 256 KB |
sub2in21.txt | AC | 1 ms | 256 KB |
sub2in22.txt | AC | 1 ms | 256 KB |
sub2in23.txt | AC | 1 ms | 256 KB |
sub2in24.txt | AC | 1 ms | 256 KB |
sub2in3.txt | AC | 1 ms | 256 KB |
sub2in4.txt | AC | 1 ms | 256 KB |
sub2in5.txt | AC | 1 ms | 256 KB |
sub2in6.txt | AC | 1 ms | 256 KB |
sub2in7.txt | AC | 1 ms | 256 KB |
sub2in8.txt | AC | 1 ms | 256 KB |
sub2in9.txt | AC | 1 ms | 256 KB |
subin1.txt | AC | 94 ms | 4468 KB |
subin10.txt | AC | 89 ms | 4468 KB |
subin101.txt | AC | 76 ms | 4468 KB |
subin102.txt | AC | 59 ms | 4468 KB |
subin103.txt | AC | 54 ms | 4468 KB |
subin104.txt | AC | 54 ms | 4468 KB |
subin105.txt | AC | 52 ms | 4468 KB |
subin106.txt | AC | 49 ms | 4468 KB |
subin107.txt | AC | 61 ms | 4468 KB |
subin108.txt | AC | 65 ms | 4468 KB |
subin109.txt | AC | 59 ms | 4468 KB |
subin11.txt | AC | 82 ms | 4468 KB |
subin12.txt | AC | 85 ms | 4468 KB |
subin13.txt | AC | 86 ms | 4468 KB |
subin14.txt | AC | 88 ms | 4468 KB |
subin15.txt | AC | 86 ms | 4468 KB |
subin16.txt | AC | 87 ms | 4468 KB |
subin17.txt | AC | 79 ms | 4468 KB |
subin18.txt | AC | 82 ms | 4468 KB |
subin19.txt | AC | 84 ms | 4468 KB |
subin2.txt | AC | 91 ms | 4468 KB |
subin20.txt | AC | 85 ms | 4468 KB |
subin201.txt | AC | 1 ms | 256 KB |
subin21.txt | AC | 30 ms | 3444 KB |
subin22.txt | AC | 30 ms | 3444 KB |
subin23.txt | AC | 31 ms | 3444 KB |
subin24.txt | AC | 31 ms | 3444 KB |
subin3.txt | AC | 95 ms | 4468 KB |
subin4.txt | AC | 80 ms | 4084 KB |
subin5.txt | AC | 84 ms | 4468 KB |
subin6.txt | AC | 61 ms | 4468 KB |
subin7.txt | AC | 17 ms | 1024 KB |
subin8.txt | AC | 12 ms | 768 KB |
subin9.txt | AC | 95 ms | 4468 KB |