QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #132425 | #5177. 摩斯电码 2.0 | xuqin | 0 | 0ms | 1760kb | C++14 | 1.4kb | 2023-07-29 21:15:26 | 2023-07-29 21:15:30 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cassert>
#include<set>
#include<random>
#include<chrono>
#include<bitset>
#include<queue>
#include<cstdlib>
#include<cmath>
using namespace std;
const int maxn=1e5+10, inf=1e9, P=1000026113;
const double eps=1e-10;
typedef long long LL;
typedef unsigned long long ULL;
const LL INF=4e18;
typedef pair<LL, int> pli;
typedef pair<int, int> pii;
inline int read() {
int x=0, f=1; char c=getchar();
for(; c<'0'||c>'9'; c=getchar()) if(c=='-') f=0;
for(; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
return f?x:-x;
}
int a[maxn], v[maxn];
int f[60][260];
int main() {
int n=read(), m=read();
for(int i=1; i<=n; ++i) v[i]=read();
int mxa=0;
for(int i=1; i<=n; ++i) a[i]=read(), mxa=max(mxa, a[i]);
int l=0, r=m, b1=v[1]+a[1]+a[n];
while(l<r) {
int mid=(l+r+1)>>1;
for(int i=1; i<=n; ++i)
for(int j=0; j<=mxa; ++j) f[i][j]=inf;
f[1][0]=0;
for(int i=1; i<n-1; ++i)
for(int j=0; j<=mxa; ++j) {
int cur=f[i][j];
if(cur==inf) continue;
for(int k=0; k<=a[i+1]; ++k)
f[i+1][a[i+1]-k]=min(f[i+1][a[i+1]-k], cur+((j+k+v[i+1])*mid+b1-1)/b1-1);
}
int ans=inf;
for(int i=0; i<=mxa; ++i)
ans=min(ans, f[n-1][i]+(i+v[n]+b1-1)*mid/b1-1);
// printf("%d %d\n", mid, ans);
if(ans<=m-mid) l=mid; else r=mid-1;
}
printf("%d\n", l);
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 1516kb
input:
5 5 2 5 5 4 3 2 4 4 5 5
output:
1
result:
wrong answer 1st lines differ - expected: '2', found: '1'
Subtask #2:
score: 0
Wrong Answer
Test #5:
score: 0
Wrong Answer
time: 0ms
memory: 1760kb
input:
5 38 170 62 7 129 93 39 98 2 178 110
output:
11
result:
wrong answer 1st lines differ - expected: '15', found: '11'
Subtask #3:
score: 0
Runtime Error
Test #9:
score: 0
Runtime Error
input:
50 340 145945353 943649879 103681368 412537460 249168929 368424447 732376003 185334999 144319344 511521494 159409847 131972188 193314434 725004712 439570846 364294834 362411427 314220847 829136416 305293003 505373341 638710304 851245152 521859350 644327541 974583375 738591681 147795709 922157319 421...
output:
result:
Subtask #4:
score: 0
Runtime Error
Test #13:
score: 0
Runtime Error
input:
1000 1000 1000000000 732930495 57470406 998674942 980507254 200197125 826994891 726235561 146440304 908089621 108786784 22006340 629816450 656110319 505896602 620885446 857656443 30603288 902307001 946990065 915078227 237356805 675986931 241912445 489230924 199892606 129509547 544771174 171477200 39...
output:
result:
Subtask #5:
score: 0
Runtime Error
Test #17:
score: 0
Runtime Error
input:
10000 1000000000 1000000000 9322 8270 4220 4967 6470 2768 7780 590 1436 4219 7804 8549 8916 9250 1420 5911 2115 7098 9942 4217 7430 5121 4217 395 1363 1098 3314 2058 6689 3270 6734 6663 2769 7773 5406 5705 1208 4409 6282 5593 7665 1334 6208 1138 6856 4597 2152 3666 5645 6841 1182 8469 1768 9165 4521...
output:
result:
Subtask #6:
score: 0
Runtime Error
Test #21:
score: 0
Runtime Error
input:
100000 1000000000 1000000000 34788 73380 66152 92356 82130 69036 96709 88944 26043 93630 93922 79818 18546 43338 40621 46994 77235 61925 24567 63929 22345 8049 40400 68808 79834 10769 68961 415 75455 73445 65121 66981 39924 45321 66260 43977 81382 98200 6894 11936 10781 29304 45584 12022 26163 73225...