Submission #1025578


Source Code Expand

#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> using vv=vector<vector<T>>;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;

ll solve(vector<pii> ps){
  int n=ps.size();
  int sum=0;
  ll re=0;
  rep(i,n-1){
    sum+=ps[i].Y;
    re+=1ll*abs(ps[i].X-ps[i+1].X)*abs(sum);
  }
  //cout<<re<<ps;
  return re;
}
ll fun(vector<pii> ps,int x){
  ps[0].Y+=x;
  ps.back().Y-=x;
  return solve(ps);
}

int main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  int n,len;
  cin>>n>>len;
  //if(n>3000) return 0;
  vector<pii> ps;
  rep(i,n){
    int x,y,z;
    cin>>x>>y>>z;
    if(y!=z) ps.eb(x,y-z);
  }
  //cout<<ps;
  n=ps.size();

  ps.eb(len+ps[0].X,0);
  int l=0,r=212345;
  int d=112300;
  while(r-l>2){
    int m1=(l+l+r)/3;
    int m2=(l+r+r)/3;
    ll v1=fun(ps,m1-d);
    ll v2=fun(ps,m2-d);
    if(v1<v2) r=m2;
    else l=m1;
  }
  ll re=1e15;
  reps(i,l-500,r+500) MN(re,fun(ps,i-d));
  cout<<re<<endl;
  return 0;
}

Submission Info

Submission Time
Task D - タクシー
User nuip
Language C++11 (GCC 4.8.1)
Score 15
Code Size 2359 Byte
Status WA
Exec Time 2028 ms
Memory 3228 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 15 / 15 0 / 30 0 / 55
Status
AC × 2
AC × 22
AC × 29
WA × 13
AC × 31
WA × 17
TLE × 14
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 18 ms 792 KB
subtask0-sample-02.txt AC 17 ms 920 KB
subtask1-01.txt AC 19 ms 800 KB
subtask1-02.txt AC 17 ms 800 KB
subtask1-03.txt AC 32 ms 800 KB
subtask1-04.txt AC 31 ms 928 KB
subtask1-05.txt AC 32 ms 800 KB
subtask1-06.txt AC 20 ms 924 KB
subtask1-07.txt AC 32 ms 928 KB
subtask1-08.txt AC 31 ms 928 KB
subtask1-09.txt AC 31 ms 924 KB
subtask1-10.txt AC 32 ms 924 KB
subtask1-11.txt AC 30 ms 928 KB
subtask1-12.txt AC 32 ms 928 KB
subtask1-13.txt AC 29 ms 924 KB
subtask1-14.txt AC 32 ms 920 KB
subtask1-15.txt AC 33 ms 844 KB
subtask1-16.txt AC 31 ms 924 KB
subtask1-17.txt AC 32 ms 928 KB
subtask1-18.txt AC 31 ms 924 KB
subtask1-19.txt AC 32 ms 928 KB
subtask1-20.txt AC 31 ms 924 KB
subtask2-01.txt AC 38 ms 924 KB
subtask2-02.txt WA 37 ms 1040 KB
subtask2-03.txt AC 21 ms 800 KB
subtask2-04.txt AC 38 ms 924 KB
subtask2-05.txt AC 36 ms 1048 KB
subtask2-06.txt WA 23 ms 796 KB
subtask2-07.txt WA 36 ms 928 KB
subtask2-08.txt WA 38 ms 928 KB
subtask2-09.txt WA 38 ms 920 KB
subtask2-10.txt WA 38 ms 920 KB
subtask2-11.txt WA 38 ms 972 KB
subtask2-12.txt WA 38 ms 928 KB
subtask2-13.txt WA 38 ms 928 KB
subtask2-14.txt AC 37 ms 928 KB
subtask2-15.txt AC 38 ms 876 KB
subtask2-16.txt WA 38 ms 928 KB
subtask2-17.txt WA 38 ms 928 KB
subtask2-18.txt AC 37 ms 928 KB
subtask2-19.txt WA 38 ms 928 KB
subtask2-20.txt WA 38 ms 928 KB
subtask3-01.txt WA 338 ms 1308 KB
subtask3-02.txt WA 972 ms 2072 KB
subtask3-03.txt TLE 2026 ms 3228 KB
subtask3-04.txt WA 635 ms 1596 KB
subtask3-05.txt TLE 2026 ms 3224 KB
subtask3-06.txt TLE 2028 ms 3172 KB
subtask3-07.txt TLE 2026 ms 3228 KB
subtask3-08.txt TLE 2028 ms 3220 KB
subtask3-09.txt AC 1390 ms 2540 KB
subtask3-10.txt TLE 2026 ms 3220 KB
subtask3-11.txt AC 40 ms 928 KB
subtask3-12.txt TLE 2027 ms 3220 KB
subtask3-13.txt TLE 2028 ms 3220 KB
subtask3-14.txt TLE 2028 ms 3224 KB
subtask3-15.txt TLE 2027 ms 3220 KB
subtask3-16.txt TLE 2028 ms 3224 KB
subtask3-17.txt TLE 2026 ms 3220 KB
subtask3-18.txt WA 1763 ms 2968 KB
subtask3-19.txt TLE 2028 ms 3220 KB
subtask3-20.txt TLE 2026 ms 3220 KB