akhauriyash/Code-Regression huggingface dataset:
nl = list(input())
k = int(input())
l = len(nl) - k

# iけためまでの0のj数
dp1 = [[0 for i in range(l+2)] for j in range(len(nl)+1)]
dp2 = [[0 for i in range(l+2)] for j in range(len(nl)+1)]
dp1[0][0] = 0
dp2[0][0] = 1
for i, t in enumerate(nl):
    t = int(t)
    for j in range(10):
        if j == 0:
            if j < t:
                for p in range(l+1):
                    dp1[i+1][p+1] += dp2[i][p]
                    dp1[i+1][p+1] += dp1[i][p]
            elif j == t:
                for p in range(l+1):
                    dp2[i+1][p+1] += dp2[i][p]
                    dp1[i+1][p+1] += dp1[i][p]
            else:
                for p in range(l+1):
                    dp1[i+1][p+1] += dp1[i][p]
        else:
            if j < t:
                for p in range(l+1):
                    dp1[i+1][p] += dp2[i][p]
                    dp1[i+1][p] += dp1[i][p]
            elif j == t:
                for p in range(l+1):
                    dp2[i+1][p] += dp2[i][p]
                    dp1[i+1][p] += dp1[i][p]
            else:
                for p in range(l+1):
                    dp1[i+1][p] += dp1[i][p]


print(dp1[-1][l] + dp2[-1][l])



Measured memory_bytes: 3444
#include <cstdio>
const int N = 1e5 + 5;
inline int Get() {
	char ch;
	while ((ch = getchar()) < '0' || ch > '9');
	int Num = ch - '0';
	while ((ch = getchar()) >= '0' && ch <= '9')
		Num = (Num << 3) + (Num << 1) + ch - '0';
	return Num;
}
int n, m, sum[N], flag[N], cnt;
int main() {
	n = Get(), m = Get();
	for (int i = 1; i <= n; ++i) sum[i] = 1;
	flag[1] = true;
	
	while (m--) {
		int x = Get(), y = Get();
		--sum[x], ++sum[y];
		if (flag[x]) flag[y] = true;
		if (!sum[x]) flag[x] = false;
	}
	
	for (int i = 1; i <= n; ++i) cnt += flag[i];
	printf("%d\n", cnt);
}

Measured memory_bytes: 896
#include <iostream>
#include <vector>
using namespace std;

int BrickCount(int i, vector<int> b);

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    vector<int> a(N, 0);
    int l;
    int i = 0;
    while (cin >> l){
        a[i] = l;
        i++;
        if (i >= N){
            break;
        }
    } 

    int brk = 0;
    int stf = 0;
    for (int i = 0; i < N; ++i){
        if (a[i] == (stf + 1)){
            stf++;
        }
        else {
            brk++;
        }
    }

    if (brk == N){
        brk = -1;
    }

    cout << brk << "\n";

    return 0;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <cstdio>
typedef long long ll;
#define all(x) (x).begin(), (x).end()  // sortなどの引数を省略
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define max3(x, y, z) max(x, max(y, z))

#ifdef _MSC_FULL_VER  //デバッグ出力
#define dout cout
#define debug() if (true)
#define check(x) std::cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) std::cout << "☆" << x << endl
#else
#define dout \
  if (false) cout
#define debug() if (false)
#define check(x) \
  if (false) cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) \
  if (false) cout << "☆" << x << endl
#endif
using namespace std;
int main() {
  int a;
  cin >> a;
  if (a<1200){
    cout << "ABC";
  } else if (a < 2800) {
    cout << "ARC";
  } else {
    cout << "AGC";
  }
}
/*
//よく使うやつ
int N;
cin >> N;
vector<int> list(N);
for (int i = 0; i < N; i++) {
cin >> list[i];
}
// for文
for (int i = 0; i < N; i++) {
}
//配列
vector<int> list;
list.at(i)
vector<vector<int>> list(10, vector<int>(10));
sort(all(list));
sort(all(list), greater<int>());
//配列の内容表示
dout << "====listの内容====\n";
for (int i = 0; i < N; i++) dout << list[i] << endl;
dout << "====ここまで====\n";
*/


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <queue>
#include <utility>
#include <cmath>
#include <iomanip>
using namespace std;

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

typedef long long lint;
typedef pair<int,int> P;

#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

int main()
{

    int A,B,K;
    cin >> A >> B >> K;

    int ans = 0;
    int num = 0;
    for(int i=min(A,B);i!=0;--i){
    	if(A%i==0 && B%i==0) num ++;
    	if(num==K){
    		ans = i;
    		break;
    	}
    }
    cout << ans << endl;


}


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

