Submission #19661541


Source Code Expand

Copy
/*
g++ -O2 --std=c++17 -D LOCAL A.cpp
*/

#include <iostream>
#include <iomanip>
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <limits.h>

using namespace std;

typedef long long LL;

#ifdef LOCAL
#define dlog(x) { cerr << '[' << __LINE__ << "] " << x << endl; }
#define dvar(v) { cerr << '[' << __LINE__ << "] " << #v << " = " << v << endl; }
#define dvec(c) { cerr << '[' << __LINE__ << "] " << #c << " = "; for (int i = 0; i < c.size(); ++i) if (i == 0) cerr << '['<<i<<']'<<c[i]; else cerr << " ["<<i<<']'<<c[i]; cerr << endl; } 
#define dmap(m) { cerr << '[' << __LINE__ << "] " << #m << " = "; for (auto it: m) cerr << it.first << "=>" << it.second << ' '; cerr << endl; }
#define dset(s) { cerr << '[' << __LINE__ << "] " << #s << " = "; for (auto item: s) cerr << item << ' '; cerr << endl; }
#else
#define dlog(x)
#define dvar(v)
#define dvec(c)
#define dmap(m)
#define dset(s)
#endif

#define rep(i,n) for (int i = 0; i < int(n); ++i)
#define repr(i,from,to) for (int i = int(from); i <= int(to); ++i)
#define rrep(i,n) for (int i = (n)-1; 0 <= i; --i)
#define rrepr(i,from,to) for (int i = int(from); int(to) <= i; --i)
#define endl '\n'

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 

typedef pair<int, int> P;
typedef pair<LL, LL> LP;
#ifndef F
#define F first
#define S second
#endif 


template<typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  return os << p.F << ':' << p.S;
}


/*
  == AC Library Cheat sheet
  documentation: file:///Users/nobu/Downloads/ac-library/document_ja/index.html

  mint
    mint m.pow(int p)  //! return m^p
    mint m.inv() //! returns i that gives (m * i).val() == 1 
    int m.val() 

  fenwick_tree (BIT)
    fenwick_tree<T> fw(int n) //! init a[0] .. a[n-1] with all 0
    void fw.add(int idx, T x); //! a[idx] += x
    T fw.sum(int l, int r); //! return a[l] + .. + a[r-1]

  dsu (UnionFind)
    dsu d(int n)  //! prepare dsu with n nodes
    void d.merge(int x, int y)  //! connect node x and y
    bool d.same(int x, int y)  //! return true if node x and y are connected
    int d.leader(int x)  //! return the leader node of the connected group
    int d.size(int x) //! return the size of the group that node x belongs to
    vector<vector<int>> d.groups() //! return a vector of vectors that contain the nodes in each group

  scc_graph
    scc_graph g(int n)  //! create a directed graph with n nodes
    g.add_edge(int from, int to)  //! create a directed edge from node from to node to
    vector<vector<int>> g.scc()  //! return the vector of strongly connected components that are topologically sorted

  segtree
    segtree<S, op, e>
      S: type of the monoid 
      op: function to return the product of two elements
      e: function to return the identity element such that op(x, e) == x fo any x 

  lazy_segtree
    lazy_segtree<S, op, e, F, mapping, composition, id>
      F: type of parameters to define the operation applied to the target elements
      mapping: function to return the element after applying the operation to the target element
      composition: function to combine the two sets of operation parameters to one
      id: function to return the operation parameter i such that mapping(i, x) = x for any x

      using S = int;
      S op(S a, S b) { return min(a, b); }
      S e() { return INF; }
      using F = int;
      S mapping(F f, S x) { return min(f, x); }
      F composition(F f, F g) { return min(f, g); }
      F id() { return INF; }

*/

// int dx[] = { 0, -1, 1, 0 };
// int dy[] = { -1, 0, 0, 1 };

// int dx[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
// int dy[] = { -1, -1, -1, 0, 0, 1, 1, 1 };

const int INF = 1e9+1e4;
const LL INFL = 1e18+1e9;
const int MOD = 1000000007;

#define USE_ACL
#ifdef USE_ACL

#include <atcoder/all>
using namespace atcoder;

using mint = static_modint<MOD>;

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < MOD);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

ostream& operator<<(ostream& os, const mint& i) {
  return os << i.val();
}

#endif

int cost(int x)
{
  return x*(x+1)/2;
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << setprecision(20);

  int r, g, b;
  cin >> r >> g >> b;

  int ans = INF;
  rep(gl, g) {
    int tmp = 0;
    int gr = g-gl-1;
    //! gl green mables move to left, gr green marbles move to right
    tmp += cost(gl)+cost(gr);
    if (gl < 100) {
      int rr = min((r-1)/2, 99-gl);
      int rl = r-rr-1;
      tmp += cost(rr)+cost(rl);
    } else {
      //! green mables invade -100
      int offset = gl-100;
      tmp += cost(r+offset)-cost(offset);
    }
    if (gr < 100) {
      int bl = min((b-1)/2, 99-gr);
      int br = b-bl-1;
      tmp += cost(bl)+cost(br);
    } else {
      //! green mables invade 100
      int offset = gr-100;
      tmp += cost(b+offset)-cost(offset);
    }
    chmin(ans, tmp);
  }
  
  cout << ans << endl;

  cout << flush;
  return 0;
}

