Submission #44081305
Source Code Expand
#include<vector>
#include<map>
#include<set>
#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<string>
#include<bitset>
#include<stdio.h>
#include<utility>
#include<queue>
#include<stack>
#include<deque>
#include<iterator>
#include<list>
#include<iomanip>
#include<chrono>
#include<unordered_set>
#include<string>
#include<cmath>
#include<cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fast ios_base::sync_with_stdio(0),cin.tie(0)
#define ll long long
#define cout std::cout
#define cin std::cin
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define pb push_back
#define sorta(vec) sort(vec.begin(),vec.end())
#define sortd(vec) sort(vec.begin(),vec.end(),greater<int>())
#define pb push_back
#define vll vector<long long int>
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>pbds; // find_by_order, order_of_key(0-indexed)
//less , less_equal , greater , greater_equal -> rule for insertion
#define start_execution auto start = std::chrono::high_resolution_clock::now();
#define stop_execution auto stop = std::chrono::high_resolution_clock::now();
#define execution_time auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(stop - start); cerr<<"Time taken : "<<((long double)duration.count())/((long double)1e9) <<"s"<<endl;
#define nline "\n"
#define all(v) (v).begin(),(v).end()
#define pii pair<ll int,ll int>
#define piii pair<ll int,pair<ll int,ll int>>
#define mem(a,k) memset(a,k,sizeof(a));
// void print_with_precision(double val,int n)
// {
// cout << fixed << setprecision(n) <<val<<endl;
// }
void debug(int x)
{
cout<<"Value Debugged is "<<x<<endl;
}
void debug(vector<int>x)
{
cout<<"Value Debugged is "<<endl;
for(auto y:x)
{
cout<<y<<" ";
}
cout<<endl;
}
void yn(bool res){if(res==true){yes;}else{no;}}
ll mod=1000000007;
ll mod_add(ll a, ll b) {a = a % mod; b = b % mod; return (((a + b) % mod) + mod) % mod;}
ll mod_mul(ll a, ll b) {a = a % mod; b = b % mod; return (((a * b) % mod) + mod) % mod;}
ll mod_sub(ll a, ll b) {a = a % mod; b = b % mod; return (((a - b) % mod) + mod) % mod;}
ll int inv(ll int r)
{
if(r==1) return 1;
return (mod-((mod/r)*inv(mod%r))%mod+mod)%mod;
}
ll mod_div(ll a,ll b){return (a*inv(b))%mod;}
ll int ceil_div(ll int a,ll int b)
{
ll int k=a%b;
if(k>0) return (a/b)+1;
return a/b;
}
ll gcd(ll a, ll b)
{
if (!a)
return b;
return gcd(b % a, a);
}
ll int lcm(ll int a,ll int b)
{
ll int g=__gcd(a,b);
return (1LL*a*b)/g;
}
ll int pwr(ll int a,ll int b, ll int n)
{
int modd=1;
if(b==0)
return 1;
if(b%2==0)
{
ll int ans1=pwr(a,b/2,n);
ll int ans2=(ans1*ans1);
if(ans1==-1 || ans2>n)
{
//return -1;
}
return ans2;
}
ll int ans1=pwr(a,b/2,n);
ll int ans2=(ans1*ans1);
if(ans1==-1 || ans2>n)
{
// return -1;
}
ans2=(ans2*a);
if(ans2>n)
{
//return -1;
}
return ans2;
}
ll int fact(ll int n)
{
if(n<0)
{return 0;}
ll int ans=1;
if(n==0) return 1;
for(int i=1;i<=n;i++){ans=(ans*i)%mod;}return ans;
}
vector<ll> sieve(int n)
{
int*arr = new int[n + 1]();
vector<ll> vect;
for (int i = 2; i <= n; i++)
if (arr[i] == 0)
{
vect.push_back(i);
for (int j = 2 * i; j <= n; j += i)
arr[j] = 1;
}
return vect;
}
/*ll int Combination(ll int n,ll int r)
{
void pre()
{
for(int i=1;i<=100003;i++)
{
dp[i]=(1LL*dp[i-1]*i)%mod;
}
}
if(r==0)
{
return 1;
}
ll int ans1=dp[n];ll int ans2=dp[r];
ll int ans3=dp[n-r];ll int ans=(ans1*inv(ans2))%mod;
ans=(ans*inv(ans3))%mod;return ans;
}*/
template<class ForwardIterator>
void read(ForwardIterator first,ForwardIterator last)
{
while (first != last)
{
cin >> (*first);
++first;
}
}
template<class T>
void read(vector<T> &v)
{
read(v.begin(), v.end());
}
vector<vector<int>>tree_input(int n)
{
vector<vector<int>>tree(n+1);
for(int i=0;i<n-1;i++)
{
int u,v;
cin>>u>>v;
tree[u].push_back(v);
tree[v].push_back(u);
}
return tree;
}
bool cmp(vector<int>&v1,vector<int>&v2)
{
if(v1[0]>v2[0])
{
return true;
}
return false;
}
bool cmp2(vector<ll int>&v1,vector<ll int>&v2)
{
if(v1[0]<v2[0])
{
return true;
}
return false;
}
//Code starts here
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
fast;
//start_execution
int tt=1;
//cin>>tt;
for(int tc=0;tc<tt;tc++)
{
ll int n,m;
cin>>n>>m;
vector<int>v1;
vector<int>v2;
vector<int>v3;
for(int i=0;i<n;i++)
{
int t,x;
cin>>t>>x;
if(t==0)
{
v1.push_back(x);
}
else if(t==1)
{
v2.push_back(x);
}
else if(t==2)
{
v3.push_back(x);
}
}
sort(all(v1));
reverse(all(v1));
sort(all(v2));
reverse(all(v2));
sort(all(v3));
reverse(all(v3));
vector<ll int>ps(v2.size(),0);
vector<ll int>ps1;
if(v2.size()>0)
{
ps[0]=v2[0];
}
if(v3.size()>0)
{
ps1.push_back(v3[0]);
}
for(int i=1;i<v2.size();i++)
{
ps[i]=ps[i-1]+v2[i];
}
for(int i=1;i<v3.size();i++)
{
ps1.push_back(ps1[i-1]+v3[i]);
}
ll int left=0;
ll int right=10000000000000000;
ll int ans=0;
while(left<=right)
{
// cout<<left<<" "<<right<<endl;
ll int mid=(left+right)/2;
ll int tot=0;
ll int av=m;
int i=0;
while(i<v1.size() && av>0)
{
if(v2.size()==0 || v1[i]>=v2[0])
{
tot+=v1[i];
av--;
}
else
{
break;
}
i++;
}
//now v1 available (i,..)
//v2(0,..)
//cout<<tot<<endl;
ll int need=mid-tot;
if(need<=0)
{
left=mid+1;
continue;
}
vector<ll int>temp;
int j=i;
int t=av;
while(i<v1.size() && t>0)
{
// cout<<i<<endl;
if(temp.size()==0)
{
temp.push_back(v1[i]);
t--;
}
else
{
temp.push_back(temp.back()+v1[i]);
t--;
}
if(temp.back()>=need)
{
break;
}
i++;
}
/* cout<<need<<endl;
for(auto x:temp)
{
cout<<x<<" ";
}
cout<<endl;*/
//take element from v2 from front then take coresponding from v1
bool res=false;
// cout<<"s"<<endl;
for(int take=0;take<=av && take<=v2.size();take++)
{
if(take>0 && ps1.size()==0)
{
break;
}
//cout<<take<<endl;
auto d=lower_bound(all(ps1),take);
if(d==ps1.end())
{
continue;
}
//cout<<take<<endl;
int rem=av-take;
if(take>0)
{
int inde=d-ps1.begin();
rem=rem-(inde)-1;
}
if(rem<0)
{
continue;
}
ll int can=0;
if(rem>0)
{
int d=temp.size()-1;
can=temp[min(d,rem-1)];
}
if(take>0)
{
//cout<<ps[take-1]<<endl;
int d=ps.size()-1;
can+=ps[min(d,take-1)];
}
if(can>=need)
{
//cout<<take<<endl;
res=true;
break;
}
}
if(res)
{
ans=mid;
left=mid+1;
}
else
{
right=mid-1;
}
}
cout<<ans<<endl;
}
//stop_execution
//execution_time
return 0;
}
Submission Info
Submission Time
2023-07-29 22:43:07+0900
Task
F - Cans and Openers
User
silenttkillerr
Language
C++ (GCC 9.2.1)
Score
0
Code Size
9498 Byte
Status
RE
Exec Time
160 ms
Memory
7612 KiB
Compile Error
./Main.cpp: In function ‘long long int pwr(long long int, long long int, long long int)’:
./Main.cpp:96:9: warning: unused variable ‘modd’ [-Wunused-variable]
96 | int modd=1;
| ^~~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:270:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
270 | for(int i=1;i<v2.size();i++)
| ~^~~~~~~~~~
./Main.cpp:274:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
274 | for(int i=1;i<v3.size();i++)
| ~^~~~~~~~~~
./Main.cpp:295:20: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
295 | while(i<v1.size() && av>0)
| ~^~~~~~~~~~
./Main.cpp:329:20: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
329 | while(i<v1.size() && t>0)
| ~^~~~~~~~~~
./Main.cpp:359:44: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
359 | for(int take=0;take<=av && take<=v2.size();take++)
| ~~~~^~~~~~~~~~~
./Main.cpp:325:17: warning: unused variable ‘j’ [-Wunused-variable]
325 | int j=i;
| ^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 500
Status
Set Name
Test Cases
Sample
sample00.txt, sample01.txt, sample02.txt
All
sample00.txt, sample01.txt, sample02.txt, testcase00.txt, testcase01.txt, testcase02.txt, testcase03.txt, testcase04.txt, testcase05.txt, testcase06.txt, testcase07.txt, testcase08.txt, testcase09.txt, testcase10.txt, testcase11.txt, testcase12.txt, testcase13.txt, testcase14.txt, testcase15.txt, testcase16.txt, testcase17.txt, testcase18.txt, testcase19.txt, testcase20.txt, testcase21.txt, testcase22.txt, testcase23.txt, testcase24.txt, testcase25.txt, testcase26.txt, testcase27.txt, testcase28.txt, testcase29.txt, testcase30.txt, testcase31.txt, testcase32.txt, testcase33.txt, testcase34.txt, testcase35.txt, testcase36.txt, testcase37.txt, testcase38.txt, testcase39.txt, testcase40.txt, testcase41.txt, testcase42.txt
Case Name
Status
Exec Time
Memory
sample00.txt
AC 7 ms
3508 KiB
sample01.txt
AC 2 ms
3404 KiB
sample02.txt
AC 2 ms
3616 KiB
testcase00.txt
WA 58 ms
4060 KiB
testcase01.txt
AC 49 ms
5524 KiB
testcase02.txt
RE 148 ms
5980 KiB
testcase03.txt
AC 55 ms
4760 KiB
testcase04.txt
AC 145 ms
6452 KiB
testcase05.txt
WA 52 ms
4688 KiB
testcase06.txt
AC 91 ms
5720 KiB
testcase07.txt
AC 101 ms
6168 KiB
testcase08.txt
AC 75 ms
5424 KiB
testcase09.txt
AC 130 ms
6400 KiB
testcase10.txt
AC 71 ms
5272 KiB
testcase11.txt
AC 97 ms
6140 KiB
testcase12.txt
AC 121 ms
6536 KiB
testcase13.txt
AC 126 ms
6284 KiB
testcase14.txt
AC 82 ms
5044 KiB
testcase15.txt
AC 76 ms
5792 KiB
testcase16.txt
AC 129 ms
6496 KiB
testcase17.txt
AC 132 ms
6360 KiB
testcase18.txt
AC 103 ms
7612 KiB
testcase19.txt
AC 92 ms
5892 KiB
testcase20.txt
AC 137 ms
6540 KiB
testcase21.txt
AC 128 ms
6344 KiB
testcase22.txt
AC 110 ms
5832 KiB
testcase23.txt
AC 118 ms
5792 KiB
testcase24.txt
AC 145 ms
6500 KiB
testcase25.txt
AC 63 ms
4956 KiB
testcase26.txt
AC 90 ms
6284 KiB
testcase27.txt
AC 94 ms
5740 KiB
testcase28.txt
AC 144 ms
6100 KiB
testcase29.txt
AC 130 ms
6276 KiB
testcase30.txt
AC 92 ms
6664 KiB
testcase31.txt
AC 153 ms
5716 KiB
testcase32.txt
AC 155 ms
6192 KiB
testcase33.txt
AC 143 ms
6508 KiB
testcase34.txt
AC 93 ms
6480 KiB
testcase35.txt
AC 104 ms
6268 KiB
testcase36.txt
AC 158 ms
6200 KiB
testcase37.txt
AC 144 ms
6496 KiB
testcase38.txt
AC 61 ms
5676 KiB
testcase39.txt
AC 160 ms
5740 KiB
testcase40.txt
AC 159 ms
6128 KiB
testcase41.txt
AC 141 ms
6404 KiB
testcase42.txt
AC 79 ms
5792 KiB