QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#39087 | #1269. New Equipments | wyhao | TL | 3ms | 3180kb | C++ | 2.7kb | 2022-07-08 13:11:41 | 2022-07-08 13:11:41 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
const int N=55,N1=3005,M=20005;
typedef long long ll;
int TT,n,m,S,T,cnt,num;
ll a[N],b[N],c[N],cst[M];
int to[M],nxt[M],f[M],h[N1];
void add(int i,int x,int y,int z,ll w){
// printf("%d %d %d %lld\n",x,y,z,w);
to[i]=y;f[i]=z;nxt[i]=h[x];cst[i]=w;h[x]=i;
}
map<int,int>Map;
ll F(int i,int j){
return a[i]*j*j+b[i]*j+c[i];
}
struct node{
int val;ll key;
bool operator<(const node a)const{
return key>a.key;
}
}d[N1],p;
int tot;
bool cmp(node x,node y){
return x.key<y.key;
}
void get1(int i,int &l,int &r){
if(2*a[i]>=-b[i]){
l=1;r=n;
return;
}
if(2*a[i]*m<=-b[i]){
r=m;l=m-n+1;
return;
}
tot=1;int t=-b[i]/(a[i]*2);
// printf("%d\n",t);
d[1].val=t;d[1].key=F(i,t);
for(int i=1;i<=n;i++){
if(t-i>=1){
tot++;
d[tot].val=t-i;
d[tot].key=F(i,t-i);
}
if(t+i<=m){
tot++;
d[tot].val=t+i;
d[tot].key=F(i,t+i);
}
}
sort(d+1,d+tot+1,cmp);
l=m;r=1;
for(int i=1;i<=n;i++){
if(d[i].val<l) l=d[i].val;
if(d[i].val>r) r=d[i].val;
}
}
priority_queue<node>Q;
ll dis[N1];
int pre[N1];
bool vis[N1];
bool I=false;
ll dfs(){
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
while(!Q.empty()) Q.pop();
dis[S]=0;pre[S]=-1;
p.val=S;p.key=0;Q.push(p);
int s=0;
while(!Q.empty()){
int x=Q.top().val;Q.pop();
if(vis[x]) continue;
s++;
if(I) printf("%d\n",x);
if(I and s==50) return 0x3f3f3f3f3f3f3f3f;
vis[x]=true;
if(x==T) return dis[T];
for(int i=h[x],y;i;i=nxt[i]){
y=to[i];
if(vis[y]) continue;
if(f[i] and dis[y]>dis[x]+cst[i]){
dis[y]=dis[x]+cst[i];
p.val=y;p.key=dis[y];
Q.push(p);
pre[y]=i;
}
}
}
return 0x3f3f3f3f3f3f3f3f;
}
void path(){
for(int t=pre[T];~t;t=pre[to[t^1]]){
f[t]--;f[t^1]++;
}
}
int main(){
// freopen("ex1.in","r",stdin);
scanf("%d",&TT);
while(TT--){
scanf("%d%d",&n,&m);num=n;
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
}
Map.clear();cnt=1;
for(int i=1,l,r,k;i<=n;i++){
get1(i,l,r);
// printf("%d %d\n",l,r);
for(int j=l;j<=r;j++){
if(!Map[j]) Map[j]=++num;
k=Map[j];ll w=F(i,j);
add(++cnt,i,k,1,w);
add(++cnt,k,i,0,-w);
}
}
S=num+1;T=S+1;
for(int i=1;i<=n;i++){
add(++cnt,S,i,1,0);
add(++cnt,i,S,0,0);
}
for(int i=n+1;i<=num;i++){
add(++cnt,i,T,1,0);
add(++cnt,T,i,0,0);
}
ll ans=0;
for(int i=1;i<=n;i++){
if(i==50) I=true;
ll k=dfs();
if(k!=0x3f3f3f3f3f3f3f3f){
ans+=k;path();
printf("%lld ",ans);
}else{
for(;i<=n;i++) printf("%lld ",ans);
break;
}
}
puts("");
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 3180kb
input:
1 3 5 2 3 10 2 -3 10 1 -1 4
output:
4 15 37
result:
ok single line: '4 15 37 '
Test #2:
score: -100
Time Limit Exceeded
input:
10 50 50 2 -16 79 8 -21 54 8 -1 3 1 -7 47 5 -20 89 1 -2 47 2 -10 26 10 31 28 2 -16 37 6 -16 44 2 -8 100 3 -26 65 3 -6 91 10 -33 56 2 -7 22 2 -12 74 1 -3 7 7 -30 51 1 -4 8 1 -10 62 2 -5 5 1 -3 38 7 -32 57 4 -24 65 1 -8 97 7 -28 71 5 -13 71 2 -14 49 6 -33 100 2 7 69 8 -22 38 5 -23 88 7 20 57 7 -11 83 ...