Submission #2961389

Source Code Expand

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

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair

int solve(int D,int G,vi& p,vi& c) {
    int P = 1 << D;
    vector<int> bonus(P, 0), bonus_k(P, 0);
    for (int i=0,b=1; i<D; ++i,b<<=1) {
        bonus[b] = (i+1)*100 * p[i] + c[i];
        bonus_k[b] = p[i];
    }
    // zeta
    for (int i=0,b=1; i<D; ++i,b<<=1) {
        for (int j=0; j<P; ++j) {
            if (j & b) bonus[j] += bonus[j ^ b];
            if (j & b) bonus_k[j] += bonus_k[j ^ b];
        }
    }

    int best = INT_MAX;
    for (int j=0; j<P; ++j) {
        int rest = G - bonus[j], bk = bonus_k[j];
        if (rest <= 0) {
            best = min(best, bk);
        } else {
            for (int i=D-1,b=1<<(D-1); i>=0; --i,b>>=1) {
                if (!(j & b)) {
                    int u = (i+1)*100, k = max(0, (rest+u-1)/u);
                    if (k <= p[i]) {
                        best = min(best, bk+k);
                    }
                }
            }
        }
    }
    return best;
}

int main() {
    int D,G; cin >> D >> G;
    vi p(D), c(D);
    rep(i,D) cin >> p[i] >> c[i];
    cout << solve(D,G,p,c) << endl;
    return 0;
}

Submission Info

Submission Time
Task C - All Green
User naoya_t
Language C++14 (GCC 5.4.1)
Score 300
Code Size 2337 Byte
Status
Exec Time 1 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02, a03, a04
All 300 / 300 a01, a02, a03, a04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24
Case Name Status Exec Time Memory
a01 1 ms 256 KB
a02 1 ms 256 KB
a03 1 ms 256 KB
a04 1 ms 256 KB
b05 1 ms 256 KB
b06 1 ms 256 KB
b07 1 ms 256 KB
b08 1 ms 256 KB
b09 1 ms 256 KB
b10 1 ms 256 KB
b11 1 ms 256 KB
b12 1 ms 256 KB
b13 1 ms 256 KB
b14 1 ms 256 KB
b15 1 ms 256 KB
b16 1 ms 256 KB
b17 1 ms 256 KB
b18 1 ms 256 KB
b19 1 ms 256 KB
b20 1 ms 256 KB
b21 1 ms 256 KB
b22 1 ms 256 KB
b23 1 ms 256 KB
b24 1 ms 256 KB