Submission #2072001
Source Code Expand
#include<deque> #include<queue> #include<vector> #include<algorithm> #include<iostream> #include<set> #include<cmath> #include<tuple> #include<string> #include<chrono> #include<functional> #include<iterator> #include<random> #include<unordered_set> #include<unordered_map> #include<array> #include<map> #include<bitset> #include<iomanip> #include<list> #include <numeric> using namespace std; typedef unsigned long long int ulint; typedef long long int llint; typedef long double lldo; #define mp make_pair #define mt make_tuple #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define fir first #define sec second #define res resize #define ins insert #define era erase #define RE return 0 //ios::sync_with_stdio(false); //std::cin.tie(0); //<< setprecision(20) const int mod=(int)1e9+7; const llint big=(llint)44e15; const long double pai=3.141592653589793238462643383279502884197; const long double ena=2.71828182845904523536; const long double eps=1e-7; template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;} template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;} template <class T> void soun(T& ar) {sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());} llint gcd(llint a,llint b){if(a%b==0){return b;}else{return gcd(b,a%b);}} llint lcm(llint a,llint b){return a/gcd(a,b) *b;} template<class T,class U> auto LB(T& ve,U in){return lower_bound(ve.begin(),ve.end(),in);} template<class T,class U> auto UB(T& ve,U in){return upper_bound(ve.begin(),ve.end(),in);} template<class T,class U> auto LBI(T& ve,U in){return LB(ve,in)-ve.begin();} template<class T,class U> auto UBI(T& ve,U in){return UB(ve,in)-ve.begin();} template<class T> void SO(T& ve){sort(ve.begin(),ve.end());} template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());} int main(void){ llint i,n,L;cin>>n>>L; llint ans=0,gen=0,mae=0; vector<pair<llint,llint>> hen;//人数,距離 for(i=0;i<n;i++){ llint dis,b,c;cin>>dis>>b>>c; hen.pub(mp(gen,dis-mae));gen+=b-c;mae=dis; } hen[0].sec=L-mae; SO(hen); //人数が少ないほうからソート //全体に人数を1足したり引いたりできる //Σabs(人数)*距離 最小化 //距離のsum値がL/2になるように人数を合わせる llint sud=0,hos=0; for(i=0;i<n;i++){ sud+=hen[i].sec; if(sud*2>=L){hos=hen[i].fir;break;} } //cerr<<"hos="<<hos<<endl; for(auto it:hen){ans+=abs(it.fir-hos)*it.sec;} cout<<ans<<endl; RE; }
Submission Info
Submission Time | |
---|---|
Task | D - タクシー |
User | WA_TLE |
Language | C++14 (Clang 3.8.0) |
Score | 100 |
Code Size | 2586 Byte |
Status | AC |
Exec Time | 254 ms |
Memory | 2420 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 15 / 15 | 30 / 30 | 55 / 55 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0-sample-01.txt, subtask0-sample-02.txt |
Subtask1 | subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt |
Subtask2 | subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt |
Subtask3 | subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt, subtask3-11.txt, subtask3-12.txt, subtask3-13.txt, subtask3-14.txt, subtask3-15.txt, subtask3-16.txt, subtask3-17.txt, subtask3-18.txt, subtask3-19.txt, subtask3-20.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0-sample-01.txt | AC | 1 ms | 256 KB |
subtask0-sample-02.txt | AC | 1 ms | 256 KB |
subtask1-01.txt | AC | 1 ms | 256 KB |
subtask1-02.txt | AC | 1 ms | 256 KB |
subtask1-03.txt | AC | 11 ms | 512 KB |
subtask1-04.txt | AC | 10 ms | 512 KB |
subtask1-05.txt | AC | 10 ms | 512 KB |
subtask1-06.txt | AC | 10 ms | 512 KB |
subtask1-07.txt | AC | 10 ms | 512 KB |
subtask1-08.txt | AC | 10 ms | 512 KB |
subtask1-09.txt | AC | 11 ms | 512 KB |
subtask1-10.txt | AC | 11 ms | 512 KB |
subtask1-11.txt | AC | 10 ms | 512 KB |
subtask1-12.txt | AC | 10 ms | 512 KB |
subtask1-13.txt | AC | 9 ms | 512 KB |
subtask1-14.txt | AC | 11 ms | 512 KB |
subtask1-15.txt | AC | 10 ms | 512 KB |
subtask1-16.txt | AC | 11 ms | 512 KB |
subtask1-17.txt | AC | 11 ms | 512 KB |
subtask1-18.txt | AC | 10 ms | 512 KB |
subtask1-19.txt | AC | 11 ms | 512 KB |
subtask1-20.txt | AC | 10 ms | 512 KB |
subtask2-01.txt | AC | 14 ms | 512 KB |
subtask2-02.txt | AC | 14 ms | 512 KB |
subtask2-03.txt | AC | 11 ms | 512 KB |
subtask2-04.txt | AC | 13 ms | 512 KB |
subtask2-05.txt | AC | 11 ms | 512 KB |
subtask2-06.txt | AC | 11 ms | 512 KB |
subtask2-07.txt | AC | 14 ms | 512 KB |
subtask2-08.txt | AC | 14 ms | 512 KB |
subtask2-09.txt | AC | 14 ms | 512 KB |
subtask2-10.txt | AC | 13 ms | 512 KB |
subtask2-11.txt | AC | 14 ms | 512 KB |
subtask2-12.txt | AC | 14 ms | 512 KB |
subtask2-13.txt | AC | 13 ms | 512 KB |
subtask2-14.txt | AC | 12 ms | 512 KB |
subtask2-15.txt | AC | 14 ms | 512 KB |
subtask2-16.txt | AC | 14 ms | 512 KB |
subtask2-17.txt | AC | 14 ms | 512 KB |
subtask2-18.txt | AC | 11 ms | 512 KB |
subtask2-19.txt | AC | 14 ms | 512 KB |
subtask2-20.txt | AC | 14 ms | 512 KB |
subtask3-01.txt | AC | 52 ms | 892 KB |
subtask3-02.txt | AC | 127 ms | 1400 KB |
subtask3-03.txt | AC | 253 ms | 2420 KB |
subtask3-04.txt | AC | 202 ms | 2420 KB |
subtask3-05.txt | AC | 253 ms | 2420 KB |
subtask3-06.txt | AC | 252 ms | 2420 KB |
subtask3-07.txt | AC | 252 ms | 2420 KB |
subtask3-08.txt | AC | 252 ms | 2420 KB |
subtask3-09.txt | AC | 193 ms | 2420 KB |
subtask3-10.txt | AC | 254 ms | 2420 KB |
subtask3-11.txt | AC | 181 ms | 2420 KB |
subtask3-12.txt | AC | 253 ms | 2420 KB |
subtask3-13.txt | AC | 248 ms | 2420 KB |
subtask3-14.txt | AC | 252 ms | 2420 KB |
subtask3-15.txt | AC | 253 ms | 2420 KB |
subtask3-16.txt | AC | 253 ms | 2420 KB |
subtask3-17.txt | AC | 253 ms | 2420 KB |
subtask3-18.txt | AC | 230 ms | 2420 KB |
subtask3-19.txt | AC | 247 ms | 2420 KB |
subtask3-20.txt | AC | 253 ms | 2420 KB |