Submission #3790263


Source Code Expand

// #include <boost/functional/hash.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// using mlint = boost::multiprecision::cpp_int;

#include <cassert>
#include <deque>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <complex>
#include <functional>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <iomanip>

using namespace std;
using i64 = int_fast64_t;
using db = double;
using pii = pair<int, int>;
using pli = pair<int_fast64_t, int>;
using pdi = pair<db, int>;
using plpii = pair<int_fast64_t, pair<int, int>>;
template <class T> using mat = vector<vector<T>>;
template <class T> using rprque = priority_queue<T, vector<T>, greater<T>>;

#define esc(x) cout << (x) << endl, exit(0)
#define inf(T) (numeric_limits<T>::max() / 2 - 1)
#define each(i, v) for (auto i = begin(v); i != end(v); ++i)
#define reach(i, v) for (auto i = rbegin(v); i != rend(v); ++i)
#define urep(i, s, t) for (int_fast64_t i = (s); i <= (t); ++i)
#define drep(i, s, t) for (int_fast64_t i = (s); i >= (t); --i)
#define rep(i, n) urep(i, 0, (n)-1)
#define rep1(i, n) urep(i, 1, (n))
#define rrep(i, n) drep(i, (n)-1, 0)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define fir first
#define sec second
#define vct vector
#define u_map unordered_map
#define u_set unordered_set
#define l_bnd lower_bound
#define u_bnd upper_bound
#define rsz resize
#define ers erase
#define emp emplace
#define emf emplace_front
#define emb emplace_back
#define pof pop_front
#define pob pop_back
#define mkp make_pair
#define mkt make_tuple
#define popcnt __builtin_popcount

struct setupper
{
    setupper(uint_fast8_t prec)
    {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(prec);
#ifdef Local
    #define debug 1
    #define print(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
        cout << "\n-- Execution At Local ---\n"
             << "\n<Standard Output>\n"
             << "\n----------------\n\n";
        auto print_atexit = []() {
            time_t end_time = time(NULL);
            struct tm *ret = localtime(&end_time);
            cout << "\n----------------\n";
            cout << "\nSuccessfully Executed At " << (ret->tm_hour) << ":" << (ret->tm_min) << ":" << (ret->tm_sec) << "\n\n";
        };
        atexit(print_atexit);
#else
    #define debug 0
#endif
    }
} ;

template <class T, class U> ostream& operator << (ostream& s, pair<T,U> p) { return s << p.fir << " " << p.sec; }
template <class T> ostream& operator << (ostream& s, vct<T> v) { each(i,v) { if(i != begin(v)) s << " "; s << *i; } return s; }

namespace std {
    template <class T> void hash_combine(size_t &seed, T const &key) {
        seed ^= hash<T>()(key) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }
    template <class T, class U> struct hash<pair<T,U>> {
        size_t operator()(pair<T,U> const &pr) const
        {
            size_t seed = 0;
            hash_combine(seed,pr.first);
            hash_combine(seed,pr.second);
            return seed;
        }
    };
    template <class Tup, size_t index = tuple_size<Tup>::value - 1> struct hashval_calc {
        static void apply(size_t& seed, Tup const& tup) {
            hashval_calc<Tup, index - 1>::apply(seed, tup);
            hash_combine(seed,get<index>(tup));
        }
    };
    template <class Tup> struct hashval_calc<Tup,0> {
        static void apply(size_t& seed, Tup const& tup) {
            hash_combine(seed,get<0>(tup));
        }
    };
    template <class ...T> struct hash<tuple<T...>> {
        size_t operator()(tuple<T...> const& tup) const
        {
            size_t seed = 0;
            hashval_calc<tuple<T...>>::apply(seed,tup);
            return seed;
        }
    };
}

