akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define sort(A) sort(A.begin(),A.end())
#define reverse(A) reverse(A.begin(),A.end());

typedef long long ll;

int main(){
  int n;
  cin >> n;
  int INF = pow(10,9);
  vector<int> dp(100005,INF);
  dp[0] = 0;
  for(int i=1;i<=100000;i++){
    int tmp = INF;
    rep(j,10){ //6のj乗と9のj乗を試す
      int cand1 = INF;
      if(i >= pow(6,j)){
        cand1 = dp[i-pow(6,j)] + 1;
      }
      int cand2 = INF;
      if(i >= pow(9,j)){
        cand2 = dp[i-pow(9,j)] + 1;
      }
      int cand3 = min(cand1,cand2);
      tmp = min(tmp,cand3);
    }
    dp[i] = tmp;
  }
  cout << dp[n] << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
#include <ctime>
#include <tuple>
#include <bitset>
using namespace std;

/*
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
        return l.first<r.first || (l.first==r.first && l.second > r.second);
        });
*/

typedef long long  ll;


int main() {
    int n,m;
    cin>>n>>m;
    vector<int>x(m);
    for(int i=0;i<m;i++){
        cin>>x.at(i);
    }
    sort(x.begin(),x.end());
    vector<int>d(m-1);
    for(int i=0;i<m-1;i++){
        d.at(i)=x.at(i+1)-x.at(i);
    }

    sort(d.begin(),d.end());
    int ans=0;
    for(int i=0;i<m-n;i++){
        ans+=d.at(i);
    }
    cout<<ans<<endl;









    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main()
{
    int n;
    vector<int> vec(105);
    
    cin >> n;
    for(int i = 0; i < n; ++i){
      int d;
      cin >> d;
      vec[d] = 1;
    }
    int ans = 0;
    for(int i = 0; i < 105; ++i){
      ans += vec[i];
    }
    cout << ans << endl;
}


Measured memory_bytes: 3532
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
const int INF = 1<<29;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin() , v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)


int main(){
    int N, M, C; cin >> N >> M >> C;
    int B[M];
    int A[N][M];
    rep(i, M) cin >> B[i];
    rep(i, N) rep(j, M) cin >> A[i][j];
    int ans = 0;
    rep(i, N){
        int sum = 0;
        rep(j, M){
            sum += A[i][j] * B[j];
        }
        if(sum + C > 0) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
# C
a,b = map(int, input().split())
if a > b:
    print(-1)
else:
    a_min, a_max, b_min, b_max = 0,0,0,0
    
    if (a*100)%8 == 0:
        a_min = a/0.08
    else:
        a_min = a/0.08 + 1
    a_max = a_min
    while int(a_max*0.08) == a:
        a_max += 1
    a_max -= 1
    
    b_min = b*10
    b_max = b_min
    while int(b_max*0.1) == b:
        b_max += 1
    b_max -= 1
    
    if b_max >= a_min and a_max >= b_min:
        print(int(max(a_min,b_min)))
    else:
        print(-1)

Measured memory_bytes: 38384
#pragma region Macros

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

using ll = long long;
#define int ll
using vi = vector<int>;
using vvi = vector<vi>;

#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

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

// debug methods
// usage: debug(x,y);
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define debug_1(x1) cout << #x1 << ": " << x1 << endl
#define debug_2(x1, x2) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define debug_3(x1, x2, x3) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << endl
#define debug_4(x1, x2, x3, x4) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << endl
#define debug_5(x1, x2, x3, x4, x5) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#ifdef _DEBUG
#define debug(...)                                                        \
    CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) \
    (__VA_ARGS__)
#else
#define debug(...)
#endif

#pragma endregion

void Main() {

    string s;
    cin >> s;
    int ans = 0;
    REP(i, SIZE(s)) {
        if (s[i] == '1') {
            ans++;
        }
    }
    cout << ans;
}

#pragma region main
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Main();
    cout << flush;
}
#pragma endregion


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define RFOR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define LL long long
#define INF INT_MAX/3

const double EPS = 1e-14;
const double PI  = acos(-1.0);


int main(){
  int n, a, b;

  scanf("%d %d %d", &n, &a, &b);

  vector<LL> v(n);
  REP (i, n) {
    scanf("%lld", &v[i]);
  }

  sort(v.begin(), v.end(), greater<LL>());

  LL dp[n + 1][n + 1];
  REP (i, n + 1) {
    dp[i][0] = 1;
    dp[i][i] = 1;
    FOR (j, i + 1, n + 1) {
      dp[i][j] = 0;
    }
  }
  FOR (i, 2, n + 1) {
    FOR (j, 1, n + 1) {
      dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
    }
  }

  bool flag = true;
  LL start = v[0];
  REP (i, a) {
    if (start != v[i]) flag = false;
  }

  LL ans = 0;
  if (flag) {
    int num = count(v.begin(), v.end(), start);
    printf("%.10lld\n", start);
    int t = num < b ? num : b;
    FOR (i, a, t + 1) {
      ans += dp[num][i];
    }
  } else {
    int num = count(v.begin(), v.end(), v[a - 1]);
    printf("%.10lf\n", accumulate(v.begin(), v.begin() + a, 0.0) / a);
    auto first = find(v.begin(), v.end(), v[a - 1]);
    int dist = first - v.begin();
    ans = dp[num][a - dist];
  }

  printf("%lld\n", ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pii;

#define rep(i, n) REP(i, 0, (n))
#define REP(i, a, n) for(int i=(a); i<(n); i++)
#define pb push_back


int main() {
    int n; cin >> n;
    string s; cin >> s;
    
    int b = 0, w = 0;
    vint cnt_b, cnt_w;
    rep(i, n) b += (s[i]=='#'), cnt_b.pb(b);
    rep(i, n) w += (s[n-i-1]=='.'), cnt_w.pb(w);
    reverse(cnt_w.begin(), cnt_w.end());

    int ans = INT_MAX;
    rep(i, n) ans = min(ans, cnt_b[i]+cnt_w[i]-1);

    cout << ans << endl;
}

Measured memory_bytes: 2808
#include <bits/stdc++.h>
using namespace std;
struct node{
  long long w;
  long long v;
};
int main(){
  long long n,W;
  cin>>n>>W;
  node a[n];
  long long sum=0;
  for(long long i=0;i<n;i++){
    cin>>a[i].w>>a[i].v;
    sum+=a[i].v;
  }
  long long b[sum+1];
  long long m=0;
  b[0]=0;
  for(long long i=1;i<=sum;i++){
    b[i]=1000000001;
  }
  for(long long i=0;i<n;i++){
    m+=a[i].v;
    for(long long j=m;j>=a[i].v;j--){
    	if(b[j-a[i].v]+a[i].w<b[j]){
          b[j]=b[j-a[i].v]+a[i].w;
        }
    }
  }
  for(long long j=sum;j>=0;j--){
    	if(b[j]<=W&&b[j]!=0){
          cout<<j<<'\n';
          break;
        }
  }
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
#define ALL(x) x.begin(), x.end()
#define LEN(x) (int)x.size()
#define iostreamBooster() do{ cin.tie(nullptr); ios_base::sync_with_stdio(false); }while(0)
using namespace std;
typedef int64_t i64;
typedef pair<int,int> pii;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr int INF = 0x3f3f3f3f;

constexpr const int N_MAX = 100010;
constexpr const int sqrtN = 512;

int N, K;
int a[N_MAX];
int b[N_MAX / sqrtN + 1];

void build()
{
  for (int i = 1; i <= N; ++i) {
    b[i / sqrtN] = __gcd(b[i / sqrtN], a[i]);
  }
}

int query(int l, int r)
{
  int ret = 0;
  while(l < r && l % sqrtN != 0) ret = __gcd(ret, a[l++]);
  while(l < r && r % sqrtN != 0) ret = __gcd(a[--r], ret);

  for (int i = l/sqrtN; i < r/sqrtN; ++i) {
    ret = __gcd(ret, b[i]);
  }

  return ret;
}

signed main()
{
  iostreamBooster();

  cin >> N;
  K = (N + sqrtN - 1) / sqrtN;

  for (int i = 1; i <= N; ++i) {
    cin >> a[i];
  }

  build();

  int maxv = 0;
  for (int i = 1; i <= N; ++i) {
    chmax(
        maxv,
        __gcd(query(1, i), query(i+1, N+1))
    );
  }

  cout << maxv << endl;


  return 0;
}



Measured memory_bytes: 640
def knapsack_DP(N, W, weight, value):
    import numpy as np
    dishes = [(weight[i], value[i]) for i in range(N)]
    dishes = sorted(dishes, key=lambda x: x[0])
    dp = np.zeros(W, dtype=int)
    ans=0
    for w, v in dishes:
        ans=max(dp[-1]+v, ans)
        np.maximum(dp[:-w] + v, dp[w:], out=dp[w:]) 
    return ans

if __name__=="__main__":
    N, W = map(int, input().split())
    weight = []
    value = []
    for i in range(N):
        w, v= map(int, input().split())
        weight.append(w)
        value.append(v)
    print(knapsack_DP(N, W, weight, value))

Measured memory_bytes: 12628
s1 = input()
s2 = input()

n1 = len(s1)
n2 = len(s2)

inf = float('inf')

def cost(j, i):
    return 0 if s1[i] == s2[j] else 1

# D[j][i] == the distance between s1[:i] and s2[:j]
D = [[inf for i in range(n1 + 1)] for j in range(n2 + 1)]

for i in range(n1 + 1):
    D[0][i] = i
for j in range(n2 + 1):
    D[j][0] = j

for j in range(1, n2 + 1):
    for i in range(1, n1 + 1):
        D[j][i] = min(D[j][i-1] + 1, D[j-1][i] + 1,
                      D[j-1][i-1] + cost(j-1, i-1))

print(D[n2][n1])



Measured memory_bytes: 44032
#include<bits/stdc++.h>
using namespace std;
using ll = long long;


#define debug(x) cout << #x << " = " << x << endl;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define FOR(it, b, e) for (typeof(b) it = (b); it != (e); ++it)
#define MSET(c, v) memset(c, v, sizeof(c))

const int INF = 0x3F3F3F3F; 
const int NEGINF = 0xC0C0C0C0;
const int NULO = -1;
const double EPS = 1e-10;
const ll mod = 1e9 + 7;

inline int cmp(double x, double y = 0) 
{  
  if(fabs(x - y) < EPS)
    return 0;
  return x > y ? 1 : -1;
}

ll exp(ll a, ll b)
{
  ll ans = 1;
  while(b)
  {
    if(b & 1)
      ans = (ans * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return ans;
}

const int maxn = 2e5 + 10;
ll fat[maxn], inv[maxn];

ll C(int n, int k)
{
  if(n < k) 
    return 0;
  if(n < 0 || k < 0) 
    return 0;
  return (((fat[n] * inv[k]) % mod) * inv[n - k]) % mod;
}

void initFactorials()
{
  fat[0] = 1;
  inv[0] = 1;
  for(int i = 1; i < maxn; i++)
  {
    fat[i] = (i * fat[i-1]) % mod;
    inv[i] = exp(fat[i], mod - 2);
  }
}

ll a[maxn];

int qt[20];


template <typename T = int>
class Convolution {
  using C = complex<double>;
  const C ZERO = C(0.0, 0.0);
  vector<T> conv;
 
  vector<C> dft(const vector<C>& x) {
    int n = x.size();
 
    if (n == 1) return x;
 
    assert(n % 2 == 0);
 
    vector<C> even(n / 2), odd(n / 2);
    for (int i = 0; i < n / 2; ++i) {
      even[i] = x[2 * i];
      odd[i] = x[2 * i + 1];
    }
 
    vector<C> q = dft(even), r = dft(odd);
    vector<C> y(n);
    for (int i = 0; i < n / 2; ++i) {
      double ith = -2.0 * i * M_PI / n;
      C wi(cos(ith), sin(ith));
      y[i] = q[i] + wi * r[i];
      y[i + n / 2] = q[i] - wi * r[i];
    }
 
    return y;
  }
 
  vector<C> inverseDft(const vector<C>& x) {
    int n = x.size();
    vector<C> y(n);
    for (int i = 0; i < n; ++i) {
      y[i] = conj(x[i]);
    }
 
    y = dft(y);
 
    for (int i = 0; i < n; ++i) {
      y[i] = conj(y[i]);
      y[i] /= n;
    }
 
    return y;
  }
 
 public:
  Convolution(const vector<T>& a, const vector<T>& b) {
    int n = a.size(), m = b.size();
    int l = 1;
    while (n + m >= l) l *= 2;
 
    vector<C> ca(l, ZERO), cb(l, ZERO);
    for (int i = 0; i < n; ++i) ca[i] = C(a[i], 0.0);
    for (int i = 0; i < m; ++i) cb[i] = C(b[i], 0.0);
 
    vector<C> fa = dft(ca), fb = dft(cb);
    vector<C> fc(l);
    for (int i = 0; i < l; ++i) {
      fc[i] = fa[i] * fb[i];
    }
 
    vector<C> c = inverseDft(fc);
    conv.resize(l);
    for (int i = 0; i < l; ++i) {
      conv[i] = round(c[i].real());
    }
  }
 
  T operator[](int i) { return conv[i]; }
 
  vector<T> toVector() { return conv; }
};

int main()
{
  ios::sync_with_stdio(0);
  int n;
  ll m;
  cin >> n >> m;
  vector<ll>freq(maxn, 0);
  for(int i = 0; i < n ; i++)
  {
    int x;
    cin >> x;
    freq[x]++;
  }

  Convolution<ll> conv(freq, freq);

  ll ans = 0;

  for(int i = maxn - 1; i >= 0 && m > 0; i--)
  {
    auto c = min(m, conv[i]);
    ans += i * c;
    m -= c;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 89476
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<ll,ll> P;

void Main() {
  ll n;
  R n;
  ll a[n];
  rep(i,n) R a[i];
  ll dp[n][2];
  rep(i,n)rep(j,2) dp[i][j]=-MAXL;
  dp[0][0]=0;
  rep(i,n) {
    rep(j,2) {
      dp[i+1][0]=max(dp[i+1][0],dp[i][j]+a[i]*(j?-1:1));
      dp[i+1][1]=max(dp[i+1][1],dp[i][j]+a[i]*((j+1)%2?-1:1));
    }
  }
  dp[n-1][0]+=a[n-1];
  dp[n-1][1]-=a[n-1];
  pr(max(dp[n-1][0],dp[n-1][1]));
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 2560
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

func primeFactor(n int) map[int]int {
	m := map[int]int{}
	for i := 2; i*i <= n; i++ {
		for n%i == 0 {
			m[i]++
			n /= i
		}
	}
	if n != 1 {
		m[n] = 1
	}
	return m
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	n := nextInt()
	a := nextInts(n)
	sort.Sort(sort.IntSlice(a))

	if n == 1 {
		puts(1)
		return
	}

	ans := 0
	if 1 < n && a[0] != a[1] {
		ans = 1
	}

	ok := make([]bool, a[n-1]+1)
	for i := range ok {
		ok[i] = true
	}
	for j := 1; a[0]*j <= a[n-1]; j++ {
		ok[a[0]*j] = false
	}
	for i := 1; i < n; i++ {
		if !ok[a[i]] {
			continue
		}
		if !(i < n-1 && a[i] == a[i+1]) && !(i > 0 && a[i] == a[i-1]) {
			ans++
		}
		for j := 1; a[i]*j <= a[n-1]; j++ {
			ok[a[i]*j] = false
		}
	}

	puts(ans)
}


Measured memory_bytes: 6248
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, q = map(int, input().split())

tree = [[] for _ in range(n)]

for i in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

add = [0] * n

for i in range(q):
    p, x = map(int, input().split())
    add[p-1] += x

ans = [0] * n

def dfs(v, p, value):
    value += add[v]
    ans[v] = value
    for c in tree[v]:
        if c == p:
            continue
        dfs(c, v, value)

dfs(0, -1, 0)

print(*ans)

Measured memory_bytes: 237004
#%%
a = input()
#b = "2 3 1"
#%%
A = [int(x) for x in a.split()]

import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

import fractions
gcb = fractions.gcd(A[0], A[1])  # 最大公約数

#%%
def prime_factorize(n):
    a = [1]
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

so_gcb = prime_factorize(gcb)


#%%
new_num = []
for num in so_gcb:
    if num not in new_num:
        new_num.append(num)

print(len(new_num))

Measured memory_bytes: 5172
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	string s;
	scan(s);
	if(s[0]=='A') prin("T");
	if(s[0]=='T') prin("A");
	if(s[0]=='G') prin("C");
	if(s[0]=='C') prin("G");
	return 0;
}


Measured memory_bytes: 256
n=int(input())
ans=0
count=[[0 for _ in range(10)] for _ in range(10)]
for i in range(1,n+1):
    stri=str(i)
    count[int(stri[0])][int(stri[-1])]+=1

for i in range(10):
    for j in range(i,10):
        if(i==j):
            ans+=count[i][j]*count[j][i]
        else:
            ans+=2*(count[i][j]*count[j][i])

print(ans)


Measured memory_bytes: 9212
#import <stdio.h>
#import <limits.h>
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

long CEIL(double x) {
    long i = (long)x;
    return i + (((x != i) && (x > 0)) ? 1 : 0);
}

int main(int argc, const char * argv[]) {
    long N, K;
    scanf("%ld %ld", &N, &K);
    
    long n;
    long i = 0;
    while (scanf("%ld", &n) != EOF) {
        if (n==1) {
            break;
        }
        i++;
    }
    
    long min = LONG_MAX;
    for(long j=MAX(0,-N+K+i); j<=MIN(K-1,i); j++){
        min = MIN(min, 1 + CEIL((double)(i-j)/(K-1)) + CEIL((double)(N-i-K+j)/(K-1)) );
    }
    
    printf("%ld", min);
}


Measured memory_bytes: 7628
#include<bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using ull = unsigned long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vs = vector<string>;
using vvs = vector<vs>;
using vc = vector<char>;
using vvc = vector<vc>;
using ii = pair<int,int>;
using vii = vector<ii>;
using vvii = vector<vii>;
using dd = pair<double, double>;
using vdd = vector<dd>;
using vvdd = vector<vdd>;
using Mii = map<int,int>;
using vMii = vector<Mii>;

#define fi first
#define se second
#define INF INT_MAX
#define mod(a,m) (a%m+m)%m
#define PB push_back
#define MP make_pair

int n;
vvvd memo;

double dp(int a, int b, int c) {
	if(a < 0 or b < 0 or c < 0) return 0.0; // these cases do not have any influence
	double& ans = memo[a][b][c];
	if(fabs(ans + 1) > 1e-9) return ans; // ans != -1
	if(not a and not b and not c) return ans = 0.0;
	return ans = (a * dp(a-1, b, c) + b * dp(a+1, b-1, c) + c * dp(a, b+1, c-1) + n) / (a + b + c);
}

int main(){
//	cout.setf(ios::fixed);
//	cout.precision(4);
	while (cin >> n) {
		vi v(3, 0);
		for (int i = 0; i < n; ++i) {
			int a;
			cin >> a;
			v[a-1]++;
		}
		memo = vvvd(n+1, vvd(n+1, vd(n+1, -1.0)));
		cout << fixed;
		cout << setprecision(15);
		cout << dp(v[0], v[1], v[2]) << '\n';
	}
}



Measured memory_bytes: 216960
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pii pair<int,int> 
#define pb push_back
#define INF INT_MAX 
#define mod 1000000007ll
#define fi first
#define se second
#define f(i,p,q) for(int i=p;i<q;i++)
#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define psi(a) printf(" %d",a)
#define poi(a) printf("%d",a)
#define sl(a) scanf("%lld",&a)
#define pl(a) printf("%lld\n",a)
#define Nline() printf("\n")
#define sstr(str) scanf("%s",str)
#define pstr(str) printf("%s\n",str)
#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define vi vector<int>
#define vvi vector<vi>
#define all(v) (v).begin(),(v).end()
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())
#define VI(a,n) vi a(n); rep(i,n)cin>>a[i];
#define sq(n) (n)*(n)
#define iso ios::sync_with_stdio(false); cin.tie(0);cout.tie(NULL);
#define cases int t;cin>>t;while(t--)
int main()
{
    iso;
    ll n;cin>>n;
  ll ans=LONG_MAX;
    for(ll i=1;i*i<=n;i++)
    {   if(n%i==0)
        ans=min(i-1+n/i-1,ans);
    }
    cout<<ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void program(); int main() {cin.sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit); program();}
#define int long long
#define endl "\n"
#define all(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pii pair<int,int>

#define N 3000
int n;
int a[N], dp[N][N];
int v(int, int);

int u(int i, int j){
    if(dp[i][j] != -1) return dp[i][j];
    if(i == j){
        return a[i];
    }
    return dp[i][j] = max(a[i]+v(i+1,j),a[j]+v(i,j-1));
}

int v(int i, int j){
    if(dp[i][j] != -1) return dp[i][j];
    if(i == j){
        return -a[i];
    }
    return dp[i][j] = min(-a[i]+u(i+1,j),-a[j]+u(i,j-1));
}

void program(){
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) dp[i][j] = -1;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    cout<<u(0,n-1)<<endl;
}

/*
WA:
-bounds on loops
-truncating
-intialization
-0 vs 1 indexing

TLE:
-might need unordered_set/map
-infinite while loop

Stuck:
-different perspective?
-bruteforce?
-greedy?
-reduce dimensionality with problem contraints?
*/


Measured memory_bytes: 70656
#include <bits/stdc++.h>
using namespace std;

// Type alias
using ll=long long;
using ld=double;

using pi=pair<int,int>;
using pll=pair<ll,ll>;
using pld=pair<ld,ld>;
using ti3=tuple<int, int, int>;

using vi=vector<int>;
using vll=vector<ll>;
using vld=vector<ld>;
using vpi=vector<pi>;
using vpll=vector<ll>;
using vpld=vector<ld>;
using vti3=vector<ti3>;

// Constants
const double EPS = 1e-9;
const int inf = numeric_limits<int>::max() / 2;
const ll mod = 1e9+7;

// Macro
#define rep(i,n) for(int i=0;i<int(n);++i)
#define rrep(i,n) for(int i=int(n-1);i>=0;--i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define RREP(i,a,b) for(int i=int(b-1);i>=int(a);--i)
#define SHOW(a) cout << #a << " = " << a << endl
#define ARR(a,n) for(int i=0;i<int(n);++i) cout << #a << "[" << i << "]" << " = " << a[i] << endl

#define ALL(a) a.begin(),a.end()

// Funtcions
ll pow(ll base, ll i, ll mod){
  ll a = 1;
  while(i){
    if (i & 1) {
      a *= base;
      a %= mod;
    }
    base *= base;
    base %= mod;
    i >>= 1;
  }
  return a;
}
ll gcd(ll a, ll b){
  while(b){
    ll c = a % b;
    a = b;
    b = c;
  }
  return a;
}
ll lcm(ll a, ll b){
  return a / gcd(a, b) * b;
}
template<typename T> bool chmin(T& a, const T& b) {
  if (a > b) return a = b, true; else return false;
}

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

ll dp[105][100005];
void solve(){
  ll N, W;
  cin >> N >> W;

  vector<pll> g;
  rep(i, N){
    int a, b;
    cin >> a >> b;
    g.emplace_back(make_pair(a, b));
  }

  rep(i, W+1) dp[0][i] = 0;

  rep(i, N){
    rep(j, W+1){
      if(j < g[i].first)
        dp[i+1][j] = dp[i][j];
      else
        dp[i+1][j] = max(dp[i][j], dp[i][j - g[i].first] + g[i].second);
    }
  }

  cout << dp[N][W] << endl;
}

int main(){
// FastIO
//ios_base::sync_with_stdio(false);
cin.tie(NULL);
  solve();
  return 0;
}

Measured memory_bytes: 80256
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
S = str(input())

if N%2!=0:
    print('No')
else:
    if S[:N//2]==S[N//2:]:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 38256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define debug(x) cout<<#x<<": "<<x<<endl
#define DEBUG(x) cout<<#x<<": "<<x<<endl
int powint(int a, int x){
	int res = 1;
	REP(i,x){
		res = res *a; 
	}
	return res;
}

using namespace std;

int main(){
	string S;
	cin>>S;
	
	if(S.find("AC") != std::string::npos){
		cout<<"Yes"<<endl;		
	} else {
		cout<<"No"<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
(println
  (reduce + (let [v   (->> (clojure.string/split (read-line) #"\s")
                           (map #(Integer/parseInt %))
                           (sort)
                           (reverse))
                  dup (conj (rest v) (last v))]
              (map (fn [i j] (- i j)) v dup))))

Measured memory_bytes: 82152
def solve(n, s, d, MOD):
    ttt = [ord(c) - 97 for c in s]

    ttx = []
    c = 1
    for t in ttt[::-1]:
        ttx.append(t * c % MOD)
        c = c * d % MOD
    ttx.reverse()
    ttc = [0]
    for t in ttx:
        ttc.append((ttc[-1] + t) % MOD)

    l, r = 0, n // 2 + 1
    while l < r:
        m = (l + r + 1) // 2
        if search(m, d, ttc, MOD):
            l = m
        else:
            r = m - 1

    return l


def search(w, d, ttc, MOD):
    appeared = []
    comparing = set()
    w2 = w * 2
    p = 1

    for i in range(w, n + 1):
        t = (ttc[i] - ttc[i - w]) * p % MOD
        if i >= w2:
            comparing.add(appeared[i - w2])
            if t in comparing:
                return True
        appeared.append(t)
        p = p * d % MOD

    return False


n = int(input())
s = input()
MOD = 10 ** 9 + 7
print(min(solve(n, s, d, MOD) for d in (29, 31)))


Measured memory_bytes: 3904
#include <iostream>
#include <cstdio>
#include <string>
 
//#define PI 3.141592653589
 
using namespace std;
 
 
 
int main()
{
    int n;
    string indication[10000];
     
    while (1)
    {
        cin >> n;
        if (n == 0) break;
        for (int i=0; i<n; i++)
        {
            cin >> indication[i];
        }
        /*
        for (int i=0; i<n; i++)
        {
            //cin >> indication[i];
            cout << indication[i];
        }
        */
         
        int dice[6] = {1, 2, 3, 5, 4, 6};
        int temp;
         
        int sum = 1;
        for (int i=0; i<n; i++)
        {
            if (indication[i] == "North")
            {
                temp = dice[0];
                dice[0] = dice[1];
                dice[1] = dice[5];
                dice[5] = dice[3];
                dice[3] = temp;
            } else if (indication[i] == "East") {
                temp = dice[0];
                dice[0] = dice[4];
                dice[4] = dice[5];
                dice[5] = dice[2];
                dice[2] = temp;
            } else if (indication[i] == "West") {
                temp = dice[0];
                dice[0] = dice[2];
                dice[2] = dice[5];
                dice[5] = dice[4];
                dice[4] = temp;
            } else if (indication[i] == "South") {
                temp = dice[0];
                dice[0] = dice[3];
                dice[3] = dice[5];
                dice[5] = dice[1];
                dice[1] = temp;
            } else if (indication[i] == "Right") {
                temp = dice[1];
                dice[1] = dice[2];
                dice[2] = dice[3];
                dice[3] = dice[4];
                dice[4] = temp;
            } else if (indication[i] == "Left") {
                temp = dice[1];
                dice[1] = dice[4];
                dice[4] = dice[3];
                dice[3] = dice[2];
                dice[2] = temp;
            }
            sum += dice[0];
            //cout << "sum = " << sum << endl;
        }
         
        //cout << "sum = " << sum << endl;
        cout << sum << endl;
    }
     
    return 0;
}

Measured memory_bytes: 3424
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int n,m,a[N],l[25][N],r[25][N],v[25],cnt=0,L[1<<25],R[1<<25],ans[N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	int V=m;
	while(V){V>>=1;v[cnt++]=V;}v[cnt]=m;
//	for(int i=1;i<=cnt;i++) printf("%d ",v[i]);
	for(int i=0;i<=cnt;i++)
	{
		l[i][1]=1;
		r[i][n]=n;
		for(int j=2;j<=n;j++) l[i][j]=(a[j]-a[j-1]<=v[i])?l[i][j-1]:j;
		for(int j=n-1;j>=1;j--) r[i][j]=(a[j+1]-a[j]<=v[i])?r[i][j+1]:j;
	}
	/*for(int i=0;i<=cnt;i++)
	{
		for(int j=1;j<=n;j++) printf("%d ",l[i][j]);
		printf("\n");
	}*/
//	L[0]=1,R[0]=n;
	for(int i=0;i<(1<<cnt);i++) R[i]=n+1;
	for(int i=0;i<(1<<cnt);i++)
		for(int j=0;j<=cnt;j++)
			if(((1<<j)&i)==0)
				L[(1<<j)|i]=max(L[(1<<j)|i],r[j][L[i]+1]),
				R[(1<<j)|i]=min(R[(1<<j)|i],l[j][R[i]-1]);
//	for(int i=0;i<(1<<cnt);i++) printf("%d %d\n",L[i],R[i]);
	/*for(int i=0;i<(1<<cnt);i++)
	{
		printf("!! %d %d\n",i,((1<<cnt)-1)^i);
		if(L[i]>=R[((1<<cnt)-1)^i]) s[R[((1<<cnt)-1)^i]]++,s[L[i]+1]--,printf("%d %d\n",R[((1<<cnt)-1)^i],L[i]);
	}
	int sum=0;
	for(int i=1;i<=n;i++) 
	{
		sum+=s[i];
		if(sum>0) puts("Possible");
		else puts("Impossible");
	}*/ 
	for(int i=1;i<=n;i++)
	{
		bool flag=0;
		for(int j=0;j<(1<<cnt);j++)
		{
			int ss=((1<<cnt)-1)^j;
			if(L[j]>=i-1&&R[ss]<=r[cnt][i]+1){flag=1;break;}
		}
		for(int j=i;j<=r[cnt][i];j++)
		{
			if(flag) ans[j]=1;
			else ans[j]=0;
		}
		i=r[cnt][i];
	}
	for(int i=1;i<=n;i++) puts(ans[i]==0?"Impossible":"Possible");
	return 0;
}

Measured memory_bytes: 37948
#include<iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    bool bRes = false;
    for(int i=0;i<= 100/4;i++)
    {
        for(int j=0;j<=100/7;j++)   
        {
            if((4*i+7*j) == n)
            {
                bRes = true;
            }
        }
    }
    if(bRes)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0 ; i < (n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using namespace std;
using p = pair<int, int>;

int main()
{
    int n,m,sum=0;
    vector<int> a(10000);

    cin >> n >> m;
    rep(i, m) {
        cin >> a.at(i);
        sum += a.at(i);
    }

    if (sum > n)
        cout << -1;
    else
        cout << n - sum;

    return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e5 + 10 ;

int arr[MAX] ;
int n ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	for(int i = 1 ; i <= 5 ; ++i)
		cin>>arr[i] ;
	for(int i = 1 ; i <= 5 ; ++i)
	{
		if(!arr[i])
			return cout<<i<<"\n" , 0 ;
	}
	return 0 ;
}		

Measured memory_bytes: 3648
#include <iostream>
#include <cstdint>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

int main(void)
{
    int64_t n;
    std::string s;
    std::cin >> n >> s;

    int64_t red = 0;
    int64_t blue = 0;
    for (auto& c : s) {
        if (c == 'R') red++;
        else blue++;
    }

    std::cout << ((red > blue) ? "Yes" : "No") << std::endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>

#define MAX_N 100'000

typedef long long ll;

using namespace std;

int A[MAX_N];
int B[MAX_N];

int main() {
  int N;
  cin >> N;
  for (int i = 0; i < N; ++i) {
    cin >> A[i] >> B[i];
  }
  ll res = 0;
  for (int i = N - 1; i >= 0; --i) {
    res += (B[i] - (A[i] + res) % B[i]) % B[i];
  }
  printf("%lld\n", res);
}

Measured memory_bytes: 3964
/*input
1
1

*/
 
/*
                                                    ______________
                                                          |       )
                                                          |   )   /
                                                          |______/
                                                    |     |      \
                                                    |     |   )   \
                                                    |_____|_______)
 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <iomanip>
#include <fstream>
#include <stack>

using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll , ll> PLL;
typedef long double ld;
 
#define pb push_back
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
int mod = 1000000007;
const int inf = 1034567891;
const ll LL_INF = 1234567890123456789ll;
#define PI 3.14159265
#define endl '\n'
#define F first
#define S second
#define debug(x) cout << #x << " = " << x << endl;
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
#define out(container) for (auto it : container) cout << it << " "; cout << endl;
 
 
template < typename T > T GCD(T a, T b)            { ll t; while(a) { t = a; a = b % a; b = t; } return b; }
template < typename T > string toString(T a)       { return to_string(a); }
template < typename T > void toInt(string s, T &x) { stringstream str(s); str >> x;}
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % mod;}
inline int powr(int a, ll b){
  int x = 1 % mod;
  while(b){
    if(b & 1) x = mul(x, a);
    a = mul(a, a);
    b >>= 1;
  }
  return x;
}
inline int inv(int a){ return powr(a, mod - 2);}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  ll n, m;
  cin >> n >> m;
  ll ans = n * (n - 1) / 2;
  ans += m * (m - 1) / 2;
  cout << ans << endl;  

  return 0;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [0 for _ in range(N)]

for i in range(1,N): #0 <= i < N
    dp[i] = min([dp[i-k] + abs(H[i]-H[i-k]) for k in range(1, min(i, K)+1)])

print(dp[-1])

Measured memory_bytes: 56672
# -*- coding: utf-8 -*-
N, M, Q = map(int, input().split())
ABCD = [list(map(int, input().split())) for _ in range(Q)]

# V[k] : 長さkである単調増加数列たち
V = [[] for _ in range(N+1)]

# 初期値として長さ1のものを入れる
for i in range(1, M+1):
    V[1].append([i])

# V[k] から V[k+1] を作る
for i in range(1, N):
    for v in V[i]:
        # 単調増加なので、末尾の値以上であるものを全て試す
        b = v[-1]
        for a in range(b, M+1):
            v2 = v + [a]
            V[i+1].append(v2)

ans = 0
for v in V[N]:
    res = 0
    for a, b, c, d in ABCD:
        if v[b-1] - v[a-1] == c:
            res += d
    ans = max(ans, res)

print(ans)

Measured memory_bytes: 36236
#include <iostream>
#include <vector>
#include <algorithm>
#include <complex>
#include <string>
#include <cmath>
using namespace std;

int main(void){
	
	int a,b; cin >> a >> b;
	if(a+b>=10){
		cout << "error" << endl;
	}else{
		cout << a+b << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;(i)--)
#define rrep1(i,n) for(int i=((int)(n));i>0;(i)--)
#define sz(c) ((int)(c).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> P;
typedef pair<int, pair<int, int> > PP;
const int MAX=1e3+10;


int N;
vi w,s;
vll v;
int S, W;

void input(){
    cin>>N;
    vi tw(N), ts(N);
    vll tv(N);
    rep(i,N){
        cin>>tw[i]>>ts[i]>>tv[i];
        S=max(S, ts[i]);
        W=max(W, tw[i]);
    }

    vector<P> seq(N);
    rep(i,N)seq[i]=mp(tw[i]+ts[i], i);
    sort(all(seq));
    rep(i,N){
        int ind=seq[i].se;
        w.pb(tw[ind]);
        s.pb(ts[ind]);
        v.pb(tv[ind]);
    }
}

ll dp[1010][20010];
ll ans;
void solve(){
    rep(i,N+1)rep(we,S+W+1)dp[i][we]=-1;
    dp[0][0]=0;
    rep(i,N)rep(we, S+W+1)if(dp[i][we]!=-1){
        dp[i+1][we]=max(dp[i+1][we], dp[i][we]);
        if(we<=s[i]) dp[i+1][we+w[i]]=max(dp[i+1][we+w[i]], dp[i][we]+v[i]);
    }
    rep(we,S+W+1)ans=max(ans, dp[N][we]);
}

void output(){
    cout<<ans;
}

int main(){
  input();
  solve();
  output();
}


Measured memory_bytes: 157952
# D not completed
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
P_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))

checked_list = [0 for _ in range(N)]
min_INF = -1 * 10 ** 10
max_score = min_INF
for i in range(N):
    if checked_list[i] == 1:
        continue
    posit = i
    loop_list = [posit]
    score_list = []
    for j in range(N):
        posit = P_list[posit] - 1
        if j == 0:
            score_list.append(C_list[posit])
        else:
            score_list.append(score_list[-1] + C_list[posit])
        if posit in loop_list:
            break
        loop_list.append(posit)

    len_loop = len(loop_list)
    max_score_list = max(score_list)
    around_score = score_list[-1]
    temp_score_base = 0
    if around_score > 0 and K // len_loop > 0:
        temp_score_base += (K // len_loop - 1) * around_score
    for k in range(len_loop):
        # print("loop", loop_list)
        # print("score", score_list)
        checked_list[loop_list[k]] = 1
        temp_max_score = temp_score_base
        rest_score = min_INF
        if around_score > 0 and K // len_loop > 0:
            # 最後に1周すべきか
            rest_score = max(max_score_list, max(score_list[:K % len_loop], default=min_INF) + around_score)
            # print(loop_list[k], temp_max_score, K, len_loop, K // len_loop)
        rest_score = max(max(score_list[:min(K, len_loop)]), rest_score)
        temp_max_score = temp_max_score + rest_score
        # print(loop_list[k], temp_max_score, rest_score)
        max_score = max(max_score, temp_max_score)
        # ループ内でずらす
        now_score = score_list.pop(0)
        len_score = len(score_list)
        score_list = [score_list[l] - now_score for l in range(len_score)]
        score_list.append(score_list[-1] + now_score)

print(max_score)

Measured memory_bytes: 10576
#include <bits/stdc++.h>
using namespace std;

//#define int long long
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

/* cpp template {{{ */

/* short */
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define X real()
#define Y imag()

/* REPmacro */
#define REPS(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define rep(i, n) REPS(i, 0, n)
#define REP0(i,n) for (ll i = 0; i <= (ll)(n); ++i)
#define REP1(i,n) for (ll i = 1; i <= (ll)(n); ++i)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (ll i = (a); i >= (ll)(n); --i)
#define DEP(i, n) DEPS(i, n, 0)
#define EACH(i, n) for (auto&& i : n)

/* debug */
#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

/* alias */
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using D = double;
using P = complex<D>;
using vs = vector<string>;
template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

/* const */
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;
const D EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

/* func */
inline bool inside(int y, int x, int H, int W) {return y >= 0 && x >= 0 && y < H && x < W;}
inline int in() {int x; cin >> x; return x;}
inline ll IN() {ll x; cin >> x; return x;}
inline vs split(const string& t, char c) {vs v; stringstream s(t); string b; while(getline(s, b, c)) v.eb(b); return v;}
template <typename T> inline bool chmin(T& a, const T& b) {if (a > b) a = b; return a > b;}
template <typename T> inline bool chmax(T& a, const T& b) {if (a < b) a = b; return a < b;}
template <typename T, typename S> inline void print(const pair<T, S>& p) {cout << p.first << " " << p.second << endl;}
template <typename T> inline void print(const T& x) {cout << x << '\n';}
template <typename T, typename S> inline void print(const vector<pair<T, S>>& v) {for (auto&& p : v) print(p);}
template <typename T> inline void print(const vector<T>& v, string s = " ") {rep(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");}
/* }}} */

signed main() 
{
    string s;
    cin >> s;
    bool flag=true;
    string div[4]={"dream","dreamer","erase","eraser"};
    rep(i,4) reverse(ALL(div[i]));
    reverse(ALL(s));
    ll i=0;
    while(i<s.size())
    {
        bool can=false;
        rep(j,4)
        {
            if(s.substr(i,div[j].size())==div[j])
            {
                can=true;
                i+=div[j].size();
            }
        }
        if(!can)
        {
            flag=false;
            break;
        }
    }
    flag? print("YES") : print("NO");
    
    return 0;
}

Measured memory_bytes: 512
N,M =map(int,input().split())
List=[[int(j) for j in input().split()] for i in range(N)]
List = sorted(List)

M_res = 0
M_res +=M

ANS = 0

while M_res > 0:
    for i in range(len(List)):
        if M_res <= List[i][1]:
            ANS +=  List[i][0] * M_res
            M_res -=M_res
        else:
            ANS += List[i][0] * List[i][1]
            M_res -=List[i][1]
        if M_res ==0:
            break
print(ANS)

Measured memory_bytes: 22376
import java.util.*;

public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        long n = Long.parseLong(sc.next());
        long a = Long.parseLong(sc.next());
        long b = Long.parseLong(sc.next());
        
        long ans = Math.min(a+(b-a)/2, n-b+1+(b-a)/2);
        if((b-a)%2==0){
            ans = (b-a)/2;
        }
        
        System.out.println(ans);
    }
}


Measured memory_bytes: 22996
n = int(input())
dic = {}
cnt = 0

for i in range(n) :
    s = input()
    if s[0] == "M" or s[0] == "A" or s[0] == "R" or s[0] == "C" or s[0] == "H" :
        if s[0] in dic :
            dic[s[0]] += 1
        else:
            dic[s[0]] = 1

lis = [x for x in dic.values()]

for j in range(len(lis) - 2) :
    for k in range(j + 1, len(lis) - 1) :
        for l in range(k + 1, len(lis)) :
            
            cnt += lis[j] * lis[k] * lis[l]
    
print(cnt)

Measured memory_bytes: 74944
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;
 
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
 
const ll INF=1e9+7;

ll f[100][10];
ll p[100][11];

int main(){
    ll n;
    cin >> n;
    rep(i,n){
        rep(j,10){
            cin >> f[i][j];
        }
    }
    rep(i,n){
        rep(j,11){
            cin >> p[i][j];
        }
    }
    ll ans=-INF;
    for(ll i=1;i<(1<<10);i++){
        ll sum=0;
        rep(j,n){
            ll cnt=0;
            rep(k,10){
                if((i>>k)%2==1 && f[j][k]==1) cnt++;
            }
            sum+=p[j][cnt];
        }
        ans=max(ans,sum);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

S=input()
N=len(S)

A=[]
ecnt=1
ocnt=idx=0
for i in range(1, N):
    if S[i-1]==S[i]=='R' or S[i-1]==S[i]=='L':
        if i%2==0:
            ecnt+=1
        else:
            ocnt+=1
    elif S[i-1]=='R' and S[i]=='L':
        idx=i
        if i%2==0:
            ecnt+=1
        else:
            ocnt+=1
    elif S[i-1]=='L' and S[i]=='R':
        A.append((ecnt, ocnt, idx))
        if i%2==0:
            ecnt=1
            ocnt=0
        else:
            ocnt=1
            ecnt=0
        idx=0
else:
    A.append((ecnt, ocnt, idx))

ans=[0]*N
for a in A:
    ecnt,ocnt,idx=a
    if idx%2==0:
        ans[idx]=ecnt
        ans[idx-1]=ocnt
    else:
        ans[idx]=ocnt
        ans[idx-1]=ecnt
print(*ans)


Measured memory_bytes: 11876
# https://atcoder.jp/contests/abc080/tasks/abc080_d
# D - Recording

N,C = map(int,input().split())
s=[0]*N
t=[0]*N
c=[0]*N
f=[False]*C
yoyaku=[False]*C
L=[]
for i in range(N):
    s[i],t[i],c[i]= map(int,input().split())
    L.append( [s[i]-0.5,c[i]-1,1] )
    L.append( [t[i],c[i]-1,0] )

L.sort()
#print(L)
ans=0
tmp=0

for i,(time, ch, sw) in enumerate(L):
    if sw==1:
        if f[ch]==False:
            tmp +=1
            f[ch]=True
            ans = max(ans,tmp)
        else:
            yoyaku[ch]=True
    else:
        if yoyaku[ch]:
            yoyaku[ch]=False
        else:
            tmp -= 1
            f[ch]=False
   
print(ans)


Measured memory_bytes: 42196
#include<bits/stdc++.h>

#define FOR(i, a, b) for(int(i)=(a);(i)<(b);(i)++)
#define REP(i, n) FOR((i), 0, (n))

#define RFOR(i, b, a) for(int(i)=(b); (i)>=(a); (i)--)
#define RREP(i, n) FOR((i), (n), 0)

#define pb push_back
#define mp make_pair 

using namespace std;

const int INF=INT_MAX/4;
const int MOD=1000000007;
const double EPS=1e-14;

const bool debug_flag=true;

void debug(string str){
	if(debug_flag){
		cout<<str<<endl;
	}
}

void debugs(string str){
	if(debug_flag){
		cout<<str;
	}
}

int main(int argc, char* argv[]){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout.precision(10);

	int n;
	cin>>n;

	string str;
	vector<vector<int> > cnt(n);
	for(int i=0; i<n; i++){
		cnt[i].resize(26);
		cin>>str;
		for(int j=0; j<str.length(); j++){
			cnt[i][str[j]-'a']++;
		}
	}

	vector<int> mins(26);
	for(int j=0; j<26; j++){
		mins[j]=50;
		for(int i=0; i<n; i++){
			if(mins[j] > cnt[i][j]){
				mins[j] = cnt[i][j];
			}
		}
	}

	for(int i=0; i<26; i++){
		for(int j=0; j<mins[i]; j++){
			cout<<char('a'+i);
		}
	}
	cout<<endl;

	return 0;
}



Measured memory_bytes: 256