Submission #640913


Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

int N,X;
int T[100000],A[100000];

bool C(int lim){
    priority_queue<pint>ord;
    priority_queue<pint>good;
    rep(i,N)ord.push(pint(T[i],i));

    int sum=0,prev=-1;
    for(int t=lim;t>=0;t--){
        while(ord.size()&&ord.top().fi>=t){
            int tmp=ord.top().se;
            ord.pop();
            good.push(pint(A[tmp],tmp));
        }
        if(good.size()==0)continue;

        pint p=good.top();
        if(p.se==prev){
            if(good.size()==1)continue;
            good.pop();
            pint tmp=good.top();good.push(p);
            p=tmp;
        }
        sum+=p.fi;
        prev=p.se;
    }

    return sum>=X;
}

signed main(){
    cin>>N>>X;
    rep(i,N)cin>>T[i],T[i]--;
    rep(i,N)cin>>A[i];

    int ub=111111,lb=-1;
    while(ub-lb>1){
        int mid=(ub+lb)/2;
        if(C(mid))ub=mid;
        else lb=mid;
    }
    if(ub==111111)cout<<-1<<endl;
    else cout<<ub+1<<endl;

    return 0;
}

Submission Info

Submission Time
Task B - DDPC特別ビュッフェⅡ
User latte0119
Language C++ (GCC 4.9.2)
Score 0
Code Size 1545 Byte
Status WA
Exec Time 1002 ms
Memory 7648 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 10 0 / 40
Status
AC × 7
AC × 26
WA × 1
AC × 34
WA × 11
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 00_example_04.txt, 00_example_05.txt, 00_example_06.txt, 00_example_07.txt
Subtask1 00_example_01.txt, 00_example_03.txt, 00_example_04.txt, 00_example_05.txt, 00_example_06.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 10_rand_06.txt, 10_rand_07.txt, 10_rand_08.txt, 10_rand_09.txt, 10_rand_10.txt, 20_hand_01.txt, 20_hand_02.txt, 20_hand_03.txt, 20_hand_04.txt, 20_hand_05.txt, 20_hand_06.txt, 20_hand_07.txt, 20_hand_08.txt, 20_hand_09.txt, 20_hand_10.txt, 20_hand_11.txt, 20_hand_12.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 00_example_04.txt, 00_example_05.txt, 00_example_06.txt, 00_example_07.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 10_rand_06.txt, 10_rand_07.txt, 10_rand_08.txt, 10_rand_09.txt, 10_rand_10.txt, 20_hand_01.txt, 20_hand_02.txt, 20_hand_03.txt, 20_hand_04.txt, 20_hand_05.txt, 20_hand_06.txt, 20_hand_07.txt, 20_hand_08.txt, 20_hand_09.txt, 20_hand_10.txt, 20_hand_11.txt, 20_hand_12.txt, 40_rand_01.txt, 40_rand_02.txt, 40_rand_03.txt, 40_rand_04.txt, 40_rand_05.txt, 40_rand_06.txt, 40_rand_07.txt, 40_rand_08.txt, 40_rand_09.txt, 40_rand_10.txt, 50_hand_01.txt, 50_hand_02.txt, 50_hand_03.txt, 50_hand_04.txt, 50_hand_05.txt, 50_hand_06.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 25 ms 932 KB
00_example_02.txt AC 25 ms 928 KB
00_example_03.txt AC 26 ms 932 KB
00_example_04.txt AC 30 ms 924 KB
00_example_05.txt AC 30 ms 928 KB
00_example_06.txt AC 26 ms 932 KB
00_example_07.txt AC 25 ms 800 KB
10_rand_01.txt AC 84 ms 924 KB
10_rand_02.txt AC 30 ms 928 KB
10_rand_03.txt AC 77 ms 1292 KB
10_rand_04.txt AC 58 ms 924 KB
10_rand_05.txt AC 47 ms 1008 KB
10_rand_06.txt AC 31 ms 928 KB
10_rand_07.txt AC 807 ms 7392 KB
10_rand_08.txt AC 36 ms 840 KB
10_rand_09.txt AC 654 ms 4632 KB
10_rand_10.txt AC 290 ms 3452 KB
20_hand_01.txt AC 679 ms 7536 KB
20_hand_02.txt AC 877 ms 7536 KB
20_hand_03.txt AC 738 ms 7532 KB
20_hand_04.txt AC 1002 ms 7544 KB
20_hand_05.txt AC 834 ms 7536 KB
20_hand_06.txt AC 675 ms 7532 KB
20_hand_07.txt AC 30 ms 924 KB
20_hand_08.txt AC 24 ms 804 KB
20_hand_09.txt AC 834 ms 7544 KB
20_hand_10.txt WA 849 ms 7540 KB
20_hand_11.txt AC 674 ms 7536 KB
20_hand_12.txt AC 708 ms 7532 KB
40_rand_01.txt WA 30 ms 812 KB
40_rand_02.txt WA 29 ms 928 KB
40_rand_03.txt AC 76 ms 1280 KB
40_rand_04.txt WA 28 ms 920 KB
40_rand_05.txt WA 45 ms 1012 KB
40_rand_06.txt AC 32 ms 928 KB
40_rand_07.txt WA 741 ms 7380 KB
40_rand_08.txt WA 35 ms 916 KB
40_rand_09.txt WA 489 ms 4636 KB
40_rand_10.txt AC 273 ms 3452 KB
50_hand_01.txt WA 642 ms 7536 KB
50_hand_02.txt WA 323 ms 3916 KB
50_hand_03.txt WA 668 ms 7536 KB
50_hand_04.txt AC 804 ms 7648 KB
50_hand_05.txt AC 807 ms 7536 KB
50_hand_06.txt AC 806 ms 7528 KB