Submission #1306340
Source Code Expand
#include <bits/stdc++.h> using namespace std; using ll=long long; #define int ll #define FOR(i,a,b) for(int i=int(a);i<int(b);i++) #define REP(i,b) FOR(i,0,b) #define MP make_pair #define PB push_back #define ALL(x) x.begin(),x.end() #define REACH cerr<<"reached line "<<__LINE__<<endl #define DBG(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl using pi=pair<int,int>; using vi=vector<int>; using ld=long double; template<class T,class U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os<<"("<<p.first<<","<<p.second<<")"; return os; } template<class T> ostream& operator <<(ostream& os,const vector<T>& v){ os<<"["; REP(i,(int)v.size()){ if(i)os<<","; os<<v[i]; } os<<"]"; return os; } int read(){ int i; scanf("%lld",&i); return i; } void printSpace(){ printf(" "); } void printEoln(){ printf("\n"); } void print(int x,int suc=1){ printf("%lld",x); if(suc==1) printEoln(); if(suc==2) printSpace(); } string readString(){ static char buf[3341919]; scanf("%s",buf); return string(buf); } char* readCharArray(){ static char buf[3341919]; static int bufUsed=0; char* ret=buf+bufUsed; scanf("%s",ret); bufUsed+=strlen(ret)+1; return ret; } template<class T,class U> void chmax(T& a,U b){ if(a<b) a=b; } template<class T,class U> void chmin(T& a,U b){ if(a>b) a=b; } template<class T> T Sq(const T& t){ return t*t; } const int inf=LLONG_MAX/3; struct Node{ int x; mutable int v,d; bool operator<(const Node&rhs)const{ return x<rhs.x; } }; signed main(){ int n=read(),k=read(),ans=0,bias=0; set<Node> s{Node{0,0,0}}; REP(i,n){ int a=read(),b=read(); ans+=a*2; if(b==1&&a*2>k){ cout<<-1<<endl; return 0; } bias=(bias+a*2)%k; int t=(k-bias)%k; auto itr=s.lower_bound(Node{t}); if(itr==s.end()||itr->x!=t){ if(itr==s.begin()) itr=s.end(); itr--; itr=s.insert(Node{t,itr->v+(t+k-itr->x)%k*itr->d,itr->d}).first; } if(b==1){ itr->d=1; itr++; while(1){ if(itr==s.end())itr=s.begin(); int w=(itr->x+bias)%k; if(0<w&&w<a*2)itr=s.erase(itr); else break; } } } int m=inf; for(auto z:s)chmin(m,z.v); cout<<ans+m<<endl; }
Submission Info
Submission Time | |
---|---|
Task | F - Train Service Planning |
User | maroonrk |
Language | C++14 (GCC 5.4.1) |
Score | 1700 |
Code Size | 2286 Byte |
Status | AC |
Exec Time | 70 ms |
Memory | 6400 KB |
Compile Error
./Main.cpp: In function ‘ll read()’: ./Main.cpp:38:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%lld",&i); ^ ./Main.cpp: In function ‘std::string readString()’: ./Main.cpp:60:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%s",buf); ^ ./Main.cpp: In function ‘char* readCharArray()’: ./Main.cpp:68:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%s",ret); ^
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 | 3 ms | 256 KB |
in10.txt | AC | 36 ms | 256 KB |
in101.txt | AC | 38 ms | 896 KB |
in102.txt | AC | 43 ms | 1280 KB |
in103.txt | AC | 36 ms | 512 KB |
in104.txt | AC | 52 ms | 2816 KB |
in105.txt | AC | 51 ms | 3072 KB |
in106.txt | AC | 39 ms | 896 KB |
in107.txt | AC | 43 ms | 1280 KB |
in108.txt | AC | 35 ms | 512 KB |
in109.txt | AC | 53 ms | 2816 KB |
in11.txt | AC | 37 ms | 256 KB |
in110.txt | AC | 52 ms | 3072 KB |
in12.txt | AC | 40 ms | 256 KB |
in13.txt | AC | 38 ms | 256 KB |
in14.txt | AC | 40 ms | 256 KB |
in15.txt | AC | 45 ms | 256 KB |
in16.txt | AC | 45 ms | 256 KB |
in17.txt | AC | 42 ms | 256 KB |
in18.txt | AC | 41 ms | 256 KB |
in19.txt | AC | 42 ms | 256 KB |
in2.txt | AC | 37 ms | 256 KB |
in20.txt | AC | 39 ms | 256 KB |
in21.txt | AC | 64 ms | 5120 KB |
in22.txt | AC | 63 ms | 6400 KB |
in23.txt | AC | 64 ms | 4224 KB |
in24.txt | AC | 64 ms | 3456 KB |
in25.txt | AC | 30 ms | 256 KB |
in26.txt | AC | 29 ms | 256 KB |
in27.txt | AC | 28 ms | 256 KB |
in28.txt | AC | 31 ms | 256 KB |
in3.txt | AC | 36 ms | 256 KB |
in4.txt | AC | 37 ms | 256 KB |
in5.txt | AC | 32 ms | 256 KB |
in6.txt | AC | 43 ms | 256 KB |
in7.txt | AC | 36 ms | 256 KB |
in8.txt | AC | 22 ms | 256 KB |
in9.txt | AC | 37 ms | 256 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 | 35 ms | 256 KB |
subin10.txt | AC | 38 ms | 256 KB |
subin101.txt | AC | 32 ms | 256 KB |
subin102.txt | AC | 46 ms | 2304 KB |
subin103.txt | AC | 58 ms | 4224 KB |
subin104.txt | AC | 52 ms | 4224 KB |
subin105.txt | AC | 70 ms | 6400 KB |
subin106.txt | AC | 61 ms | 6400 KB |
subin107.txt | AC | 44 ms | 3328 KB |
subin108.txt | AC | 46 ms | 3328 KB |
subin109.txt | AC | 46 ms | 2560 KB |
subin11.txt | AC | 43 ms | 256 KB |
subin12.txt | AC | 42 ms | 256 KB |
subin13.txt | AC | 40 ms | 256 KB |
subin14.txt | AC | 39 ms | 256 KB |
subin15.txt | AC | 38 ms | 256 KB |
subin16.txt | AC | 37 ms | 256 KB |
subin17.txt | AC | 41 ms | 256 KB |
subin18.txt | AC | 41 ms | 256 KB |
subin19.txt | AC | 38 ms | 256 KB |
subin2.txt | AC | 34 ms | 256 KB |
subin20.txt | AC | 37 ms | 256 KB |
subin201.txt | AC | 1 ms | 256 KB |
subin21.txt | AC | 29 ms | 256 KB |
subin22.txt | AC | 30 ms | 256 KB |
subin23.txt | AC | 29 ms | 256 KB |
subin24.txt | AC | 29 ms | 256 KB |
subin3.txt | AC | 36 ms | 256 KB |
subin4.txt | AC | 31 ms | 256 KB |
subin5.txt | AC | 41 ms | 256 KB |
subin6.txt | AC | 46 ms | 896 KB |
subin7.txt | AC | 34 ms | 256 KB |
subin8.txt | AC | 24 ms | 256 KB |
subin9.txt | AC | 36 ms | 384 KB |