void read() {}
template <class T, class ...Rest> void read(T &x, Rest &... rest) { cin >> x; read(rest...); }
template <class T> void write(T x) { cout << x; }
template <class T, class ...Rest> void write(T x, Rest ... rest) { cout << x << ' '; write(rest...); }
void writeln() {}
template <class T, class ...Rest> void writeln(T x, Rest ... rest) { cout << x << endl; writeln(rest...); }
const auto add = [](auto &x, auto y) { x += y; };
const auto mul = [](auto &x, auto y) { x *= y; };
const auto lam_min = [](auto x, auto y) { return min(x, y); };
const auto lam_max = [](auto x, auto y) { return max(x, y); };
const auto chmax = [](auto &m, auto x) { if(m < x){ m = x; return true; } return false; };
const auto chmin = [](auto &m, auto x) { if(m > x){ m = x; return true; } return false; };
bool odd(i64 x) { return x & 1; }
bool even(i64 x) { return !odd(x); }
bool parity(i64 x, i64 y) { return odd(x) ^ even(y); }
bool bit(i64 n, uint8_t e) { return (n >> e) & 1; }
i64 mask(i64 n, uint8_t e) { return n & ((1 << e) - 1); }
int ilog(i64 x, uint64_t b = 2) {
    if (x) return ilog(x / b, b) + 1;
    return -1;
}
uint divcnt(i64 x, i64 d) { if(x | d) return x % d ? 0 : divcnt(x / d, d) + 1; return inf(uint); }
i64 qceil(i64 x, i64 y) { return x > 0 ? (x - 1) / y + 1 : x / y; }
i64 gcd(i64 a, i64 b) {
    if (!b) return abs(a);
    return gcd(b, a % b);
}
i64 lcm(i64 a, i64 b) {
    if (a | b) return abs(a / gcd(a, b) * b);
    return 0;
}
i64 extgcd(i64 a, i64 b, i64 &x, i64 &y) {
    i64 d = a;
    if (b) d = extgcd(b, a % b, y, x), y -= (a / b) * x;
    else x = 1, y = 0;
    return d;
}
template <class F> i64 binsr(i64 ok, i64 ng, const F &fn) {
    while (abs(ok - ng) > 1) {
        i64 mid = (ok + ng) / 2;
        (fn(mid) ? ok : ng) = mid;
    }
    return ok;
}
template <class T> T cmprs(T &v) {
    T tmp = v, ret = v;
    sort(all(tmp));
    tmp.erase(unique(all(tmp)), end(tmp));
    each(i, ret) *i = l_bnd(all(tmp), *i) - begin(tmp) + 1;
    return ret;
}

