QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#521995 | #5044. Happiness | E_huan | WA | 1ms | 3992kb | C++14 | 2.6kb | 2024-08-16 17:11:46 | 2024-08-16 17:11:47 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=310;
int n,ans,MN=1e9,MX,mn[15]; // MN,MX 是最早最晚过题 , mn[i] 是最早通过 i 的时间
string s;
int x[N][15],y[N][15]; // x 是通过时间(n 是通过需要的时间) y 是罚时增加的时间
struct node {
int x,y;
int a[12];
inline bool operator<(const node &t) const {
if(x!=t.x) return x>t.x;
if(y!=t.y) return y<t.y;
for(int i=x;i>=1;i--) if(a[i]!=t.a[i]) return a[i]<t.a[i];
return 0;
}
}o[N]; // o[i] 是 {i通过的题数,i 的总罚时}
int val(int l,int r) {
int res=0;
while(l<=r) res=res*10+(s[l]-'0'),l++;
return res;
}
void work(int pid,int l,int r,int tid) {
if(l==r) {x[pid][tid]=y[pid][tid]=-1; return;} //'-'
int p=l+1; while(s[p]!=' ') p++;
x[pid][tid]=val(l,p-1),y[pid][tid]=val(p+1,r)*20;
}
bool vis[15];
int p[N]; // 潘的做题顺序
inline void answer(int c,int t2,int val) {
o[n]={c,t2};
if(c&&(x[n][p[1]]<=MN)) val+=700;
int t=0;
for(int i=1;i<=c;i++) t+=x[n][p[i]],o[n].a[i]=t;
if(c&&(t>=MX)) val+=500;
int r=lower_bound(o+1,o+(n-1)+1,o[n])-o;
if(r<=(n/10)) val+=1200;
else if(r<=(3*(n/10))) val+=800;
else if(r<=(6*(n/10))) val+=400;
ans=max(ans,val+(5000/r));
}
void dfs(int c,int t,int t2,int val) { // c 表示已经通过的题目数量,t 表示当前时间,t2 是总罚时,val 表示快乐值(只考虑 MN MX mn)
if(c>=n) {answer(c,t2,val); return;}
bool f=0;
for(int i=1;i<=10;i++) if((!vis[i])&&(t+x[n][i]<=300)) { // 接着做 i
vis[i]=1; p[c+1]=i; f=1;
dfs(c+1,t+x[n][i],t2+(t+x[n][i])+y[n][i],val+800*((t+x[n][i])<=mn[p[c]]));
vis[i]=0;
}
if(!f) answer(c,t2,val);
}
int main() {
// freopen("in.in","r",stdin);
scanf("%d",&n); getchar();
for(int i=1;i<=n;i++) {
getline(cin,s);
int l=0,r=0,len=s.length(),c=0;
while(r<len) {
while((s[r]!=',')&&r<len) r++;
work(i,l,r-1,++c);
l=r+1; r=l;
}
for(int j=1;j<=10;j++)
if(x[i][j]>=0) {
o[i].y+=x[i][j]+y[i][j];
o[i].a[++o[i].x]=x[i][j];
}
sort(o[i].a+1,o[i].a+o[i].x+1);
}
memset(mn,0x3f,sizeof mn);
for(int i=1;i<=10;i++) {
if(x[n][i]==-1) vis[i]=1;
for(int p=1;p<n;p++) if(x[p][i]>=0) {
MX=max(MX,x[p][i]); MN=min(MN,x[p][i]);
mn[i]=min(mn[i],x[p][i]);
}
}
sort(o+1,o+(n-1)+1);
dfs(0,0,0,0);
printf("%d\n",ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3920kb
input:
10 233 1,-,-,7 7,257 4,173 5,117 1,-,-,85 3 -,231 0,167 0,257 7,-,-,122 4,283 0,215 4,- 41 1,-,290 8,-,-,-,-,246 7,120 3,184 9 142 8,243 7,69 0,-,41 9,-,279 1,264 4,-,74 9 53 8,-,187 9,60 1,48 8,99 10,-,-,55 7,259 5 250 0,-,-,-,166 0,16 3,-,82 4,73 0,184 3 -,-,-,-,105 3,-,-,-,152 4,- -,84 5,98 8,-,1...
output:
1800
result:
ok 1 number(s): "1800"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
10 15 0,19 10,152 4,45 10,154 7,172 3,168 4,263 1,187 7,24 4 2 3,93 5,113 7,160 0,274 4,128 8,119 0,46 6,50 5,129 2 117 8,190 1,202 1,69 1,64 5,218 0,148 2,156 7,86 2,162 5 209 1,145 0,214 2,99 10,9 1,47 5,235 5,87 3,250 10,285 5 245 0,150 1,237 8,182 7,4 3,38 5,238 6,164 2,259 3,59 6 31 8,44 9,27 6...
output:
1300
result:
ok 1 number(s): "1300"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
300 -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,...
output:
6200
result:
ok 1 number(s): "6200"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
300 164 7,180 10,59 4,162 10,16 3,140 1,204 10,73 9,289 5,14 8 97 3,18 1,153 4,160 6,166 10,25 8,300 9,183 8,98 10,195 10 195 5,247 10,116 1,129 7,79 5,238 7,198 3,192 2,282 7,117 2 125 1,269 10,188 9,72 8,65 5,249 5,46 1,192 3,77 0,241 3 18 1,147 0,12 6,34 9,120 3,282 4,44 1,206 2,50 10,125 10 174 ...
output:
16
result:
ok 1 number(s): "16"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3992kb
input:
300 -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,-,- -,-,-,-,-,-,-,-,...
output:
9800
result:
ok 1 number(s): "9800"
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3988kb
input:
300 171 8,75 1,-,190 7,44 5,-,10 9,72 1,63 2,- 295 0,-,60 10,-,64 7,-,-,-,-,- 247 8,67 10,-,-,93 1,-,69 4,90 1,-,- 278 1,206 7,-,-,22 4,97 1,-,156 1,227 0,276 4 245 6,111 5,-,-,281 10,44 7,266 4,-,130 5,- 244 7,-,-,-,183 9,118 7,-,-,123 8,158 2 63 5,-,-,117 3,286 7,-,-,-,278 1,151 5 291 1,223 6,-,-,...
output:
820
result:
wrong answer 1st numbers differ - expected: '20', found: '820'