NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #196446 | #2653. 划分 | wosile | 100 | 4728ms | 20716kb | C++11 | 882b | 2023-10-26 10:22:25 | 2023-10-26 12:37:11 |
answer
#include<bits/stdc++.h>
using namespace std;
int n,q;
typedef long long ll;
int a[1000005],r[1000005],dis[1000005];
ll pre[1000005];
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
while(q--){
ll s;
scanf("%lld",&s);
for(int i=1;i<=n;i++){
r[i]=r[i-1];
while(r[i]<=n && pre[r[i]]-pre[i-1]<=s)r[i]++;
// printf("%d %d\n",r[i],pre[r[i]]-pre[i-1]);
dis[i]=1;
}
r[n+1]=n+1;
for(int i=n;i>=1;i--)if(r[i]<=n){
if(r[r[i]]<=n){
dis[i]=dis[r[i]]+1;
r[i]=r[r[i]];
}
// printf("%d %d %d\n",i,dis[i],r[i]);
}
int L=1,ans=0x3f3f3f3f;
for(int i=1;i<=n;i++){
while(L<=n && pre[n]-pre[L-1]+pre[i]>s)L++;
if(pre[i]>s)break;
if(r[i+1]>=L)ans=min(ans,dis[i+1]+1);
else ans=min(ans,dis[i+1]+2);
}
printf("%d\n",ans);
}
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 717ms
memory: 20716kb
input:
1000000 50 657029265 329943981 565712113 1013377922 149930697 886906548 554358409 1317719377 2058201...
output:
222611 286 285145 3 3 5 9 666772 112788 3 67 70655 227877 3 80106 79252 53242 3 66232 6 136245 14349...
result:
ok 50 lines
Test #2:
score: 10
Accepted
time: 689ms
memory: 20712kb
input:
1000000 50 656978844 1630001881 2140212835 206030595 1012571201 1623756379 251275777 1239134037 1976...
output:
182327 9 251764 3 89132 667818 103511 188226 4 81521 205827 119956 47273 36172 54428 5 33721 4 40834...
result:
ok 50 lines
Test #3:
score: 10
Accepted
time: 701ms
memory: 20716kb
input:
1000000 50 656928423 782576134 1567229910 1546166915 1875211705 213122563 2095676792 1160548697 1895...
output:
8 75108 5 409278 117335 119238 666478 94032 666478 115405 107298 4 208383 3 158654 101243 122980 115...
result:
ok 50 lines
Test #4:
score: 10
Accepted
time: 700ms
memory: 20716kb
input:
1000000 50 656878002 2082634034 994246985 738819588 590368562 949972394 1792594160 1081963357 181410...
output:
3 9 7 4 59 21 3 3 11 6 172653 3 666775 5 107165 79015 582315 4 3 156186 666775 289647 547795 121675 ...
result:
ok 50 lines
Test #5:
score: 10
Accepted
time: 130ms
memory: 20716kb
input:
1000000 1 748123205 189953250 1383573308 763657840 1435042408 368911799 515316904 129657177 15997557...
output:
9
result:
ok single line: '9'
Test #6:
score: 10
Accepted
time: 129ms
memory: 20712kb
input:
1000000 1 748156819 754903748 333906160 586061509 1575776621 1309334343 717371992 897875286 22234433...
output:
4
result:
ok single line: '4'
Test #7:
score: 10
Accepted
time: 130ms
memory: 20716kb
input:
1000000 1 748173626 1037378997 1956556233 1571005167 572401904 1779545615 818399536 208242517 168112...
output:
3
result:
ok single line: '3'
Test #8:
score: 10
Accepted
time: 120ms
memory: 20716kb
input:
1000000 1 748190433 1319854246 1431722659 408465178 1716510834 102273240 919427080 1666093395 992416...
output:
3
result:
ok single line: '3'
Test #9:
score: 10
Accepted
time: 708ms
memory: 20716kb
input:
1000000 50 656777160 387782540 1995764782 1271608581 168165923 276188409 1186428896 924792677 165136...
output:
225100 54699 39503 72843 5 119247 5 145035 306458 4 16 70341 3 63267 131771 6 162196 666374 666374 8...
result:
ok 50 lines
Test #10:
score: 10
Accepted
time: 704ms
memory: 20716kb
input:
1000000 50 656827581 1235208287 421264060 2078955908 1453009066 1686822225 1489511528 1003378017 173...
output:
32394 152110 3 196873 15 65320 3 170189 3 36288 302374 50575 8 126177 5 7 40946 3 3 666517 93886 473...
result:
ok 50 lines
