Submission #642320
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;} vint a[101010]; int N,X; int T[101010],A[101010]; bool C(int t){ priority_queue<int>que; for(int i=101010-1;i>t;i--)rep(j,a[i].size())que.push(a[i][j]); int sum=0; for(int i=t;i>=0;i--){ rep(j,a[i].size())que.push(a[i][j]); if(que.empty())continue; sum+=que.top(); que.pop(); } return sum>=X; } signed main(){ cin>>N>>X; rep(i,N)cin>>T[i],T[i]--; rep(i,N)cin>>A[i]; rep(i,N)a[T[i]].pb(A[i]); int lb=-1,ub=101010; while(ub-lb>1){ int mid=(ub+lb)/2; if(C(mid))ub=mid; else lb=mid; } if(ub==101010)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 | 50 |
Code Size | 1269 Byte |
Status | AC |
Exec Time | 394 ms |
Memory | 9692 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 10 / 10 | 40 / 40 | ||||||
Status |
|
|
|
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 | 34 ms | 3164 KB |
00_example_02.txt | AC | 34 ms | 3168 KB |
00_example_03.txt | AC | 34 ms | 3168 KB |
00_example_04.txt | AC | 36 ms | 3296 KB |
00_example_05.txt | AC | 36 ms | 3292 KB |
00_example_06.txt | AC | 34 ms | 3164 KB |
00_example_07.txt | AC | 34 ms | 3228 KB |
10_rand_01.txt | AC | 36 ms | 3288 KB |
10_rand_02.txt | AC | 34 ms | 3156 KB |
10_rand_03.txt | AC | 48 ms | 3544 KB |
10_rand_04.txt | AC | 35 ms | 3292 KB |
10_rand_05.txt | AC | 41 ms | 3420 KB |
10_rand_06.txt | AC | 35 ms | 3292 KB |
10_rand_07.txt | AC | 241 ms | 7972 KB |
10_rand_08.txt | AC | 36 ms | 3292 KB |
10_rand_09.txt | AC | 166 ms | 6044 KB |
10_rand_10.txt | AC | 112 ms | 5296 KB |
20_hand_01.txt | AC | 318 ms | 9656 KB |
20_hand_02.txt | AC | 394 ms | 7384 KB |
20_hand_03.txt | AC | 246 ms | 7392 KB |
20_hand_04.txt | AC | 250 ms | 7876 KB |
20_hand_05.txt | AC | 250 ms | 8232 KB |
20_hand_06.txt | AC | 221 ms | 7392 KB |
20_hand_07.txt | AC | 35 ms | 3292 KB |
20_hand_08.txt | AC | 37 ms | 3228 KB |
20_hand_09.txt | AC | 226 ms | 8536 KB |
20_hand_10.txt | AC | 222 ms | 8476 KB |
20_hand_11.txt | AC | 196 ms | 7512 KB |
20_hand_12.txt | AC | 201 ms | 7396 KB |
40_rand_01.txt | AC | 34 ms | 3296 KB |
40_rand_02.txt | AC | 35 ms | 3296 KB |
40_rand_03.txt | AC | 49 ms | 3612 KB |
40_rand_04.txt | AC | 36 ms | 3292 KB |
40_rand_05.txt | AC | 39 ms | 3296 KB |
40_rand_06.txt | AC | 36 ms | 3164 KB |
40_rand_07.txt | AC | 241 ms | 8104 KB |
40_rand_08.txt | AC | 37 ms | 3296 KB |
40_rand_09.txt | AC | 180 ms | 6228 KB |
40_rand_10.txt | AC | 108 ms | 5176 KB |
50_hand_01.txt | AC | 240 ms | 9692 KB |
50_hand_02.txt | AC | 129 ms | 5728 KB |
50_hand_03.txt | AC | 278 ms | 7408 KB |
50_hand_04.txt | AC | 230 ms | 7920 KB |
50_hand_05.txt | AC | 231 ms | 7940 KB |
50_hand_06.txt | AC | 229 ms | 7936 KB |