constexpr int dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
constexpr int dy[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
constexpr long double gold = 1.618033988;
constexpr long double eps = 1e-15;
constexpr uint_fast64_t mod = 1e9 + 7;

string s;
int n,k;

int tonum(char c) {
    return (c!='+' and c!='-')?c-'0':-1;
}

bool vis[2][60][60][60];
int max_[60][60][60],min_[60][60][60];

int solvemin(int i,int j,int h);

int solvemax(int i,int j,int h) {
    if(vis[0][i][j][h]) return max_[i][j][h];
    vis[0][i][j][h]=true;
    int ret=-inf(int);
    if(j-i==1) {
        if(tonum(s[i])>=0) {
            ret=h>0?9:tonum(s[i]);
        } else {
            if(h>0) ret=9;
        }
        return max_[i][j][h]=ret;
    }
    if(h>0) {
        urep(b,i+1,j-2)rep(c,h) {
            int lef=solvemax(i,b,c);
            int rigx=solvemax(b,j-1,h-c-1);
            int rign=solvemin(b,j-1,h-c-1);
            if(lef<inf(int) and rigx > -inf(int)) {
                ret=max(ret,lef+rigx);
            }
            if(lef<inf(int) and rign<inf(int)) {
                ret=max(ret,lef-rign);
            }
        }
    }
    if(s[j-1]=='+') {
        urep(b,i+1,j-2)rep(c,h+1) {
            int lef=solvemax(i,b,c);
            int rigx=solvemax(b,j-1,h-c);
            if(min(rigx,lef)!=-inf(int)) ret=max(ret,lef+rigx);
        }
    } else if(s[j-1]=='-') {
        urep(b,i+1,j-2)rep(c,h+1) {
            int lef=solvemax(i,b,c);
            int rign=solvemin(b,j-1,h-c);
            if(min(-rign,lef)!=-inf(int)) ret=max(ret,lef-rign);
        }
    }
    return max_[i][j][h]=ret;
}

int solvemin(int i,int j,int h) {
    if(vis[1][i][j][h]) return min_[i][j][h];
    vis[1][i][j][h]=true;
    int ret=inf(int);
    if(j-i==1) {
        if(tonum(s[i])>=0) {
            ret=h>0?0:tonum(s[i]);
        } else {
            if(h>0) ret=0;
        }
        return min_[i][j][h]=ret;
    }
    if(h>0) {
        urep(b,i+1,j-2)rep(c,h) {
            int lef=solvemin(i,b,c);
            int rigx=solvemax(b,j-1,h-c-1);
            int rign=solvemin(b,j-1,h-c-1);
            if(lef<inf(int) and rigx > -inf(int)) {
                ret=min(ret,lef-rigx);
            }
            if(lef<inf(int) and rign<inf(int)) {
                ret=min(ret,lef+rign);
            }
        }
    }
    if(s[j-1]=='-') {
        urep(b,i+1,j-2)rep(c,h+1) {
            int lef=solvemin(i,b,c);
            int rigx=solvemax(b,j-1,h-c);
            if(min(rigx,-lef)!=-inf(int)) ret=min(ret,lef-rigx);
        }
    } else if(s[j-1]=='+') {
        urep(b,i+1,j-2)rep(c,h+1) {
            int lef=solvemin(i,b,c);
            int rign=solvemin(b,j-1,h-c);
            if(min(-rign,-lef)!=-inf(int)) ret=min(ret,lef+rign);
        }
    }
    return min_[i][j][h]=ret;
}

int main() {
    read(k,s);
    n=s.size();
    int ans=solvemax(0,n,k);
    if(ans!=-inf(int)) writeln("OK",ans);
    else writeln("NG");
}

Submission Info

Submission Time
Task A - 計算ドリル
User jell
Language C++14 (GCC 5.4.1)
Score 0
Code Size 9039 Byte
Status WA
Exec Time 437 ms
Memory 1536 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 5
AC × 27
WA × 26
Set Name Test Cases
Sample example0, example1, example2, example3, example4
All example0, example1, example2, example3, example4, handmade0, handmade1, handmade2, maxrand0, maxrand1, maxrand10, maxrand11, maxrand12, maxrand13, maxrand14, maxrand15, maxrand16, maxrand17, maxrand18, maxrand19, maxrand2, maxrand3, maxrand4, maxrand5, maxrand6, maxrand7, maxrand8, maxrand9, rand0, rand1, rand10, rand11, rand12, rand13, rand14, rand15, rand16, rand17, rand18, rand19, rand2, rand3, rand4, rand5, rand6, rand7, rand8, rand9, smallrand0, smallrand1, smallrand2, smallrand3, smallrand4
Case Name Status Exec Time Memory
example0 AC 1 ms 256 KB
example1 AC 1 ms 256 KB
example2 AC 1 ms 256 KB
example3 AC 1 ms 256 KB
example4 AC 1 ms 384 KB
handmade0 AC 1 ms 256 KB
handmade1 AC 1 ms 256 KB
handmade2 AC 1 ms 256 KB
maxrand0 WA 76 ms 1536 KB
maxrand1 WA 127 ms 1536 KB
maxrand10 AC 131 ms 1536 KB
maxrand11 WA 242 ms 1536 KB
maxrand12 WA 3 ms 1536 KB
maxrand13 WA 36 ms 1536 KB
maxrand14 AC 345 ms 1536 KB
maxrand15 AC 148 ms 1536 KB
maxrand16 WA 3 ms 1536 KB
maxrand17 AC 155 ms 1536 KB
maxrand18 WA 19 ms 1536 KB
maxrand19 AC 248 ms 1536 KB
maxrand2 WA 384 ms 1536 KB
maxrand3 AC 260 ms 1536 KB
maxrand4 AC 71 ms 1536 KB
maxrand5 WA 14 ms 1536 KB
maxrand6 WA 77 ms 1536 KB
maxrand7 WA 437 ms 1536 KB
maxrand8 WA 142 ms 1536 KB
maxrand9 AC 294 ms 1536 KB
rand0 WA 1 ms 384 KB
rand1 AC 2 ms 512 KB
rand10 AC 6 ms 640 KB
rand11 WA 12 ms 768 KB
rand12 WA 2 ms 768 KB
rand13 AC 1 ms 256 KB
rand14 WA 4 ms 768 KB
rand15 AC 1 ms 256 KB
rand16 WA 49 ms 1024 KB
rand17 WA 1 ms 512 KB
rand18 WA 20 ms 1024 KB
rand19 WA 4 ms 768 KB
rand2 WA 84 ms 1152 KB
rand3 AC 1 ms 256 KB
rand4 AC 138 ms 1280 KB
rand5 WA 2 ms 640 KB
rand6 AC 2 ms 512 KB
rand7 WA 4 ms 640 KB
rand8 WA 1 ms 512 KB
rand9 WA 2 ms 384 KB
smallrand0 AC 1 ms 256 KB
smallrand1 WA 1 ms 256 KB
smallrand2 AC 1 ms 256 KB
smallrand3 AC 1 ms 256 KB
smallrand4 AC 1 ms 256 KB