Submission #1025565


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;
}

int main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  int n,l;
  cin>>n>>l;
  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();

  ll re=1e15;
  ps.eb(l+ps[0].X,0);
  // int l=-112345,r=112345;
  // while(r-l>1){
  //   int m1=(l+l+r)/2;
  //   int m2=(l+r+r)/2;
  // }
  reps(x,-3000,3001){
    vector<pii> vs=ps;
    vs[0].Y+=x;
    vs.back().Y-=x;
    MN(re,solve(vs));
  }
  cout<<re<<endl;
  return 0;
}

Submission Info

Submission Time
Task D - タクシー
User nuip
Language C++11 (GCC 4.8.1)
Score 0
Code Size 2249 Byte
Status WA
Exec Time 21 ms
Memory 928 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 0 / 15 0 / 30 0 / 55
Status
AC × 2
AC × 4
WA × 18
AC × 4
WA × 38
AC × 4
WA × 58
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 19 ms 928 KB
subtask0-sample-02.txt AC 17 ms 796 KB
subtask1-01.txt AC 20 ms 800 KB
subtask1-02.txt AC 21 ms 792 KB
subtask1-03.txt WA 18 ms 800 KB
subtask1-04.txt WA 18 ms 928 KB
subtask1-05.txt WA 19 ms 928 KB
subtask1-06.txt WA 18 ms 792 KB
subtask1-07.txt WA 17 ms 800 KB
subtask1-08.txt WA 18 ms 924 KB
subtask1-09.txt WA 18 ms 924 KB
subtask1-10.txt WA 17 ms 800 KB
subtask1-11.txt WA 19 ms 796 KB
subtask1-12.txt WA 18 ms 928 KB
subtask1-13.txt WA 19 ms 800 KB
subtask1-14.txt WA 18 ms 792 KB
subtask1-15.txt WA 18 ms 796 KB
subtask1-16.txt WA 19 ms 928 KB
subtask1-17.txt WA 18 ms 800 KB
subtask1-18.txt WA 19 ms 800 KB
subtask1-19.txt WA 19 ms 796 KB
subtask1-20.txt WA 19 ms 796 KB
subtask2-01.txt WA 17 ms 800 KB
subtask2-02.txt WA 17 ms 800 KB
subtask2-03.txt WA 19 ms 800 KB
subtask2-04.txt WA 19 ms 924 KB
subtask2-05.txt WA 19 ms 800 KB
subtask2-06.txt WA 18 ms 796 KB
subtask2-07.txt WA 18 ms 796 KB
subtask2-08.txt WA 17 ms 800 KB
subtask2-09.txt WA 18 ms 800 KB
subtask2-10.txt WA 17 ms 796 KB
subtask2-11.txt WA 19 ms 796 KB
subtask2-12.txt WA 19 ms 928 KB
subtask2-13.txt WA 19 ms 928 KB
subtask2-14.txt WA 19 ms 800 KB
subtask2-15.txt WA 18 ms 916 KB
subtask2-16.txt WA 18 ms 800 KB
subtask2-17.txt WA 18 ms 796 KB
subtask2-18.txt WA 19 ms 796 KB
subtask2-19.txt WA 19 ms 928 KB
subtask2-20.txt WA 16 ms 796 KB
subtask3-01.txt WA 19 ms 800 KB
subtask3-02.txt WA 18 ms 920 KB
subtask3-03.txt WA 17 ms 924 KB
subtask3-04.txt WA 20 ms 924 KB
subtask3-05.txt WA 20 ms 916 KB
subtask3-06.txt WA 18 ms 924 KB
subtask3-07.txt WA 19 ms 800 KB
subtask3-08.txt WA 17 ms 796 KB
subtask3-09.txt WA 19 ms 928 KB
subtask3-10.txt WA 19 ms 924 KB
subtask3-11.txt WA 19 ms 796 KB
subtask3-12.txt WA 17 ms 924 KB
subtask3-13.txt WA 19 ms 736 KB
subtask3-14.txt WA 17 ms 920 KB
subtask3-15.txt WA 18 ms 800 KB
subtask3-16.txt WA 17 ms 796 KB
subtask3-17.txt WA 19 ms 928 KB
subtask3-18.txt WA 18 ms 924 KB
subtask3-19.txt WA 18 ms 916 KB
subtask3-20.txt WA 18 ms 916 KB