DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選

Submission #640913

Source codeソースコード

#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

Task問題 B - DDPC特別ビュッフェⅡ
User nameユーザ名 ひふみ☆
Created time投稿日時
Language言語 C++ (GCC 4.9.2)
Status状態 WA
Score得点 0
Source lengthソースコード長 1545 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score 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 0 / 10 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 0 / 40 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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
20_hand_11.txt AC 674 ms 7536 KB
20_hand_12.txt AC 708 ms 7532 KB
40_rand_01.txt WA
40_rand_02.txt WA
40_rand_03.txt AC 76 ms 1280 KB
40_rand_04.txt WA
40_rand_05.txt WA
40_rand_06.txt AC 32 ms 928 KB
40_rand_07.txt WA
40_rand_08.txt WA
40_rand_09.txt WA
40_rand_10.txt AC 273 ms 3452 KB
50_hand_01.txt WA
50_hand_02.txt WA
50_hand_03.txt WA
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