Submission #1225558

#TimeUsernameProblemLanguageResultExecution timeMemory
1225558_rain_Long Distance Coach (JOI17_coach)C++20
100 / 100
102 ms16816 KiB
#include<bits/stdc++.h> using namespace std; typedef long long LL; #define i64 long long const int N=(int)2e5; const LL INF=(LL)1e18; LL s[N+2]; pair<LL,int>d[N+2]; int n,m; LL w,x,t; namespace subtask1{ bool check(){ return n<=1000 && m<=1000; } LL pre[N+2]={}; int need[N+2]={}; LL dp[N+2]={}; void main_code(){ sort(d+1,d+m+1,[&](pair<LL,int> x,pair<LL,int> y){ return x.first % t < y.first % t; }); s[++n]=x; sort(s+1,s+n+1); for(int i=1;i<=m;++i) pre[i]=pre[i-1]+d[i].second; for(int i=1;i<=n;++i) { int pos=upper_bound(d+1,d+m+1,pair<LL,int>(s[i]%t,-1))-d-1; if (need[pos]==0) need[pos]=i; } dp[0]=(LL)(x/t)*w+w; for(int i=1;i<=m;++i){ dp[i]=dp[i-1]+(LL)(x/t+(x%t>=d[i].first))*w; if (need[i]){ for(int j=0;j<i;++j){ LL t1=(s[need[i]]/t); LL addmore=pre[i]+w*i*t1+dp[j]-pre[j]-t1*j*w; dp[i]=min(dp[i],addmore); } } } cout<<dp[m]<<'\n'; } } namespace Convex_hull{ struct Line { i64 a ; i64 b; Line(i64 a , i64 b) : a(a) , b(b) {}; }; struct Hull { Line X ; long double intersec; }; class Convexhull { public: vector<Hull> line; double getintersec(Line x , Line y) { return (long double)(y.b - x.b) / (x.a - y.a); } i64 f(Line a , i64 x) { return a.a * x + a.b; } void addline(Line x) { int n = line.size(); while (n > 1 && getintersec(x , line[n - 2].X) <= line[n - 1].intersec) { --n; line.pop_back(); } if (line.empty()) line.push_back({x , LLONG_MIN}); else line.push_back({x , getintersec(x , line[n - 1].X)}); return; } i64 find(i64 val) { int l = 0 , r = line.size()-1 , pos = 0; while (l<=r) { int m = l + r >> 1; if (line[m].intersec <= val) pos = m , l = m + 1; else r = m - 1; } return f(line[pos].X , val); } void add(i64 a , i64 b) { addline(Line{a,b}); return; } void reset() { line.clear(); } }; } namespace subtask2{ bool check(){ return n<=2e5; } using namespace Convex_hull; Convexhull baoloi; LL pre[N+2]={}; LL dp[N+2]={}; int need[N+2]={}; void main_code(){ sort(d+1,d+m+1); s[++n]=x; sort(s+1,s+n+1); for(int i=1;i<=m;++i) pre[i]=pre[i-1]+d[i].second; for(int i=1;i<=n;++i) { int pos=upper_bound(d+1,d+m+1,pair<LL,int>(s[i]%t,-1))-d-1; if (need[pos]==0) need[pos]=i; } dp[0]=(LL)(x/t)*w+w; baoloi.add(0,dp[0]-pre[0]); for(int i=1;i<=m;++i){ dp[i]=dp[i-1]+w*((x/t)+(x%t>=d[i].first)); if (need[i]){ LL t1=w*(s[need[i]]/t); LL addmore=pre[i]+t1*i+baoloi.find(t1); dp[i]=min(dp[i],addmore); } baoloi.add(-i,dp[i]-pre[i]); } cout<<dp[m]; } } int main(){ ios::sync_with_stdio(false); cin.tie(0) ; cout.tie(0); #define task "main" if (fopen(task".inp","r")){ freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } cin>>x>>n>>m>>w>>t; for(int i=1;i<=n;++i) cin>>s[i]; for(int i=1;i<=m;++i) cin>>d[i].first>>d[i].second; if (subtask2::check()){ return subtask2::main_code(),0; } return 0; }

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:150:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |                 freopen(task".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
coach.cpp:151:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |                 freopen(task".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...