QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#32212 | #2572. Box Packing | RobeZH# | WA | 3ms | 3860kb | C++ | 773b | 2022-05-18 02:19:57 | 2022-05-18 02:20:04 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,n) for(int i=1;i<=n;++i)
#define st first
#define nd second
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
const int N = 1e5+5,mod=1e9+7;
pr a[N];
int dp[N],is[N],mx,n,k,ans,la[N];
bool in[N];
int main() {
scanf("%d%d",&n,&k);
rep(i,n)scanf("%d%d",&a[i].st,&a[i].nd);
sort(a+1,a+n+1);
ans=0;
rep(tim,k){
dp[0]=0;is[0]=0;mx=0;
rep(i,n)if(!in[i]){
int to=upper_bound(dp,dp+mx+1,a[i].nd)-dp;
la[i]=is[to-1];
dp[to]=a[i].nd;
is[to]=i;
mx=max(mx,to);
}
ans+=mx;
int now=is[mx];
while(now!=0)in[now]=1,now=la[now];
}
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3860kb
input:
4 1 2 2 4 2 3 4 5 5
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3800kb
input:
4 2 2 2 4 2 3 4 5 5
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3796kb
input:
10 2 8 12 15 5 13 19 11 5 2 13 13 12 5 6 8 6 14 2 16 3
output:
7
result:
ok 1 number(s): "7"
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3776kb
input:
10 2 16 4 2 5 11 16 15 5 6 12 2 1 9 16 9 10 12 11 11 17
output:
7
result:
wrong answer 1st numbers differ - expected: '8', found: '7'