QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#380618 | #8572. Passing Game | ucup-team1134# | TL | 604ms | 12800kb | C++23 | 4.5kb | 2024-04-07 06:50:13 | 2024-04-07 06:50:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005;
const ll INF=1LL<<61;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//dynamic CHT MIN
/**
* Author: Simon Lindholm
* Date: 2017-04-20
* License: CC0
* Source: own work
* Description: Container where you can add lines of the form kx+m, and query maximum values at points x.
* Useful for dynamic programming (``convex hull trick'').
* Time: O(\log N)
* Status: stress-tested
*/
#pragma once
struct Line {
mutable ll k, m, p;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct LineContainerMIN : multiset<Line, less<>> {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
static const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
if (y == end()) return x->p = inf, 0;
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m) {
k*=-1;m*=-1;
auto z = insert({k, m, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
ll query(ll x) {
assert(!empty());
auto l = *lower_bound(x);
return -(l.k * x + l.m);
}
};
ll dp[MAX];
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
int Q;cin>>Q;
while(Q--){
ll N,K;cin>>N>>K;
chmin(K,62LL);
vector<array<ll,3>> S(N);
for(int i=0;i<N;i++) cin>>S[i][0];
for(int i=0;i<N;i++) cin>>S[i][1];
for(int i=0;i<N;i++) S[i][2]=i;
sort(all(S));
vector<array<ll,3>> T;
int stt=-1,goo=-1;
for(int i=0;i<N;i++){
if(S[i][2]==0){
stt=i;
}
if(S[i][2]==N-1){
goo=i;
}
}
T.push_back(S[stt]);
{
ll la=S[stt][1];
for(int i=stt-1;i>=0;i--){
if(chmin(la,S[i][1])) T.push_back(S[i]);
else if(i==goo) T.push_back(S[i]);
}
}
{
ll la=S[stt][1];
for(int i=stt+1;i<si(S);i++){
if(chmin(la,S[i][1])) T.push_back(S[i]);
else if(i==goo) T.push_back(S[i]);
}
}
int bi=N-1;
sort(all(T));
S=T;
//for(auto [a,b,c]:S) cout<<a<<" "<<b<<" "<<c<<endl;
N=si(S);
stt=-1;goo=-1;
for(int i=0;i<N;i++){
if(S[i][2]==0){
stt=i;
}
if(S[i][2]==bi){
goo=i;
}
}
//cout<<stt<<" "<<goo<<endl;
for(int i=0;i<MAX;i++){
dp[i]=INF;
}
dp[stt]=0;
for(int t=0;t<=K;t++){
bool upd=false;
vector<ll> neL(N,INF),neR(N,INF);
{
LineContainerMIN cht;
for(int i=0;i<N;i++){
neR[i]=dp[i];
auto [x,v,iii]=S[i];
if(i>=stt&&si(cht)) chmin(neR[i],cht.query(x));
if(neR[i]!=INF&&neR[i]<dp[goo]) cht.add(v,v*(-x)+neR[i]);
}
}
{
LineContainerMIN cht;
for(int i=N-1;i>=0;i--){
neL[i]=dp[i];
auto [x,v,iii]=S[i];
if(i<=stt&&si(cht)) chmin(neL[i],cht.query(-x));
if(neL[i]!=INF&&neL[i]<dp[goo]) cht.add(v,v*x+neL[i]);
}
}
for(int i=0;i<N;i++){
if(min(neL[i],neR[i])<dp[goo]&&chmin(dp[i],min(neL[i],neR[i]))) upd=true;
}
if(!upd) break;
}
cout<<dp[goo]<<"\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 6140kb
input:
2 4 2 3 2 1 6 3 1 1 3 2 0 1 2 1 2
output:
7 1
result:
ok 2 number(s): "7 1"
Test #2:
score: 0
Accepted
time: 63ms
memory: 12392kb
input:
1 300000 204334 809492393 304618667 173130445 377106790 364888630 949045125 622060683 557772818 216607577 848817467 862855568 507840723 120816645 639713488 741781998 682531787 685261161 601686403 355792373 162819930 710057718 234560726 998604853 678957602 485413982 855985802 109303681 979706626 4822...
output:
31313390701066
result:
ok 1 number(s): "31313390701066"
Test #3:
score: 0
Accepted
time: 55ms
memory: 8240kb
input:
3 100000 65460 217141764 710454586 789075415 24849107 685675008 839804815 638763480 327755609 43827967 390187172 301370841 622696676 598237196 232099091 211987715 416876077 572665966 73382836 520033984 808399404 752832432 341795744 434460344 535426588 136624537 997406768 297342165 558882675 26863877...
output:
70635841128944 47230361360721 59110547802683
result:
ok 3 number(s): "70635841128944 47230361360721 59110547802683"
Test #4:
score: 0
Accepted
time: 58ms
memory: 12800kb
input:
1 300000 101975 207258305 525434317 528778163 645316642 562113679 143398489 9114413 669854123 106324041 841914487 21419012 308025536 689200225 263298218 39377353 860366080 24610184 43404209 529054797 902238799 422737070 484129934 967667618 953541323 338625285 115085955 363490839 998893783 877857789 ...
output:
40311829457542
result:
ok 1 number(s): "40311829457542"
Test #5:
score: 0
Accepted
time: 3ms
memory: 5976kb
input:
18 17 0 500000000 499999997 500000010 499999965 500000118 499999609 500001291 499995739 500014064 499953589 500153157 499494579 501667889 494495965 518163316 440061055 697798520 197798520 59938945 18163316 5504035 1667889 505421 153157 46411 14064 4261 1291 391 118 35 10 3 1 17 1 500000000 499999997...
output:
15506866876 14901483521 14901483521 14596599454 14596599454 14327495899 14327495899 14069829018 14069829018 13814295534 13814295534 13559037370 13559037370 13303815695 13303815695 13061698660 13061698660 13061698660
result:
ok 18 numbers
Test #6:
score: 0
Accepted
time: 62ms
memory: 12428kb
input:
1 300000 108311 562733523 631963246 813519221 169288073 117366252 527887631 958029417 190367625 583075950 97173270 896048212 131308006 37400006 90012864 923307076 279518077 383193505 134227338 223315078 230865002 126513901 226753074 767298214 632275980 328061909 158106292 275417458 205909246 6796599...
output:
22530954433990
result:
ok 1 number(s): "22530954433990"
Test #7:
score: 0
Accepted
time: 604ms
memory: 5900kb
input:
6000 50 9 134170081 235040736 405102476 567954026 351391400 872095141 116079799 935104039 779623552 857355273 642352783 394389351 10847154 403727586 104520573 266338849 213345479 719882827 836874283 973992590 698097800 821674140 408510849 363267881 10753022 371526254 123631785 246871721 505280626 29...
output:
30096348366675791 46069208396039888 43208901362730729 70517421587512986 11224815513692355 71475323642044669 1805862419831112 135052117577413332 26429620406592108 30539122715657614 7984965510320702 45549957862209120 42689412604990122 11269234889588471 80025912449049377 62081070915081025 4881768842034...
result:
ok 6000 numbers
Test #8:
score: 0
Accepted
time: 60ms
memory: 8320kb
input:
3 100000 29147 500000000 597145750 552984982 372885743 640231243 733918327 800174654 803027973 174812114 914218248 958491647 953654602 654712814 719285245 331288273 879947652 879757804 768921697 826703535 228697076 180453233 681236422 977876007 50434656 229471634 830980737 12014073 250160020 4486414...
output:
13061698660 13061698660 13061698660
result:
ok 3 number(s): "13061698660 13061698660 13061698660"
Test #9:
score: -100
Time Limit Exceeded
input:
30000 10 10 802030518 640274071 71550121 799843967 796619138 223219513 312183499 673542337 879397647 631413076 598196518 983359971 96204862 446173607 402690754 668171337 905549873 566661387 434495917 150918417 10 10 224422012 525305826 404334728 998133227 59632864 62611196 296576565 812713672 614679...
output:
69273774453668369 15440670445128286 192723941525693508 75675642974614068 36131012282542320 85171320762046356 27782956555892610 12331410768391077 241652836554719225 121097012285620735 382589380847694270 12204787868953675 98646491955517787 1209132821823955 27110849050473250 137126106329510200 13480620...