QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #217333 | #1773. Breaking Bars | PhantomThreshold | TL | 35ms | 3848kb | C++20 | 1.5kb | 2023-10-16 19:24:30 | 2023-10-16 19:24:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
vector<vector<int>> id(7,vector<int>(7));
vector<int> x(33),y(33);
int idx=0;
for(int i=6;i>=1;i--)
for(int j=i;j>=1;j--)
{
id[i][j]=id[j][i]=++idx;
x[idx]=i;y[idx]=j;
}
int n,t;
cin>>n>>t;
vector<int> cnt(33);
int tot=0;
for(int i=1;i<=n;i++)
{
int xi,yi;
char ch;
cin>>xi>>ch>>yi;
cnt[id[xi][yi]]++;
tot+=xi*yi;
}
int ans=9;
function<void(int,int,int,int,int)> dfs=[&](int pos,int sum,int cuts,int curcut,int waste)
{
if(cuts>=ans)return;
if(tot-waste<t*2)return;
// cerr<<"dfs "<<pos<<' '<<sum<<' '<<cuts<<' '<<curcut<<' '<<tot-waste<<' '<<tot<<' '<<waste<<endl;
// for(int i=1;i<=idx;i++)cerr<<cnt[i]<<' ';cerr<<endl;
int tmp=sum;
for(int i=pos;i<=idx;i++)
{
tmp+=(cnt[i]/2)*x[i]*y[i];
}
if(tmp>=t)
{
ans=min(ans,cuts);
return;
}
if(pos>idx)return;
dfs(pos+1,sum+(cnt[pos]/2)*x[pos]*y[pos],cuts,0,waste+(cnt[pos]%2)*x[pos]*y[pos]);
if(cnt[pos] and curcut<2)
{
cnt[pos]--;
for(int i=1;i<x[pos];i++)
{
cnt[id[i][y[pos]]]++;
cnt[id[x[pos]-i][y[pos]]]++;
dfs(pos,sum,cuts+1,curcut+1,waste);
cnt[id[i][y[pos]]]--;
cnt[id[x[pos]-i][y[pos]]]--;
}
for(int i=1;i<y[pos];i++)
{
cnt[id[x[pos]][i]]++;
cnt[id[x[pos]][y[pos]-i]]++;
dfs(pos,sum,cuts+1,curcut+1,waste);
cnt[id[x[pos]][i]]--;
cnt[id[x[pos]][y[pos]-i]]--;
}
cnt[pos]++;
}
};
dfs(1,0,0,0,0);
cout<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3848kb
input:
16 118 5x6 3x5 4x5 6x3 6x1 1x1 4x5 4x5 2x3 1x2 5x3 5x3 6x2 3x6 5x6 4x2
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
6 30 2x3 3x3 1x5 2x5 3x5 3x5
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
3 2 1x1 1x1 1x2
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
4 25 2x3 3x3 2x5 5x5
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
5 10 1x1 1x1 1x1 1x1 4x4
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
6 34 1x1 1x2 2x3 3x3 5x5 5x5
output:
2
result:
ok single line: '2'
Test #7:
score: 0
Accepted
time: 26ms
memory: 3488kb
input:
15 70 1x1 1x2 1x3 1x4 1x5 2x2 2x3 2x4 2x5 3x3 3x4 3x5 4x4 4x5 5x5
output:
7
result:
ok single line: '7'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
11 40 1x1 1x2 1x3 2x3 2x4 4x5 2x2 2x2 1x4 2x4 4x5
output:
3
result:
ok single line: '3'
Test #9:
score: 0
Accepted
time: 5ms
memory: 3800kb
input:
20 74 4x3 5x1 4x2 3x3 1x2 2x1 4x2 1x5 1x1 1x4 1x1 5x5 1x4 4x5 3x2 3x5 1x2 3x4 1x1 2x3
output:
6
result:
ok single line: '6'
Test #10:
score: 0
Accepted
time: 12ms
memory: 3828kb
input:
20 104 4x2 2x3 4x5 5x1 1x3 4x3 1x2 1x1 5x2 5x4 5x5 4x1 5x5 3x5 4x2 3x1 3x1 5x4 2x1 4x4
output:
6
result:
ok single line: '6'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
13 44 5x4 3x2 3x2 4x1 4x4 1x2 1x5 1x2 1x1 3x5 1x2 1x3 3x2
output:
5
result:
ok single line: '5'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
5 21 1x3 1x2 5x4 4x4 1x1
output:
3
result:
ok single line: '3'
Test #13:
score: 0
Accepted
time: 5ms
memory: 3844kb
input:
18 77 5x4 4x2 5x5 1x4 3x1 4x3 2x3 1x1 3x4 5x2 5x3 2x2 2x1 2x1 1x2 5x3 3x3 1x4
output:
6
result:
ok single line: '6'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
9 30 5x2 5x3 1x4 1x4 2x3 1x2 3x3 2x3 4x1
output:
5
result:
ok single line: '5'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
8 37 2x4 1x3 5x4 5x5 2x4 1x4 1x2 1x4
output:
2
result:
ok single line: '2'
Test #16:
score: 0
Accepted
time: 35ms
memory: 3540kb
input:
19 103 1x5 5x2 2x2 5x4 1x5 1x1 5x5 2x2 2x5 5x4 3x4 3x2 4x4 5x4 5x3 2x2 2x4 4x3 3x3
output:
7
result:
ok single line: '7'
Test #17:
score: 0
Accepted
time: 26ms
memory: 3648kb
input:
19 75 2x1 1x1 5x5 2x4 1x3 2x3 2x2 2x3 4x5 4x3 3x1 4x1 4x2 4x4 5x1 1x4 1x5 5x3 3x1
output:
7
result:
ok single line: '7'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
20 81 2x3 2x5 5x3 2x1 3x1 5x2 4x5 2x1 1x5 5x2 2x5 1x5 3x2 1x5 1x2 4x2 4x2 5x4 3x2 3x3
output:
2
result:
ok single line: '2'
Test #19:
score: -100
Time Limit Exceeded
input:
47 297 3x5 3x2 1x5 5x6 5x5 5x5 4x2 5x4 4x1 6x2 6x6 5x3 1x2 2x6 6x2 3x3 2x2 2x2 1x4 2x5 5x3 4x4 6x3 3x6 5x4 3x6 3x1 6x1 3x1 1x2 3x4 1x6 6x6 5x3 1x1 5x5 2x1 1x4 5x1 5x6 2x1 4x6 2x2 6x6 2x3 6x1 3x1