QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #674126 | #7532. Inspection (32 MB ML!) | ucup-team3161# | ML | 1ms | 10104kb | C++17 | 2.7kb | 2024-10-25 14:07:08 | 2024-10-25 14:07:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
#define mid ((l+r)/2)
const int N=1e4+5,M=105;
const ll INF=1e18;
int n,o1,o2,m1,c1,m2,c2,a[N];ll s[N],dp1[M][M][M],dp2[M][M][M];
ll ans1;vector<pair<int,int>> ans;
void W(ll &x,ll y) {x=min(x,y);}
void clear1(int c1,int c2)
{
for(int j1=0;j1<=c1;++j1) for(int j2=0;j2<=c2;++j2)
dp1[o1][j1][j2]=INF;
}
void clear2(int c1,int c2)
{
for(int j1=0;j1<=c1;++j1) for(int j2=0;j2<=c2;++j2)
dp2[o2][j1][j2]=INF;
}
void slv(int l,int r,int c1,int c2)
{
if(!c1 && !c2) return;
o1=0;clear1(c1,c2);dp1[o1][0][0]=0;
for(int i=l;i<=mid;++i)
{
o1=(o1+1)%M;
for(int j1=0;j1<=c1;++j1) for(int j2=0;j2<=c2;++j2)
dp1[o1][j1][j2]=dp1[(o1-1+M)%M][j1][j2]+a[i];
for(int j1=0;j1<=c1;++j1) for(int j2=0;j2<=c2;++j2)
{
if(i-l+1>=m1) W(dp1[o1][j1+1][j2],dp1[(o1-m1+M)%M][j1][j2]);
if(i-l+1>=m2) W(dp1[o1][j1][j2+1],dp1[(o1-m2+M)%M][j1][j2]);
}
}
o2=0;clear2(c1,c2);dp2[o2][0][0]=0;
for(int i=r;i>mid;--i)
{
o2=(o2+1)%M;
for(int j1=0;j1<=c1;++j1) for(int j2=0;j2<=c2;++j2)
dp2[o2][j1][j2]=dp2[(o2-1+M)%M][j1][j2]+a[i];
for(int j1=0;j1<=c1;++j1) for(int j2=0;j2<=c2;++j2)
{
if(r-i+1>=m1) W(dp2[o2][j1+1][j2],dp2[(o2-m1+M)%M][j1][j2]);
if(r-i+1>=m2) W(dp2[o2][j1][j2+1],dp2[(o2-m2+M)%M][j1][j2]);
}
}
int lc1,lc2,rc1,rc2,l1,r1;ll mn=INF;
for(int j1=0;j1<=c1;++j1) for(int j2=0;j2<=c2;++j2)
{
ll t=dp1[o1][j1][j2]+dp2[o2][c1-j1][c2-j2];
if(t<mn) mn=t,lc1=j1,lc2=j2,rc1=c1-j1,rc2=c2-j2,l1=mid+1,r1=mid;
}
if(c1) for(int i=0;i<=m1;++i) if(mid-l+1>=i && r-mid>=m1-i)
for(int j1=0;j1<c1;++j1) for(int j2=0;j2<=c2;++j2)
{
ll t=dp1[(o1-i+M)%M][j1][j2]+dp2[(o2-(m1-i)+M)%M][c1-j1-1][c2-j2];
if(t<mn) mn=t,lc1=j1,lc2=j2,rc1=c1-j1-1,rc2=c2-j2,l1=mid-i+1,r1=mid+m1-i;
}
if(c2) for(int i=0;i<=m2;++i) if(mid-l+1>=i && r-mid>=m2-i)
for(int j1=0;j1<=c1;++j1) for(int j2=0;j2<c2;++j2)
{
ll t=dp1[(o1-i+M)%M][j1][j2]+dp2[(o2-(m2-i)+M)%M][c1-j1][c2-j2-1];
if(t<mn) mn=t,lc1=j1,lc2=j2,rc1=c1-j1,rc2=c2-j2-1,l1=mid-i+1,r1=mid+m2-i;
}
if(l1<=r1) ans.eb(l1,r1);
slv(l,l1-1,lc1,lc2);slv(r1+1,r,rc1,rc2);
}
int main()
{
scanf("%d %d %d %d %d",&n,&c1,&m1,&c2,&m2);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
slv(1,n,c1,c2);
sort(ans.begin(),ans.end());
for(auto [l,r]:ans) ans1+=s[r]-s[l-1];
printf("%lld\n",ans1);
for(auto [l,r]:ans) printf("%d %d\n",l-1,r);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 8044kb
input:
20 2 3 3 2 2 0 2 0 1 2 1 2 1 2 2 2 1 1 2 2 2 1 2 2
output:
22 5 8 8 10 10 12 14 17 18 20
result:
ok Sum = 22
Test #2:
score: 0
Accepted
time: 1ms
memory: 10092kb
input:
25 1 5 1 10 30 8 87 61 66 75 86 3 14 23 56 36 60 23 32 65 49 61 11 50 98 91 36 12 85
output:
933 2 7 15 25
result:
ok Sum = 933
Test #3:
score: 0
Accepted
time: 1ms
memory: 10104kb
input:
50 3 3 3 5 19 54 97 19 24 82 0 57 88 32 95 62 60 52 75 21 73 38 11 29 98 8 39 76 94 90 63 81 48 55 64 34 28 27 72 73 70 28 75 76 84 14 15 29 82 46 36 55 47 83
output:
1659 1 6 10 15 23 28 34 37 38 41 47 50
result:
ok Sum = 1659
Test #4:
score: -100
Memory Limit Exceeded
input:
100 20 1 25 2 980 361 796 376 660 459 30 116 265 564 904 831 111 427 376 848 291 126 983 411 272 596 53 757 459 340 901 182 263 595 548 471 699 450 117 63 383 17 45 967 406 858 72 212 356 598 757 70 658 310 424 100 772 505 767 239 368 793 557 574 103 175 213 313 366 24 444 690 599 106 881 224 737 46...