Submission Info

Submission Time
Task D - マーブル
User nobukichi
Language C++ (GCC 9.2.1)
Score 40
Code Size 5817 Byte
Status WA
Exec Time 9 ms
Memory 3692 KB

Judge Result

Set Name sub1 sub2 All
Score / Max Score 10 / 10 30 / 30 0 / 60
Status
AC × 29
AC × 57
AC × 83
WA × 2
Set Name Test Cases
sub1 sample_01_ABC.txt, test_ABC_01.txt, test_ABC_02.txt, test_ABC_03.txt, test_ABC_04.txt, test_ABC_05.txt, test_ABC_06.txt, test_ABC_07.txt, test_ABC_08.txt, test_ABC_09.txt, test_ABC_10.txt, test_ABC_11.txt, test_ABC_12.txt, test_ABC_13.txt, test_ABC_14.txt, test_ABC_15.txt, test_ABC_16.txt, test_ABC_17.txt, test_ABC_18.txt, test_ABC_19.txt, test_ABC_20.txt, test_ABC_21.txt, test_ABC_22.txt, test_ABC_23.txt, test_ABC_24.txt, test_ABC_25.txt, test_ABC_26.txt, test_ABC_27.txt, test_ABC_28.txt
sub2 sample_01_ABC.txt, sample_02_BC.txt, test_ABC_01.txt, test_ABC_02.txt, test_ABC_03.txt, test_ABC_04.txt, test_ABC_05.txt, test_ABC_06.txt, test_ABC_07.txt, test_ABC_08.txt, test_ABC_09.txt, test_ABC_10.txt, test_ABC_11.txt, test_ABC_12.txt, test_ABC_13.txt, test_ABC_14.txt, test_ABC_15.txt, test_ABC_16.txt, test_ABC_17.txt, test_ABC_18.txt, test_ABC_19.txt, test_ABC_20.txt, test_ABC_21.txt, test_ABC_22.txt, test_ABC_23.txt, test_ABC_24.txt, test_ABC_25.txt, test_ABC_26.txt, test_ABC_27.txt, test_ABC_28.txt, test_BC_29.txt, test_BC_30.txt, test_BC_31.txt, test_BC_32.txt, test_BC_33.txt, test_BC_34.txt, test_BC_35.txt, test_BC_36.txt, test_BC_37.txt, test_BC_38.txt, test_BC_39.txt, test_BC_40.txt, test_BC_41.txt, test_BC_42.txt, test_BC_43.txt, test_BC_44.txt, test_BC_45.txt, test_BC_46.txt, test_BC_47.txt, test_BC_48.txt, test_BC_49.txt, test_BC_50.txt, test_BC_51.txt, test_BC_52.txt, test_BC_53.txt, test_BC_54.txt, test_BC_55.txt
All sample_01_ABC.txt, sample_02_BC.txt, sample_03_C.txt, test_ABC_01.txt, test_ABC_02.txt, test_ABC_03.txt, test_ABC_04.txt, test_ABC_05.txt, test_ABC_06.txt, test_ABC_07.txt, test_ABC_08.txt, test_ABC_09.txt, test_ABC_10.txt, test_ABC_11.txt, test_ABC_12.txt, test_ABC_13.txt, test_ABC_14.txt, test_ABC_15.txt, test_ABC_16.txt, test_ABC_17.txt, test_ABC_18.txt, test_ABC_19.txt, test_ABC_20.txt, test_ABC_21.txt, test_ABC_22.txt, test_ABC_23.txt, test_ABC_24.txt, test_ABC_25.txt, test_ABC_26.txt, test_ABC_27.txt, test_ABC_28.txt, test_BC_29.txt, test_BC_30.txt, test_BC_31.txt, test_BC_32.txt, test_BC_33.txt, test_BC_34.txt, test_BC_35.txt, test_BC_36.txt, test_BC_37.txt, test_BC_38.txt, test_BC_39.txt, test_BC_40.txt, test_BC_41.txt, test_BC_42.txt, test_BC_43.txt, test_BC_44.txt, test_BC_45.txt, test_BC_46.txt, test_BC_47.txt, test_BC_48.txt, test_BC_49.txt, test_BC_50.txt, test_BC_51.txt, test_BC_52.txt, test_BC_53.txt, test_BC_54.txt, test_BC_55.txt, test_C_56.txt, test_C_57.txt, test_C_58.txt, test_C_59.txt, test_C_60.txt, test_C_61.txt, test_C_62.txt, test_C_63.txt, test_C_64.txt, test_C_65.txt, test_C_66.txt, test_C_67.txt, test_C_68.txt, test_C_69.txt, test_C_70.txt, test_C_71.txt, test_C_72.txt, test_C_73.txt, test_C_74.txt, test_C_75.txt, test_C_76.txt, test_C_77.txt, test_C_78.txt, test_C_79.txt, test_C_80.txt, test_C_81.txt, test_C_82.txt
Case Name Status Exec Time Memory
sample_01_ABC.txt AC 9 ms 3628 KB
sample_02_BC.txt AC 2 ms 3624 KB
sample_03_C.txt AC 2 ms 3656 KB
test_ABC_01.txt AC 3 ms 3528 KB
test_ABC_02.txt AC 2 ms 3584 KB
test_ABC_03.txt AC 2 ms 3628 KB
test_ABC_04.txt AC 2 ms 3592 KB
test_ABC_05.txt AC 3 ms 3504 KB
test_ABC_06.txt AC 2 ms 3620 KB
test_ABC_07.txt AC 2 ms 3660 KB
test_ABC_08.txt AC 2 ms 3528 KB
test_ABC_09.txt AC 3 ms 3464 KB
test_ABC_10.txt AC 2 ms 3668 KB
test_ABC_11.txt AC 2 ms 3524 KB
test_ABC_12.txt AC 2 ms 3624 KB
test_ABC_13.txt AC 1 ms 3628 KB
test_ABC_14.txt AC 2 ms 3672 KB
test_ABC_15.txt AC 1 ms 3588 KB
test_ABC_16.txt AC 2 ms 3528 KB
test_ABC_17.txt AC 2 ms 3632 KB
test_ABC_18.txt AC 2 ms 3580 KB
test_ABC_19.txt AC 2 ms 3468 KB
test_ABC_20.txt AC 2 ms 3504 KB
test_ABC_21.txt AC 4 ms 3588 KB
test_ABC_22.txt AC 2 ms 3584 KB
test_ABC_23.txt AC 1 ms 3596 KB
test_ABC_24.txt AC 2 ms 3656 KB
test_ABC_25.txt AC 2 ms 3596 KB
test_ABC_26.txt AC 2 ms 3656 KB
test_ABC_27.txt AC 2 ms 3528 KB
test_ABC_28.txt AC 2 ms 3468 KB
test_BC_29.txt AC 2 ms 3656 KB
test_BC_30.txt AC 2 ms 3656 KB
test_BC_31.txt AC 2 ms 3596 KB
test_BC_32.txt AC 2 ms 3628 KB
test_BC_33.txt AC 2 ms 3624 KB
test_BC_34.txt AC 2 ms 3692 KB
test_BC_35.txt AC 2 ms 3524 KB
test_BC_36.txt AC 2 ms 3632 KB
test_BC_37.txt AC 2 ms 3504 KB
test_BC_38.txt AC 2 ms 3584 KB
test_BC_39.txt AC 2 ms 3508 KB
test_BC_40.txt AC 3 ms 3588 KB
test_BC_41.txt AC 3 ms 3584 KB
test_BC_42.txt AC 3 ms 3524 KB
test_BC_43.txt AC 2 ms 3520 KB
test_BC_44.txt AC 2 ms 3628 KB
test_BC_45.txt AC 2 ms 3620 KB
test_BC_46.txt AC 2 ms 3464 KB
test_BC_47.txt AC 2 ms 3584 KB
test_BC_48.txt AC 2 ms 3596 KB
test_BC_49.txt AC 2 ms 3596 KB
test_BC_50.txt AC 2 ms 3528 KB
test_BC_51.txt AC 2 ms 3560 KB
test_BC_52.txt AC 2 ms 3556 KB
test_BC_53.txt AC 2 ms 3632 KB
test_BC_54.txt AC 2 ms 3632 KB
test_BC_55.txt AC 2 ms 3580 KB
test_C_56.txt AC 2 ms 3528 KB
test_C_57.txt AC 2 ms 3660 KB
test_C_58.txt AC 2 ms 3632 KB
test_C_59.txt AC 3 ms 3668 KB
test_C_60.txt AC 2 ms 3524 KB
test_C_61.txt AC 2 ms 3624 KB
test_C_62.txt AC 2 ms 3508 KB
test_C_63.txt AC 3 ms 3464 KB
test_C_64.txt AC 2 ms 3632 KB
test_C_65.txt AC 2 ms 3584 KB
test_C_66.txt AC 2 ms 3632 KB
test_C_67.txt AC 2 ms 3592 KB
test_C_68.txt AC 2 ms 3624 KB
test_C_69.txt AC 2 ms 3520 KB
test_C_70.txt AC 2 ms 3632 KB
test_C_71.txt AC 2 ms 3624 KB
test_C_72.txt AC 2 ms 3504 KB
test_C_73.txt AC 2 ms 3588 KB
test_C_74.txt AC 2 ms 3580 KB
test_C_75.txt AC 2 ms 3500 KB
test_C_76.txt AC 2 ms 3528 KB
test_C_77.txt AC 2 ms 3524 KB
test_C_78.txt AC 2 ms 3528 KB
test_C_79.txt WA 2 ms 3632 KB
test_C_80.txt AC 2 ms 3580 KB
test_C_81.txt WA 2 ms 3628 KB
test_C_82.txt AC 2 ms 3596 KB