Submission #2714556


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


#define INFTY 0x7fffffff

int solve(int N,int K,vi& a) {
    if (K == accumulate(ALL(a), 0)) return 1;

    vector<ii> numer(N+1, ii(INFTY,-1));
    numer[0] = ii(0,0);
    int denom = 1;
#ifdef DEBUG
    cerr << numer << " /" << denom << endl;
#endif
    rep(st, N){
        vector<ii> numer2 = numer; // (N+1, ii(INFTY,-1));
        int denom2 = ((st == 0) ? 0 : denom) + a[st];
        rep(i, N) {
            if (numer[i].first == INFTY) break;

            // numer2/denom2 > numer/denom;
            ll n = (ll)numer[i].first * denom2;
            int border = n/denom; // これ以下では勝てない
            int lower = border + 1; // これ以上なら勝てる

#ifdef DEBUG
            fprintf(stderr, ";; i=%d, (%d,%d)/%d, +%d ->\n", i, numer[i].first, numer[i].second, denom, a[st]);
#endif
            // 取らない/取れない
            // ii plus0(numer[i].first, min(denom2, border));
            numer2[i].first = min(numer2[i].first, numer[i].first);
            numer2[i].second = min(denom2, max(numer2[i].second, border));
#ifdef DEBUG
            fprintf(stderr, "  (+0) (%d,%d); ", numer[i].first, border); cerr << numer2[i] << endl;
#endif
            // numer2[i] = ii(numer[i].first, min(denom2, max(numer[i].second, border-1)));
            // 取る
            // numer2[i] > numer[i]*denom2/denom
            if (lower <= denom2) {
                numer2[i+1].first = lower;
                // numer2[i+1].second = min(denom2, lower+a[st]);
                // numer2[i+1].second = min(denom2, max(numer2[i+1].second, numer[i].second+a[st]));
                numer2[i+1].second = min(denom2, max(numer2[i+1].second, numer[i].second+a[st]));
                // numer2[i+1].second = min(denom2, max(numer2[i].second, border));
                // fprintf(stderr, "  (+1) (%d,%d); ", lower, numer[i].second+a[st]); cerr << numer2[i+1] << endl;
#ifdef DEBUG
                fprintf(stderr, "  (+1) (%d,%d); ", lower, lower+a[st]); cerr << numer2[i+1] << endl;
#endif
            }
        }
#ifdef DEBUG
        cerr << numer2 << " /" << denom2 << endl;
#endif
        numer = numer2;
        denom = denom2;
    }
    for (int i=N; i>=0; --i) {
        if (IN(K, numer[i].first, numer[i].second)) return i;
        // if (numer[i].first <= K) return i;
    }
    return 0;
}

int main() {
    int N,K; cin>>N>>K;
    vi a(N);
    rep(i,N) cin >> a[i];
    cout << solve(N,K,a) << endl;
    return 0;
}

Submission Info

Submission Time
Task B - 高橋君ゲーム
User naoya_t
Language C++14 (GCC 5.4.1)
Score 100
Code Size 3727 Byte
Status
Exec Time 39 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt, s4.txt
All 100 / 100 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, s1.txt, s2.txt, s3.txt, s4.txt
Case Name Status Exec Time Memory
01.txt 38 ms 256 KB
02.txt 38 ms 256 KB
03.txt 38 ms 256 KB
04.txt 38 ms 256 KB
05.txt 39 ms 256 KB
06.txt 38 ms 256 KB
07.txt 38 ms 256 KB
08.txt 38 ms 256 KB
09.txt 39 ms 256 KB
10.txt 39 ms 256 KB
11.txt 38 ms 256 KB
12.txt 38 ms 256 KB
13.txt 38 ms 256 KB
14.txt 39 ms 256 KB
15.txt 38 ms 256 KB
16.txt 39 ms 256 KB
17.txt 38 ms 256 KB
18.txt 38 ms 256 KB
19.txt 38 ms 256 KB
20.txt 38 ms 256 KB
21.txt 2 ms 256 KB
22.txt 2 ms 256 KB
23.txt 39 ms 256 KB
24.txt 38 ms 256 KB
25.txt 2 ms 256 KB
26.txt 2 ms 256 KB
27.txt 2 ms 256 KB
28.txt 2 ms 256 KB
29.txt 38 ms 256 KB
30.txt 38 ms 256 KB
31.txt 38 ms 256 KB
32.txt 38 ms 256 KB
33.txt 38 ms 256 KB
34.txt 38 ms 256 KB
35.txt 39 ms 256 KB
36.txt 38 ms 256 KB
37.txt 38 ms 256 KB
38.txt 38 ms 256 KB
39.txt 38 ms 256 KB
40.txt 38 ms 256 KB
41.txt 38 ms 256 KB
42.txt 39 ms 256 KB
43.txt 38 ms 256 KB
44.txt 38 ms 256 KB
45.txt 38 ms 256 KB
46.txt 38 ms 256 KB
47.txt 38 ms 256 KB
48.txt 38 ms 256 KB
49.txt 39 ms 256 KB
50.txt 38 ms 256 KB
51.txt 1 ms 256 KB
52.txt 1 ms 256 KB
53.txt 1 ms 256 KB
54.txt 1 ms 256 KB
55.txt 1 ms 256 KB
56.txt 1 ms 256 KB
57.txt 1 ms 256 KB
58.txt 1 ms 256 KB
59.txt 1 ms 256 KB
60.txt 1 ms 256 KB
61.txt 1 ms 256 KB
62.txt 1 ms 256 KB
63.txt 1 ms 256 KB
64.txt 1 ms 256 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB
s3.txt 1 ms 256 KB
s4.txt 1 ms 256 KB