QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#32212#2572. Box PackingRobeZH#WA 3ms3860kbC++773b2022-05-18 02:19:572022-05-18 02:20:04

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-18 02:20:04]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3860kb
  • [2022-05-18 02:19:57]
  • 提交

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'