int main() {
	int a,b;
	cin >> a >> b;
	char k = 'x';
	if(a + b == 15)
	{
		k = '+';
	}
	else if(a * b == 15)
	{
		k = '*';
	}
	cout << k << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
using namespace std;
using ll = long long;
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;
const ll MOD = 1e9 + 7;


int main(){
    int n, q;
    cin >> n >> q;
    using Graph = vector<vector<int>>;
    Graph G(n, vector<int>());
    rep(i, n-1){
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    vector<int> ans(n);
    rep(i, q){
        int p, x;
        cin >> p >> x;
        ans[p-1] += x;
    }

    function<void(int, int)> dfs = [&](int v, int p){
        for(auto nv: G[v]){
            if(nv == p) continue;
            ans[nv] += ans[v];
            dfs(nv, v);
        }
    };

    dfs(0, -1);
    rep(i, n) cout << ans[i] << " ";
    cout << endl;
}

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

using namespace std;

long long len(long long a){
	int res=0;
	while(a)res++,a/=10;
	return res;
}

int main(){
	long long n,ans=1e18;
	cin >> n;
	for(long long i=1;i*i<=n;i++){
		if(n%i!=0)continue;
		ans=min(ans,max(len(i),len(n/i)));
	}
	cout<<ans;
	
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define MOD 1000000007
vector<ll> fact(2000001);
void init_fact(int n){
	fact[0]=1;
	for (int i = 1; i < n+1; i++){
		fact[i]=fact[i-1]*i;
		fact[i]%=MOD;
	}
}
ll mod_pow(ll x, ll p){
	ll res=1;
	ll n=x;
	while(p>0){
		if(p&1==1)res=(res*n)%MOD;
		n=(n*n)%MOD;
		p=(p>>1);
	}
	return res;
}

ll nCr(int n, int r){
	ll res=1;
	res*=fact[n];
	res*=mod_pow(fact[r],MOD-2);
	res%=MOD;
	res*=mod_pow(fact[n-r],MOD-2);
	res%=MOD;
	return res;
}
int main() {
    ll K; cin>>K;
    string s; cin>>s;
    ll S=s.size();
    init_fact(K+S);
    ll ans=0;
    for (int i = 0; i < K+1; i++){
        ll tmp=nCr(S+K-i-1,S-1);
        tmp*=mod_pow(25,K-i);
        tmp%=MOD;
        tmp*=mod_pow(26,i);
        tmp%=MOD;
        ans+=tmp;
        ans%=MOD;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 20880
import java.util.*;

public class Main{
	public static void main(String args[]){
		new Main();
	}

	public Main(){
		int size = 0;
		long sum = 0;
		int[] data = null;
		List<Long> Ans = new ArrayList<Long>();
		Scanner sc = new Scanner(System.in);

		while(true){
			size = sc.nextInt();

			if(size == 0) break;

			data = new int[size];
			for(int i=0; i<size; i++){
				data[i] = sc.nextInt();
			}

			QuickSort(data, 0, size-1);

			sum = 0;
			for(int i=0; i<size; i++){
				sum += (long)(data[i] * (size - i - 1));
			}
			Ans.add(sum);
		}

		for(int i=0; i<Ans.size(); i++){
			System.out.println(Ans.get(i));
		}
	}

	public void QuickSort(int[] a, int start, int end){
		if(start == end) return;
		int p = pivot(a, start, end);
		if(p != -1){
			int k = partition(a, start, end, a[p]);
			QuickSort(a, start, k-1);
			QuickSort(a, k, end);
		}
	}

	public int pivot(int[] a, int start, int end){
		int k = start+1;
		while(k <= end && a[start] == a[k]) k++;
		if(k > end) return -1;
		if(a[start] >= a[k]) return start;
		return k;
	}

	public int partition(int[] a, int start, int end, int x){
		int l = start;
		int r = end;

		while(l <= r){
			while(l <= end && a[l] < x) l++;

			while(r >= start && a[r] >= x) r--;

			if(l > r) break;
			int t = a[l];
			a[l] = a[r];
			a[r] = t;
			l++;
			r--;
		}

		return l;
	}
}

Measured memory_bytes: 13000
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pll pair<ll,ll>
#define pb push_back
#define F first
#define S second
#define I insert
#define vll vector<ll>
#define vpll vector<pll>
#define all(x) (x).begin(), (x).end()
#define sz(x) (ll)(x).size()
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){ cout << name << " : " << arg1 << std::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 endl '\n'

ll power(ll a, ll b, ll mod){ ll c = 1; while(b>0){ if(b%2) c*=a, c%=mod; b/=2; a*=a; a%=mod; } return c; }
 
const ll N = (20) + 10;
const ll M = 320;
const ll Mod = 1e9 + 7;
vll adj[N];
vll we[N];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout<<setprecision(25);
    ll n,a,b,c,d,m,x,y,e,i,j,k; e = 0;
    cin>>n;
    n--;
    a = 1<<19; i =1; j=-1;
    // cout<<a*2<<endl;
    // cout<<a<<endl;
    // cout<<a-a/2<<endl;
    vll v;
    while(a > 0){
        if( (n & a) > 0 ){
            if(j == -1) j=i;
            else v.pb(i);
        }
        i++; a/=2;
    }
    // cout<<j<<endl;
    // for(auto z : v) cout<<z<<' ';
    // cout<<endl;
    for(i=1;i<20;i++){
        adj[i].pb(i+1);
        we[i].pb(0);
        if(i >= j){
            adj[i].pb(i+1);
            k = 20-i-1; k = 1<<k;
            we[i].pb(k);
        }
    }
    ll val = 1<<(20-j);
    ll la = -1;
    for(auto z : v){
        adj[1].pb(z);
        we[1].pb(val);
        val += 1<<(20-z);
    }
    adj[1].pb(20);
    we[1].pb(val);
    for(i=1;i<=20;i++){
        e += sz(adj[i]);
    }
    cout<<20<<' '<<e<<endl;
    for(i=1;i<=20;i++){
        for(j=0;j<sz(adj[i]);j++){
            cout<<i<<' '<<adj[i][j]<<' '<<we[i][j]<<endl;  
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
  int counta = 0, countb = 0;
  string S;
  cin >> S;
  size_t size = S.length();
  
  for(int i = 0; i < size; i += 2) if(S[i] != '0') ++counta;
  for(int i = 1; i < size; i += 2) if(S[i] != '1') ++counta;
  
  for(int i = 0; i < size; i += 2) if(S[i] != '1') ++countb;
  for(int i = 1; i < size; i += 2) if(S[i] != '0') ++countb;
 
  if(counta > countb) cout << countb <<endl;
  else cout << counta << endl;
  
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int(i)=0;i<(n);i++)

int main(){
  int n;cin>>n;
  long long ans=0;
  vector<long long> d(n,0);
  REP(i,n) cin>>d.at(i);
  for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n;j++){
      ans+=d.at(i)*d.at(j);
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
using P = pair<int, int>;
using ll = long long;
const int INF = 1001001001;

int main() {
    int n; cin >> n;
    vector<ll> a(n);
    rep(i, n){
        cin >> a[i];
    } 
    rep(i, n){
        if(a[i] == 0){
            cout << 0 << endl;
            return 0;
        }
    } 
    // sort(a.begin(), a.end());
    ll ans = 1;
    ll ans1 = 1000000000000000000;
    rep(i, n){
        ans *= a[i];
        ans1 /= a[i];
    } 
    if(ans1 < 1){
        cout << -1 << endl;
        return 0;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4052
# Your code here!
n = gets.to_i

arr = gets.split.map(&:to_i).sort
sum=Array.new(n,0)
sum[0] = arr[0]
i=1
(n-1).times{
    
    sum[i] = sum[i-1]+arr[i]
    
    i+=1
}

key=0
j=0

(n-1).times{
    
    if sum[j]*2<arr[j+1]
        key = j+1  
    end
    
   j+=1 
    
}

puts  n-key










Measured memory_bytes: 10112
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

h, w, k = LI()
sy, sx, gy, gx = LI()
cost = [[INF] * w for _ in range(h)]
cost[sy - 1][sx - 1] = 0
grid = SR(h)
q = deque([(sy - 1, sx - 1)])
while q:
    cy, cx = q.popleft()
    for i, j in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        for l in range(1, k + 1):
            ny, nx = cy + i * l, cx + j * l
            if 0 <= nx < w and 0 <= ny < h and grid[ny][nx] == "." and cost[ny][nx] >= cost[cy][cx] + 1:
                if cost[ny][nx] == INF:
                    q.append((ny, nx))
                cost[ny][nx] = cost[cy][cx] + 1
            else:
                break


print(cost[gy - 1][gx - 1] if cost[gy - 1][gx - 1] != INF else -1)










Measured memory_bytes: 119740
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

using namespace std;

int main() {
   int x,y;
   cin >> x >> y;
   cout << x+y/2 << endl;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;
 
public class Main {    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int n = sc.nextInt();
        List<Integer> list = new ArrayList<>();
        for(int i=1;i<=n;i++){
            int p = sc.nextInt();
            list.add(p);
        }
        sc.close();
        boolean flag = true;
        int plus = x;
        int minus = x;
        while(true){
            if(flag){
                if(!list.contains(x)){
                    System.out.println(x);
                    return;
                }else{
                    flag = false;
                }
            }else{
                minus--;
                if(!list.contains(minus)){
                    System.out.println(minus);
                    return;
                }
                plus++;
                if(!list.contains(plus)){
                    System.out.println(plus);
                    return;
                }
            }
        }
    }
}

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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#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 FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll n,k,r,s,p;
  cin >> n >> k >> r >> s >> p;
  string t;
  cin >> t;

  string rt = "rsp";
  vll po;
  po.push_back(r);
  po.push_back(s);
  po.push_back(p);
  REP(i, n){
    REP(j, 3){
      if(t[i] == rt[j]){
        if(j == 0)
          t[i] = rt[2];
        else
          t[i] = rt[j-1];
        break;
      }
    }
  }


  ll ans = 0;
  for(ll i = 0; i < n; i++){
    if(i-k>=0){
      if(t[i] == t[i-k]){
        t[i] = 'a';
        continue;
      }
    }

    REP(j, 3){
      if(t[i] == rt[j])
        ans += po[j];
    }
  }

  cout << ans << endl;

}


Measured memory_bytes: 592
from numba import jit
def _resolver(N):
    count = 0
    for j in range(1, N+1):
        for i in range(1, N+1):
            if i % j ==0:
                count += i
    #j, j*2, j*3 ,,,, j*(N//j)
    return count

#@jit("u8(u8)")
def resolver(N):
    if N == 0:
        return 0
    if N == 1:
        return 1
    
    count = 0
    #for j in range(N+1):
    #    for i in range(N+1):
    #        if i % j ==0:
    #            count += i
    #j, j*2, j*3 ,,,, j*(N//j)

    for j in range(1,N+1):
        length = N // j
        count += length*(j+(j*length)) // 2
    return count

def resolver2(N):

    import numpy as np
    J = np.arange(1, N+1, dtype=np.int64)
    length = N // J
    count = sum(length*(J+(J*length)) // 2)
    return count

def test():
    print(resolver2(10**7))
    for n in range(1, 100):
        ans1 = _resolver(n)
        ans2 = resolver2(n)
        if ans1 != ans2 or n < 11:
            print(f"n={n} ans={ans1}, {ans2}")
    print("OK")


def main():
    #test()
    N = int(input())
    ans = resolver(N)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 91604
//Compete against Yourself.
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define pb push_back
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 50;

int n, sz[N], x[N][N], y[N][N];
int32_t main(){_

   cin>>n;  

   for (int i = 0; i < n; ++i)
   {
      cin >> sz[i];

      for (int j = 0; j < sz[i]; ++j)
      {
         cin >> x[i][j] >> y[i][j];
         --x[i][j];
      }

   }

   int ans = 0;

   for (int i = 0; i < (1LL << n); ++i)
   {
      vector<int> honest;
      vector<bool> good(n, false);
      for (int j = 0; j < n; ++j)
      {
         if(i & (1LL << j)){
            honest.push_back(j);
            good[j] = true;
         }
      }

      bool is_good = true;
      for(auto it: honest){
         for (int i = 0; i < sz[it]; ++i)
         {
            int xx = x[it][i], yy = y[it][i];
            if(good[xx] != yy){
               is_good = false;
               break;
            }
         }
      }

      if (!is_good){
         continue;
      }

      int vals = accumulate(good.begin(), good.end(), 0);
      tr(i, good);
      ans = max(ans,  vals);
   }

   cout<<ans;
   
   

   return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long w = sc.nextLong();
        long h = sc.nextLong();
        double x = sc.nextLong();
        double y = sc.nextLong();
        double midx = w / 2.0;
        double midy = h / 2.0;
        System.out.println(w * h / 2.0);
        if(midx == x && midy == y) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
}

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

#define NDEBUG
#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


ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }

const ll MOD=1000000007LL;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

vector<int> hs;

ll solve(int H, int W, int K) {
    int P = 1 << (W - 1);
    rep(p, P) {
        bool good = true;
        for (int i = 0, m = 3; i < W -2; ++i, m <<= 1) {
            if ((p & m)==m) { good = false; break; }
        }
        if (good) hs.pb(p);
    }
    vector<vector<int>> pat(W, vi(W, 0));
    for (int a=0,ma=1;a<W;++a,ma<<=1) {
        int cnt = 0;
        for (int h : hs) {
            bool good = true;
            if (a>=1 && (h&(ma>>1))) {
                good = false;
                continue;
                 }
            if (a < W-1 && (h&ma)) {
                good = false;
                continue;
            }
            if (good) {
                ++cnt;
            }
        }
        pat[a][a] = cnt;

        if (a<W-1 ) {
            cnt = 0;
            for (int h : hs) {
                if (h & ma) {
                    ++cnt;
                }
            }
            pat[a][a + 1] = pat[a + 1][a] = cnt;
        }

        for (int b = a + 2; b<W; ++b) {
            pat[a][b] = pat[b][a] = 0;
        }
     }

     vector<ll> dp(W, 0);
     dp[0] = 1;
     rep(i, H) {
         vector<ll> dp2(W, 0);
         rep(a, W) rep(b, W) { dp2[b] = ADD(dp2[b], MUL(dp[a], pat[a][b])); }
         dp = dp2;
     }

     return dp[K - 1];
}

int main() {
    int H, W, K;
    cin >> H >> W >> K;
    assert(IN(H, 1, 100));
    assert(IN(W, 1, 8));
    assert(IN(K, 1, W));

    cout << solve(H,W,K) << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define Yes cout<<"Yes"<<endl #define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl #define no cout<<"no"<<endl
#define vec(a,y,x)  vector<vector<char>> a (y,vector<char>(x))
const vector<int> dx={1,0,-1,0};
const vector<int> dy={0,1,0,-1};

in sum_vec(vector<int> a){
  in sum=0;
  rep(i,a.size())
    sum+=a.at(i);
  return sum;
}

vector<int> color;
bool dfs (vector<vector<int>>&G,int v,int cur){
  color.at(v)=cur;
  for(int next_v : G.at(v)){
    //cout<<"v:"<<v<<" next_v:"<<next_v<<" ";
    if(color.at(next_v)==-1){
      //cout<<"未探索"<<endl;
      if(!dfs(G,next_v,1-cur)) return false;
    }
    else{
      if(color.at(next_v)==cur) {/*cout<<"矛盾"<<endl;*/ return false;}
      if(color.at(next_v)==1-cur){/*cout<<"矛盾無し"<<endl;*/ continue;}
    }
  }
  return true;
}

int main(){
  in m;
  in n;
  cin>>n>>m;
  vector<vector<int>> G(n);
  
  rep(i,m){
    int a,b;
    cin>>a>>b;
    G.at(a-1).push_back(b-1);
    G.at(b-1).push_back(a-1);
  }
  color.assign(n,-1);
  in sum;
    
  if(dfs(G,0,0)){
    sum=sum_vec(color);
    printf("%ld \n",sum*(n-sum)-m);
  }
  else
    printf("%ld \n",(n*(n-1))/2-m);
  //color.assign(n,-1);
  //cout<<dfs(G,0,0)<<endl;
  //cout<<sum<<endl;
  //rep(i,n)
    //cout<<color.at(i);
  
}

Measured memory_bytes: 6912
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
#define ll long long
#define FOR(i, a, b) for(ll i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rep1(i, n) FOR(i, 1, n+1)
#define rrep(i, n) for (ll i = ((int)(n)-1); i >= 0; --i)
#define whole(x) (x).begin(),(x).end()
#define rwhole(x) (x).rbegin(), (x).rend()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define P pair<int, int>
#define debug(var) cerr << "[" << #var << "] " << var << endl
template<typename T1, typename T2>
bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
template<typename T1, typename T2>
bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define pr(s) cout << (s) << '\n'
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
const int INF = 1001001001;
const ll INFll = 1E+18;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n, x, m;
    cin >> n >> x >> m;
    vector<ll> v(m);
    rep(i, m) {
        v[i] = ((ll)i*i)%m;
        //debug(v[i]);
    }
    
    ll xx = x;
    ll s = 0;
    ll index = 0;
    while (1) {
        s += xx;
        xx = v[xx];
        index++;
        if (xx==0) {
            pr(s);
            return 0;
        }
        if (index==n) {
            pr(s);
            return 0;
        }
        if (index==m+5) break;
    }
    
    
    vector<bool> used(m);
    ll loop = 0;
    ll now = x;
    ll sum_loop = 0;
    ll ans = 0;
    ll start = 0;
    //return 0;
    while (1) {
        used[now] = true;
        now = v[now];
        if (used[now]) {
            start = now;
            break;
        }
    }
    now = x;
    while (1) {
        ans += now;
        now = v[now];
        n--;
        if (now==start) break;
    }
    now = start;
    while (1) {
        loop++;
        sum_loop += now;
        now = v[now];
        if (now==start) break;
    }
    //debug(loop);
    ll z = n/loop;
    
    ans += z*sum_loop;
    n %= loop;
    now = start;
    rep(i, n) {
        ans += now;
        now = v[now];
        //debug(ans);
    }

    
    
    pr(ans);
    return 0;
}

Measured memory_bytes: 3988
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
typedef int64_t Int;

int main(){
    string S; int K;
    cin >> K >> S;
    
    if(S.size() <= K){
        cout << S << endl;
    } else {
        rep(i,K) cout << S[i];
        cout << "..." << endl;
    }
}


Measured memory_bytes: 3628
#include<stdio.h>
#include<string.h>

int main(void){
    char S[10];
    int ch = 0;
    int num = 0;
    int N;
    scanf("%s",S);

    for(int i = 0; i < strlen(S); i++){
        if(i == 0){
            if(S[i] != 65){ ch = 0; break;}
            ch = 1;
        }

        if(i == 1){
            if(S[i] >= 65 && S[i] <= 90){ ch = 0; break;}
        }

        if(i >= 2 && i <= strlen(S) -2){
            if(S[i] == 67){
                if(num == 0){ num = 1; continue;}
                else{ch = 0; break;}
            }else if(S[i] >= 65 && S[i] <= 90){
                ch = 0; break;
            }
        }

        if(i > strlen(S)- 2){
            if(S[i] >= 65 && S[i] <= 90){
                ch = 0;
                break;
            }
        }
    }
    if(num == 0) ch = 0;

    if(ch == 1) printf("AC\n");
    else if(ch == 0) printf("WA\n");
    return 0;
}

Measured memory_bytes: 128
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author EigenFunk
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ADuplexPrinting solver = new ADuplexPrinting();
        solver.solve(1, in, out);
        out.close();
    }

    static class ADuplexPrinting {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            out.println(n / 2 + n % 2
            );
        }

    }
}



Measured memory_bytes: 23124
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>



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

using namespace std;
int a,b,c,d;
int k1,k2,k3;

int main(){
  cin >> a >> b >> c >> d;
  k1 = a-b;
  k1 = max(k1,-k1);
  k2 = b-c;
  k2 = max(k2,-k2);
  k3 = max(a-c,c-a);
  
  if((k1<=d&&k2<=d)||k3<=d) cout << "Yes" << endl;
  else cout << "No" << endl;
  
  return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char s1[3001],s2[3001],s[3001];
long long mat[3001][3001],c[3001][3001];
int main()
{
	long long i,j,idx=0;
	scanf("%s",s1);
	scanf("%s",s2);
	long long len1=strlen(s1),len2=strlen(s2);
	for(i=0;i<=len1;i++)
		mat[0][i]=0;
	for(i=0;i<=len2;i++)
		mat[i][0]=0;
	for(i=1;i<=len2;i++)
	{
		for(j=1;j<=len1;j++)
		{
			if(s1[j-1] == s2[i-1])
			{
				mat[i][j] = mat[i-1][j-1] + 1;
				c[i][j] = 1;
			}
			else
			{
				if(mat[i-1][j] > mat[i][j-1])
				{
					mat[i][j] = mat[i-1][j];
					c[i][j] = 2;
				}
				else
				{
					mat[i][j] = mat[i][j-1];
					c[i][j]=3;
				}
			}
		}
	}
	/*for(i=0;i<=len2;i++)
	{
		for(j=0;j<=len2;j++)
			printf("%lld ",mat[i][j]);
		printf("\n");
	}*/
	s[idx]=' ';
	long long id=len1;
	for(i=len2;i>=0;)
	{
		for(j=id;j>=0;)
		{
			if(c[i][j] == 1)
			{
				s[idx++]=s1[j-1];
				j--;
				i--;
				break;
			}
			else if(c[i][j] == 2)
			{
				i--;
				break;
			}
			else
				j--;
			if(i==0 || j==0)
				break;
		}
		id=j;
		if(i==0 || j==0)
			break;
	}
	for(i=idx-1;i>=0;i--)
		printf("%c",s[i]);
	printf("\n");
}


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

#define MAX_VAL 300010

using namespace std;

using ii = pair<int,int>;
using ll = long long;

int main()
{
    cin.tie(0);ios_base::sync_with_stdio(false);
    int N, W;
    cin >> N >> W;

    vector<ll> dp(MAX_VAL, numeric_limits<ll>::max());
    dp[0] = 0;

    for(int i=0;i<N;++i){
        ll w; int v; cin>>w>>v;
        for(int j=MAX_VAL;j>=0;j--){
            if(dp[j] != numeric_limits<ll>::max() && j+v < MAX_VAL){
                dp[j+v] = min(dp[j+v], dp[j] + w);
            }
        }
    }


    for(int i=MAX_VAL-1;i>=0;i--){
        if(dp[i] != numeric_limits<ll>::max() && dp[i] <=W){
            cout << i << '\n';
            break;
        }
    }
    return 0;
}


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

using namespace std;

const long long M=2e5 + 10;
const long long M2=1e18 ;
long long n, k, l, r, mid, ll, rr, mmid, cnt, i, a[M];

int main(){
	
	cin >> n >> k;
	
	for (i = 0 ; i < n ; i ++ ) cin >> a [ i ] ;
	
	sort ( a , a + n ) ;
	
	l = -M2 ; r = M2 ;
	
	while ( l + 1 < r ){
		mid = l + r >> 1 ;
		cnt = 0;
		for (i = 0 ; i < n ; i ++ ){
			
			if (a [ i ] < 0){
				
				ll = i ; rr = n;
				
				while (ll + 1 < rr){

					mmid = ll + rr >> 1 ;
					if (a[i] * a[mmid] <= mid) rr = mmid;
					else ll = mmid;
					
				}
				
				cnt += n - rr;
			}
			else {
				ll = i ; rr = n;
				
				while (ll + 1 < rr){

					mmid = ll + rr >> 1 ;
					if (a[i] * a[mmid] <= mid) ll = mmid;
					else rr = mmid;
					
				}
				
				cnt += ll - i;
			}
		}
		if ( cnt < k ) l = mid ;
		else r = mid ;
	}
	
	cout << r ;
	
	return 0;
}

Measured memory_bytes: 5168
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int MOD = (int)(1e9) + 7;
const int INF = (1ll << 31) - 1;
const double PI = acos(-1);
const double EPS = 1e-9;
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 (a > b) { a = b; return true; } return false; }
const int NIL = -1;
struct Seg {
	int n;
	vector<int>d, lazy;
	Seg(int m) {
		for (n = 1; n < m; n <<= 1);
		d.assign(2 * n, INF);
		lazy.assign(2 * n, NIL);
	}
	void eval(int k, int l, int r) {
		if (lazy[k] != NIL) {
			d[k] = lazy[k];
			if (r - l > 1) {
				lazy[2 * k] = lazy[2 * k + 1] = lazy[k];
			}
			lazy[k] = NIL;
		}
	}
	void update(int a, int b, int x, int k = 1, int l = 0, int r = -1) {
		if (r == -1)r = n;
		eval(k, l, r);
		if (r <= a || b <= l)return;
		else if (a <= l&&r <= b) {
			lazy[k] = x;
			eval(k, l, r);
		}
		else {
			update(a, b, x, 2 * k, l, (l + r) / 2);
			update(a, b, x, 2 * k + 1, (l + r) / 2, r);
			d[k] = min(d[2 * k], d[2 * k + 1]);
		}
	}
	int find(int a, int b, int k = 1, int l = 0, int r = -1) {
		if (r == -1)r = n;
		eval(k, l, r);
		if (r <= a || b <= l)return INF;
		else if (a <= l&&r <= b)return d[k];
		else return min(find(a, b, 2 * k, l, (l + r) / 2), find(a, b, 2 * k + 1, (l + r) / 2, r));
	}
};
signed main() {
	cin.tie(0);
	int n, q; cin >> n >> q;
	Seg seg(n);
	rep(i, 0, q) {
		int com; cin >> com;
		if (com) {
			int s, t; cin >> s >> t;
			cout << seg.find(s, t+1) << endl;
		}
		else {
			int s, t, x; cin >> s >> t >> x;
			seg.update(s, t+1, x);
		}
	}
	return 0;
}

Measured memory_bytes: 4936
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
 
#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))
 
#define DEBUG(x) cout<<#x<<": "<<(x)<<endl
 
int main(){
	int n;
	cin>>n;
	int sum = 0, mx = 0;
	REP(i,n){
		int a;
		cin>>a;
		sum += a; CHMAX(mx, a);
	}
	sum -= mx/2;
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int MOD=1e9+7;
ll a[N];
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    ll n,k,sum=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++)   cin >> a[i];
    for(int i=1;i<=n;i++)   sum+=a[i];
    sort(a+1,a+1+n);
    cout << n + (k-sum)/a[1]<<endl;

    return 0;
}


Measured memory_bytes: 256
#二回目

n=int(input())
h=list(map(int,input().split()))

dp=[-1]*n
dp[0]=0
dp[1]=abs(h[1]-h[0])
for i in range(2,n):
    dp[i]=min(   abs(h[i]-h[i-1])+dp[i-1] ,abs(h[i]-h[i-2])+dp[i-2]  )
#print(dp)
print(dp[-1])



Measured memory_bytes: 13980
/*Whose woods these are I think I know.
His house is in the village though;
He will not see me stopping here
To watch his woods fill up with snow.

My little horse must think it queer
To stop without a farmhouse near
Between the woods and frozen lake
The darkest evening of the year.

He gives his harness bells a shake
To ask if there is some mistake.
The only other sound’s the sweep
Of easy wind and downy flake.

The woods are lovely, dark and deep,
But I have promises to keep,
And miles to go before I sleep,
And miles to go before I sleep.*/

#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007
const int maxn= 100010;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli n=0ll,x=0ll;
    cin>>n>>x;
    cout<<3ll*(n-__gcd(n,x))<<endl;
}

Measured memory_bytes: 256
/**
n×m  の行列 A  と、m×1  の列ベクトルb  を読み込み、A  と b  の積を出力するプログラムを作成してください。

次のように m  個の数を縦に並べたものを m×1 の列ベクトルと呼びます。

b=? ? ? ? ? b 1 b 2 :b m  ? ? ? ? ?

次のように n  個の数を含む列ベクトルを m  個横に並べたものを n×m  の行列と呼びます。

A=? ? ? ? ? a 11 a 21 :a n1  a 12 a 22 :a n2  ......:... a 1m a 2m :a nm  ? ? ? ? ?

ベクトルまたは行列の中に含まれる数のことを要素と呼び、m×1  の列ベクトル b  の上から i  番目の要素は b i (i=1,2,...,m) 、n×m  の行列 A  には n×m  個の要素が含まれ、i  行 j  列目の要素は a ij (i=1,2,...,n,j=1,2,...,m) で示されます。

n×m の行列 A  とm×1 の列ベクトル b  の積は、n×1 の列ベクトル c  となり、c  の i  番目の要素 c i   は次の式で得られます：

 */

/*sucannerクラス使うためにインポート*/
import java.util.Scanner;

class Main {
	// プログラムのエントリポイント
	public static void main(String[] args) {
		// 入力ストリームの生成
		int i = 0;
		int j = 0;
		int k = 0;

		Scanner sc = new Scanner(System.in);
		// 縦と横の数字を受け取る
		int n = sc.nextInt();
		int m = sc.nextInt();

		// 行列AとBの配列を作る
		int[][] A = new int[n][m];
		int[] B = new int[m];
		int[] C = new int[n];

		//受け取った縦＊横の数だけ処理を繰り返す
		for ( i = 0; i < n; i++) {
			for ( j = 0; j < m; j++) {
				//数字を受け取って配列に入れる
				A[i][j] = sc.nextInt();
				//配列確認用
				//System.out.print(A[i][j]);
			}
			//System.out.println();
		}
		//受け取った縦の数だけ処理を繰り返す
		for ( k = 0; k < m; k++){
			//数字を受け取って配列にいれる
			B[k] = sc.nextInt();
			//配列確認用
			//System.out.println(B[k]);
		}
		//計算
		for ( i = 0;  i < n ; i++){
			for ( j = 0; j < m ;j++){
				C[i] += A[i][j] * B[j] ;


		}
			//縦の回数だけ配列の中身を表示
			System.out.println(C[i]);
		}
	}
}

Measured memory_bytes: 31852
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+5;
const int mod=998244353;
ll fac[maxn];
ll inv[maxn];
ll power(ll base,ll n)
{
    ll r=1;
    while(n)
    {
        if(n%2) r=r*base%mod;
        base=base*base%mod;
        n/=2;
    }
    return r;
}
void init()
{
    fac[0]=1;
    for(int i=1;i<maxn;i++)
    {
        fac[i]=fac[i-1]*i%mod;
    }
    inv[maxn-1]=power(fac[maxn-1],mod-2);
    for(int i=maxn-1;i>=1;i--)
    {
        inv[i-1]=inv[i]*i%mod;
    }
}
ll C(ll m,ll n)
{
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,m,k;
    cin>>n>>m>>k;
    ll ans=0;
    init();
    for(int i=0;i<=k;i++)
    {
        ans+=m*C(i,n-1)%mod*power(m-1,n-i-1)%mod;
        ans%=mod;
    }
    cout<<ans<<'\n';

}


Measured memory_bytes: 6772
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define SORT(a) sort(a.begin(),a.end())
using namespace std;
int main(){
    //Seiranchan!
    int N,l,r,ans=0;
    cin >> N;
    REP(i,N){
        cin >> l >> r;
        ans += r-l+1;

    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <list>
using namespace std;
 
#define REP(i,n) for(int i=0;i<(n);++i)
#define ll long long
const long long INF = 1LL<<60;
const long long mod = 100000007;
using Graph = vector<vector<int>>;


int main(){
    int N,M;
    cin >> N >> M;
    int ans = 0;
    int a,b;
    a=0;
    b=0;
    if(N!=0&&N!=1) a = N * (N-1);
    a /= 2;
    
    if(M!=0&&M!=1) b = M * (M-1);
    b /= 2;
    ans = a+b;
    cout << ans << endl;
}

Measured memory_bytes: 3588
s=tuple(input())
a=0
n=len(s)-1

for i in range(2**n):
    l=list(s)
    c=1
    for j in range(n):
        if (i>>j)&1:
            l.insert(j+c,"+")
            c+=1
    a+=eval("".join(l))
print(a)

Measured memory_bytes: 38768
using namespace std;
#include<bits/stdc++.h>
#define int long long
#define pb push_back 
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define repa(i,a,b) for (int i=a; i<=b; i++)
#define repd(i,b,a) for (int i=b; i>=a; i--)
#define endl "\n"
//debugging
#define debug1(a) cout<<#a<<" = "<<(a)<<endl;
#define debug2(a,b) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<endl;
#define debug3(a,b,c) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl;
#define debug4(a,b,c,d) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<", "<<#d<<" = "<<(d)<<endl;

const int N = 1e+6+5;
int big = 1e+18+3;
int mod = 1e+9+7;

signed main()
{
    IOS;
        
    int n,m;
    cin>>n>>m;
    int sum = 0;
    int ar[m+1];
    repa(i,1,m)
        cin>>ar[i],sum+=ar[i];
    if (sum>n)
        cout<<-1<<endl;
    else
        cout<<n-sum<<endl;
}

Measured memory_bytes: 3732
def resolve():
    H, W = list(map(int, input().split()))
    N = int(input())
    A = list(map(int, input().split()))
    C = [[0 for _ in range(W)] for __ in range(H)]
    color = 1
    reverse = False
    cnt = 0
    for i in range(H):
        for j in range(W):
            if reverse:
                _j = W-1 - j
            else:
                _j = j
            C[i][_j] = color
            cnt += 1
            if cnt == A[color-1]:
                color += 1
                cnt = 0
        reverse = not reverse
    [print(" ".join(map(str, C[i]))) for i in range(H)]
        

if '__main__' == __name__:
    resolve()

Measured memory_bytes: 3568
# ABC044C - 高橋君とカード / Tak and Cards (ARC060C)
from collections import defaultdict


def main():
    N, A = tuple(map(int, input().split()))
    X = tuple(map(lambda x: int(x) - A, input().split()))
    D = defaultdict(int)
    D[0] = 1
    for i in X:
        for j, k in list(D.items()):
            D[i + j] += k
    print(D[0] - 1)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3572
#include <stdio.h>

int main(void)
{
	int i, exit = 0;
	char c;
	
	while (1){
		scanf("%c", &c);
		
		if (c == '\n'){
			break;
		}
		
		if (c >= 'a' && c <= 'z'){
			c -= 'a' - 'A';
		}
		
		printf("%c", c);
	}
	
	printf("\n");
	
	return (0);
}

Measured memory_bytes: 524
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using ld = long double;

int main()
{
  ll dep = 100;
  ll x;
  int count = 0;
  cin >> x;


  while (dep < x) {
    ld culc = dep * 1.01;
    dep = floor(culc);
    count++;
  }

  cout << count << endl;

  return 0;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;

const int MOD = 1000000007;

int main()
{
    int n;
    cin >> n;

    vector<ll> a(n);
    rep (i, n)
        cin >> a[i];

    ll ans = 0;
    rep (digit, 60)
    {
        ll cnt0 = 0, cnt1 = 0;
        rep (i, n)
        {
            if (1 & (a[i] >> digit))
                cnt1++;
            else
                cnt0++;
        }
        ll pow = (1LL << digit) % MOD;
        ll temp = cnt0 * cnt1 % MOD;
        temp = temp * pow % MOD;
        ans = (ans + temp) % MOD;
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5632
#include <stdio.h>

int main(void)
{
	int n, i;
	int e, p1, p2, cnt;
	long long num[4000] = {0};
	int flag[4000] = {0};
	long long tmp;

	while (1) {
		scanf("%d", &n);
		if (n == 0) {
			break;
		}
		cnt = 1;
		for (i = 0; i < 4000; ++i) {
			num[i] = 0;
			flag[i] = 0;
		}
		
		for (i = 0; i < n; ++i) {
			scanf("%d %d %d", &e, &p1, &p2);
			num[e] += p1 * p2;
			
			
			if (num[e] >= 1000000) {
				cnt = 0;
				if (flag[e] == 0) {
					printf("%d\n", e);
					flag[e] = 1;
				}
			}
		}
		if (cnt) printf("NA\n");
	}
	
	return 0;
}

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

int main() {
  int a,b,c,n;
  cin >> a>>b>>c>>n;
  
  long ans=0;
  rep(i,n/a+1){
    rep(j,(n-i*a)/b+1){
      if((n-i*a-j*b)%c==0){
        ans++;
      }
    }
  }
  
  
  cout<<ans<<endl;  
}



Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = (int)1e9;
const ll  inf = (ll)1e18;
const int mod = 1000000007;
const int MAX_N = 100010;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	vector<ll> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}

	vector<ll> L(n + 1, 0), R(n + 1, 0);

	for (int i = 0; i < n; i++) {
		L[i + 1] = gcd(L[i], a[i]);
	}
	for (int i = n - 1; i >= 0; i--) {
		R[i] = gcd(R[i + 1], a[i]);
	}

	ll ma = 0;
	for (int i = 0; i < n; i++) {
		chmax(ma, gcd(L[i], R[i + 1]));
	}

	cout << ma << endl;

	return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
ll ans = 0;

int main()
{
ll n ;
cin >> n ;
vector<vector<ll>> v(n);
rep(i,n-1){
  ll a , b ;
  cin >> a >> b ;
  if(a>b)swap(a,b);
  v[a-1].push_back(b-1);
}
ans=n*(n+1)/2;
rep(i,n){
  for(auto j:v[i]){
    ans+=n*(n+1)/2-(i+1)*(n-j);
  }
}
rep(i,n){
  ans-=n*(n+1)/2-(i+1)*(n-i);
}
cout << ans << endl;
return 0;
}

Measured memory_bytes: 14264
#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
	int n;
	int ans = 0;
	cin >> n;
	vector<int> vec(n);

	for (int i = 0; i < n; i++) {
		cin >> vec.at(i);
	}

	for (int i = 0; i < n; i++) {
		if (vec.at(i) % 2 == 0) {
			if ((vec.at(i) % 3 != 0) && (vec.at(i) % 5 != 0)) {
				ans = 1;
			}
		}
	}

	if (ans == 0) {
		cout << "APPROVED" << endl;
	}
	else {
		cout << "DENIED" << endl;
	}
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,a,n) for(int i = (a);i < (n);i++)
typedef unsigned long long ull;
typedef long long ll;
using namespace std;

int main(){
    int n;
    int used_cnt[201] = {0};
    cin >> n;
    int pts[n] = {0},game[n][3];
    
    rep(i,0,n){
        rep(j,0,3){
            cin >> game[i][j];
        }
        
    }
    
    rep(i,0,3){
        rep(i,0,201){
            used_cnt[i] = 0;
        }
        rep(j,0,n){
            used_cnt[game[j][i]]++;
        }
        
        rep(j,0,n){
            if(used_cnt[game[j][i]] == 1){
                pts[j] += game[j][i];
            }
        }
    }
    
    rep(i,0,n){
        cout << pts[i] << endl;
        
    }

    
    return 0;   
}


Measured memory_bytes: 3104
A = input()

#print(A)

LENGTH = len(A)
S = int(A)
S_LIST = []

for i in A:
    S_LIST.append(i)

#print(S_LIST)

LIST = list(map(int,S_LIST))
#print(LIST)

PATTERN_A = []
for i in range(LENGTH):
    if i % 2 == 0:
        PATTERN_A.append(0)
    else:
        PATTERN_A.append(1)

#print(PATTERN_A)


COUNT = 0
for i in range(LENGTH):
    if PATTERN_A[i] == LIST[i]:
        COUNT += 1

if LENGTH - COUNT < COUNT:
    COUNT = LENGTH - COUNT

print(COUNT)

Measured memory_bytes: 5680