QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#149619 | #5480. New Year Festival | lgvc | RE | 39ms | 379928kb | C++23 | 3.4kb | 2023-08-24 23:00:37 | 2023-08-24 23:00:38 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define pai 3.141592653589793238462643383279502884197169399375105820
#define eps 0.00000001
#define ULL unsigned long long
#define LL long long
#define INF 0x3f3f3f3f
#define INF_LL 0x3f3f3f3f3f3f3f3f
static char buf[1000000],*paa=buf,*pd=buf;
static char buf2[1000000],*pp=buf2;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline void pc(char ch){
if(pp-buf2==1000000) fwrite(buf2,1,1000000,stdout),pp=buf2;
*pp++=ch;
}
inline void pcc(){
fwrite(buf2,1,pp-buf2,stdout);
pp=buf2;
}
inline int read(void){
int w=1;
register int x(0);register char c(getchar());
while(c<'0'||c>'9'){if(c=='-') w=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
return w*x;
}
void write(int x){
static int sta[20];
int top=0;
do{
sta[top++]=x%10,x/=10;
}while(x);
while(top) pc(sta[--top]+48);
}
void we(int x){
write(x);
pc('\n');
}
struct n_t{
int x,y;
};
inline bool cmp(n_t m,n_t n) {
return m.x<n.x;
}
int N,s[15],l[15],f[15],p[15],q[15],x[15][70],y[15][70],vi[16000009],as=INF_LL;
std::vector<n_t> dp,dq,stt[16000009];
inline int qr(int x) {
if(x>dq[dq.size()-1].x) return dq[dq.size()-1].y;
if(dq.size()==1) return dq[0].y;
int l=0,r=dq.size()-2,md;
while(l<r) {
md=(l+r+1)>>1;
if(x>=dq[md].x) l=md;else r=md-1;
}
return dq[l].y+(dq[l+1].y-dq[l].y)/(dq[l+1].x-dq[l].x)*(x-dq[l].x);
}
std::vector<n_t> ff(int xx) {
dp.clear();
dq.clear();
dp.push_back((n_t){0,0});
dp.push_back((n_t){100000000,0});
int vq=0;
for(int i=1;i<=xx;i++) {
vq=vq*N+f[i];
if(i<=7&&vi[vq]) {
dp=stt[vq];
if(dp.empty()) return dp;
continue;
}
dq=dp;
for(int j=1;j<=s[f[i]];j++) {
if(x[f[i]][j]>=dq[0].x) dp.push_back((n_t){x[f[i]][j],qr(x[f[i]][j])});
}
dq.clear();
std::sort(dp.begin(),dp.end(),cmp);
for(int j=0;j<dp.size();j++) if(dp[j].x<=x[f[i]][s[f[i]]]&&dp[j].x>=x[f[i]][1]) dq.push_back(dp[j]);
int st=1;
for(int j=0;j<dq.size();j++) {
while(st+1<s[f[i]]&&dq[j].x>=x[f[i]][st+1]) st++;
if(s[f[i]]==1) dq[j].y+=y[f[i]][1];
else dq[j].y+=y[f[i]][st]+(y[f[i]][st+1]-y[f[i]][st])/(x[f[i]][st+1]-x[f[i]][st])*(dq[j].x-x[f[i]][st]);
dq[j].x+=l[f[i]];
}
if(dq.empty()) {
if(i<=6) vi[vq]=1;
return dq;
}
dp.clear();
dp.push_back(dq[0]);
for(int j=1;j<dq.size();j++) {
if(dq[j].x!=dq[j-1].x) dp.push_back(dq[j]);
}
for(int j=1;j<dp.size();j++) {
dp[j].y=std::min(dp[j].y,dp[j-1].y);
}
if(i<=7) {
vi[vq]=1;
stt[vq]=dp;
}
}
return dp;
}
inline void tryy(int x) {
int k=0,ct=1;
for(int i=1;i<=N;i++) if((x>>i-1)&1) p[++k]=i,q[k]=k-1;
for(int i=1;i<=k;i++) ct=ct*i;
while(ct--) {
for(int i=1;i<=k;i++) f[i]=p[q[i]+1];
dq=ff(k);
if(!dq.empty()) as=std::min(as,dq[dq.size()-1].y);
std::next_permutation(q+1,q+k+1);
}
}
signed main(void) {
//freopen("m.in","r",stdin);
//freopen("m.out","w",stdout);
N=read();
for(int i=1;i<=N;i++) {
s[i]=read();l[i]=read();
for(int j=1;j<=s[i];j++) {
x[i][j]=read();
y[i][j]=read();
}
}
srand(time(NULL));
tryy((1<<N)-1);
printf("%lld\n",as);
/* int s=N/2;
for(int i=0;i<(1<<N);i++) {
if(__builtin_popcount(i)!=s) continue;
tryy(i);
}
if(N%2==1) {
for(int i=0;i<(1<<N);i++) {
if(__builtin_popcount(i)!=s+1) continue;
tryy(i);
}
}*/
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 39ms
memory: 379928kb
input:
3 3 50 300 2500 350 0 400 3000 2 120 380 0 400 2400 4 160 0 800 400 0 450 100 950 4600
output:
1460
result:
ok single line: '1460'
Test #2:
score: 0
Accepted
time: 32ms
memory: 379904kb
input:
4 2 160 384 0 1000 2464 3 280 0 2646 441 0 1000 2795 1 160 544 0 2 240 720 0 1220 2000
output:
2022
result:
ok single line: '2022'
Test #3:
score: -100
Runtime Error
input:
11 6 192168 0 8547618 626988 33627138 706274 36560720 1103426 50858192 1399013 55291997 1418093 55559117 6 161415 0 58611901 321482 57647455 349707 57534555 550744 55524185 885629 50500910 1448846 27972230 6 195811 0 6825079 56106 8339941 78686 8836701 323216 12993711 525834 15627745 1414450 2095944...