Submission #3214905
Source Code Expand
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <limits.h>
#include <cinttypes>
#include <string.h>
#include <bits/stdc++.h>
using namespace std;
#define countof(a) (sizeof(a)/sizeof(*a))
#define vi vector<int>
#define vvi vector<vector<int> >
#define vpi vector<pi >
#define pi pair<int,int>
#define fi first
#define se second
#define all(n) n.begin(), n.end()
#define FOR(var, to) for (register s64 var = 0; var < (s64)to; var++)
#define FROMTO(var, from, to) for (register s64 var = from; var <= (s64)to; var++)
#define INIT(var) FOR(i,countof(var)) var[i] = 0
#define INPUT(var) FOR(i,countof(var)) var[i] = ri()
#define SORT(v) qsort(v,countof(v),sizeof(*v),int_less)
#define SORTT(v) qsort(v,countof(v),sizeof(*v),int_greater)
#define QSORT(v,b) qsort(v,countof(v),sizeof(*v),b)
#define MOD 1000000007
#define INF (1 << 30)
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef int64_t s64;
template<int mod>
struct ModInt{
int x;
ModInt():x(0){}
ModInt(long long y):x(y>=0?y%mod:(mod-(-y)%mod)%mod){}
ModInt &operator+=(const ModInt &p){
if((x+=p.x)>=mod)x-=mod;
return *this;
}
ModInt &operator-=(const ModInt &p){
if((x+=mod-p.x)>=mod)x-=mod;
return *this;
}
ModInt &operator*=(const ModInt &p){
x=(int)(1LL*x*p.x%mod);
return *this;
}
ModInt &operator/=(const ModInt &p){
*this*=p.inverse();
return *this;
}
ModInt operator-()const{return ModInt(-x);}
ModInt operator+(const ModInt &p)const{return ModInt(*this)+=p;}
ModInt operator-(const ModInt &p)const{return ModInt(*this)-=p;}
ModInt operator*(const ModInt &p)const{return ModInt(*this)*=p;}
ModInt operator/(const ModInt &p)const{return ModInt(*this)/=p;}
bool operator==(const ModInt &p)const{return x==p.x;}
bool operator!=(const ModInt &p)const{return x!=p.x;}
ModInt inverse()const{
int a=x,b=mod,u=1,v=0,t;
while(b>0){
t=a/b;
a-=t*b;
swap(a,b);
u-=t*v;
swap(u,v);
}
return ModInt(u);
}
friend ostream &operator<<(ostream &os,const ModInt<mod> &p){
return os<<p.x;
}
friend istream &operator>>(istream &is,ModInt<mod> &a){
long long x;
is>>x;
a=ModInt<mod>(x);
return (is);
}
};
typedef ModInt<MOD> mint;
struct UnionFind{
vi data;
UnionFind(int size):data(size,-1){}
bool unite(int x,int y) {
x=root(x);y=root(y);
if(x!=y){
if(data[y]<data[x])swap(x,y);
data[x]+=data[y];data[y]=x;
}
return x!=y;
}
bool find(int x,int y) {
return root(x)==root(y);
}
int root(int x) {
return data[x]<0?x:data[x]=root(data[x]);
}
int size(int x) {
return -data[root(x)];
}
bool united() {
int comroot = -1;
FOR(i,data.size()) {
if (comroot != -1 && root(i) != comroot) return false;
comroot = root(i);
}
return true;
}
};
static inline int ri() {
int a;
scanf("%d", &a);
return a;
}
static inline s64 rs64() {
s64 a;
scanf("%" SCNd64, &a);
return a;
}
static inline void wi(int a) {
printf("%d", a);
}
static inline void wu64(u64 a) {
printf("%" PRIu64, a);
}
static inline void ws64(s64 a) {
printf("%" PRId64, a);
}
int int_less(const void *a, const void *b) {
return (*((const int*)a) - *((const int*)b));
}
int int_greater(const void *a, const void *b) {
return (*((const int*)b) - *((const int*)a));
}
int main() {
int n;cin>>n;
int w;cin>>w;
int a[n],b[n];
FOR(i,n)cin>>a[i]>>b[i];
vi nn[4];
FOR(i,n) nn[a[i]-a[0]].push_back(b[i]);
vi nn_sum[4];
FOR(i,4) {
sort(all(nn[i]),greater<int>());
/*
for (auto i : nn[i]) cout << i << " ";
cout << endl; */
if (nn[i].size()) {
nn_sum[i].push_back(nn[i][0]);
FROMTO(j,1,nn[i].size()-1) {
nn_sum[i].push_back(nn_sum[i][j-1]+nn[i][j]);
}
}
}
int res = 0;
FOR(i,nn[0].size()+1) {
s64 cost0 = i*((s64)a[0]);
if (cost0 > w) break;
FOR(j,nn[1].size()+1) {
s64 cost1 = cost0 + j*((s64)a[0]+1);
if (cost1 > w) break;
FOR(k,nn[2].size()+1) {
s64 cost2 = cost1 + k*((s64)a[0]+2);
if (cost2 > w) break;
int l = (w-cost2)/(a[0]+3);
l = min(l,(int)nn[3].size());
int score = 0;
// cout << i << j << k <<l << endl;
score += i?nn_sum[0][i-1]:0;
score += j?nn_sum[1][j-1]:0;
score += k?nn_sum[2][k-1]:0;
score += l?nn_sum[3][l-1]:0;
res = max(res, score);
}
}
}
cout << res << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Simple Knapsack |
User |
QCFium |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
5256 Byte |
Status |
AC |
Exec Time |
1 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0, example1, example2, example3 |
All |
antigreedy0, antigreedy1, antigreedy2, example0, example1, example2, example3, quarter0, quarter1, quarter2, rand0, rand1, rand2, smallw0, smallw1, smallw2 |
Case Name |
Status |
Exec Time |
Memory |
antigreedy0 |
AC |
1 ms |
256 KB |
antigreedy1 |
AC |
1 ms |
256 KB |
antigreedy2 |
AC |
1 ms |
256 KB |
example0 |
AC |
1 ms |
256 KB |
example1 |
AC |
1 ms |
256 KB |
example2 |
AC |
1 ms |
256 KB |
example3 |
AC |
1 ms |
256 KB |
quarter0 |
AC |
1 ms |
256 KB |
quarter1 |
AC |
1 ms |
256 KB |
quarter2 |
AC |
1 ms |
256 KB |
rand0 |
AC |
1 ms |
256 KB |
rand1 |
AC |
1 ms |
256 KB |
rand2 |
AC |
1 ms |
256 KB |
smallw0 |
AC |
1 ms |
256 KB |
smallw1 |
AC |
1 ms |
256 KB |
smallw2 |
AC |
1 ms |
256 KB |