akhauriyash/Code-Regression huggingface dataset:
def min_lunlun(lmd, dnum):
    # lmdが先頭にあり、最も小さいdnum桁のlunlun数をつくる
    lst = [lmd]
    for i in range(1, dnum):
        lst.append(max(0, lst[i - 1] - 1))
    return lst


def next_lunlun(lst):
    # lstから次のlunlun数を作る
    # 数を増やせる桁を確認する
    add_d = -1
    for i in reversed(range(1, len(lst))):
        if lst[i] < 9 and lst[i - 1] >= lst[i]:
            add_d = i
            break
    lst[add_d] = lst[add_d] + 1
    for i in range(add_d + 1, len(lst)):
        lst[i] = max(lst[i - 1] - 1, 0)

    return lst



def submit():
    k = int(input())

    if k < 10:
        print(k)
        return

    # d[i][j] : i始まりのj桁のルンルン数の数
    d = [[0 for _ in range(11)] for _ in range(10)]
    for x in range(10):
        d[x][1] = 1

    for j in range(1, 10):
        for i in range(10):
            if 0 <= i - 1:
                d[i][j + 1] += d[i - 1][j]
            if i + 1 < 10:
                d[i][j + 1] += d[i + 1][j]
            d[i][j + 1] += d[i][j]

    total = 0
    lmd = dnum = -1
    for j in range(1, 11):
        for i in range(1, 10):
            if total + d[i][j] >= k:
                prev_total = total
                lmd = i
                dnum = j
                break
            total += d[i][j]
        if lmd > 0:
            break

    lst = min_lunlun(lmd, dnum)
    for i in range(k - prev_total - 1):
        next_lunlun(lst)
    print("".join(map(str, lst)))
    

submit()

Measured memory_bytes: 41692
#include<bits/stdc++.h>
using namespace std;
#define FasterIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

typedef unsigned long long ull;
typedef long long ll;
typedef double db;

#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pi pair<int,int>
#define vi vector<int>
#define pL pair<ll,ll>
#define vL vector<ll>
#define vp vector<pi>
#define vpL vector<pL>

const int MX=2000000+5;
const ll inf=1e16;
const ll mod=1e9+7;

ll bigmod(ll b, ll p)
{
    ll ans=1;
    for(; p; p>>=1)
    {
        if(p&1) ans=(ans*b)                       %mod;
        b=(b*b)                                   %mod;
    }
    return ans;
}

ll F[MX], IF[MX];

ll nCr(ll n, ll r)
{
    ll res=(IF[r]*IF[n-r])                         %mod;
    return (F[n]*res)                              %mod;
}

void FCT()
{
    F[0]=IF[0]=1;
    for(ll i=1; i<MX; i++) F[i]=(F[i-1]*i)         %mod;
    for(ll i=1; i<MX; i++) IF[i]=bigmod(F[i], mod-2);
}


ll tableSum(ll r1, ll c1, ll r2, ll c2)
{
    ll sm=0;
    for(int i=r1; i<=r2; i++)
    {
        sm=(sm+nCr(i+c2+1, c2))                    %mod;
        sm=(sm-nCr(i+c1, c1-1)+mod)                %mod;
    }
    return sm;
}

int main()
{
    FasterIO;

    FCT();

    ll r1, c1, r2, c2;

    cin>>r1>>c1>>r2>>c2;

    ll sm=tableSum(r1, c1, r2, c2);

    cout<<sm<<endl;
    return 0;
}


Measured memory_bytes: 31488
a=str(input())
odd0,even0=0,0
odd1,even1=0,0
for i in range(len(a)):
  if i%2==0:#奇数
    if a[i]=="0":
      odd0+=1
  else:
    if a[i]=="0":
      even0+=1
odd1=len(a)-int(len(a)/2)-odd0
even1=int(len(a)/2)-even0
print(min(odd1+even0,odd0+even1))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    string S; cin >> S;
    if (S.at(0) != 'A') {
        cout << "WA\n";
        return 0;
    }

    int count = 0;
    FOR(i, 2, S.length() - 1) {
        if (S.at(i) == 'C') count++;
    }
    if (count != 1) {
        cout << "WA\n";
        return 0;
    }

    count = 0;
    F0R(i, S.length()) {
        if (isupper(S.at(i))) {
            count++;
        }
    }
    if (count != 2) {
        cout << "WA\n";
        return 0;
    }
    cout << "AC\n";
    return 0;
}

// read the question correctly (ll vs int)
// template by bqi343

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


def main():
    N, Q = map(int, input().split())
    link = [[] for _ in range(N)]
    a = []
    b = []
    a_append = a.append
    b_append = b.append
    for i in range(N-1):
        x, y = map(int, input().split())
        a_append(x)
        b_append(y)
    cost = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        cost[p-1] += x

    for i in range(N-1):
        ai = a[i]-1
        bi = b[i]-1
        ci = cost[i]
        link[ai].append((bi, ci))
        link[bi].append((ai, ci))

    def dfs(v, c, p):
        for nv in link[v]:
            nv0 = nv[0]
            if nv0 == p:
                continue
            cost[nv0] += c
            dfs(nv0, cost[nv0], v)
        return

    dfs(0, cost[0], -1)

    print(*cost)


if __name__ == '__main__':
    main()


Measured memory_bytes: 328328
n = gets.chomp.to_i

d = Math.log10(n).floor + 1

# p d

if d == 1
  puts n
elsif d % 2 == 0
  puts '90' * (d / 2 - 1) + '9'
else
  c =  ('90' * ((d - 1) / 2 - 1) + '9').to_i
  puts c + (n - ('9' * (d - 1)).to_i)
end


Measured memory_bytes: 1788
import scipy.sparse.csgraph as c,numpy;s=numpy.int8([list(t[:-1])for t in open(0)][1:]);m=c.dijkstra(s);i=m[0]%2<1;print(-any(s[j][:,j].any()for j in(i,i^True))or-~int(m.max()))

Measured memory_bytes: 14832
#include<stdio.h>
#include<iostream>
using namespace std;

int main(){
	while(1){
		int n,a,u[10]={0,1,2,3,4,5,6,7,8,9},p[10]={};
		cin >> n;
		if(n==0)return 0;
		for(int i=0;i<n;i++){
			cin >> a;
			for(int i=0;i<10;i++){
				if(a==u[i])p[i]=p[i]+1;
				/*cout << "p["<< i << "]=" << p[i];*/ 
			}
			/*cout << endl;*/
		}
		/*for(int i=0;i<10;i++){
			cout << "p["<< i << "]=" << p[i]; 
		}*/
		for(int r=0;r<10;r++){
			if(p[r]==0){cout << "-";}
			else if(p[r]!=0){
				for(int i=0;i<p[r];i++){
					cout << "*";
				}
			}
			cout << endl;
		}

	}
	return 0;
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
using ll = long long int;
ll count(int n)
{
    ll c = 1;
    int t = 0;
    while(n%2==0)
    {
        t++;
        n/=2;
    }
    if(c>0)c*=(ll)(t+1);
    for(int i=3;i<=sqrt(n);i++)
    {
        int ans = 0;
        while(n%i==0)
        {
            ans++;
            n/=i;
        }
        if(ans>0)c*=(ll)(ans+1);
    }
    if(n>2)c*=2;
    return c;
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    //freopen("inputfile.txt","r",stdin);
    int n;cin>>n;
    ll ans = 0;
    for(int i=1;i<n;i++){
    if((n-i)==1) ans++;
    else ans+=count(n-i);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3664
#include<bits/stdc++.h>
using namespace std;
map<int,int>m;
map<int,int> ::iterator iter;

int main()
{
	string a;
	cin>>a;int sum=0,flag=0;
	if(a[0]=='R')
		flag=1;
	for(int i=1;i<3;i++)
	{
		if(a[i]=='R')
		flag=1;
		if(a[i]=='R'&&a[i-1]=='R')
		sum++;
	}
	if(flag==1)cout<<sum+1;else cout<<0; 
	return 0;
}

Measured memory_bytes: 3588
import java.util.*;
import java.io.*;
 
public class Main {
    static boolean[][] used;
    static int[] ans;
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = sc.nextInt();
        int m = sc.nextInt();
        ArrayList<ArrayList<Integer>> work = new ArrayList<ArrayList<Integer>>();
        for(int i = 0; i < m; i++){
            work.add(new ArrayList<Integer>());
        }
        for(int i = 0; i < n; i++){
            int a = sc.nextInt()-1;
            int b = sc.nextInt();
            if(a >= m){
                continue;
            }
            work.get(a).add(b);
        }
        Queue<Integer> q = new PriorityQueue<Integer>();
        int cnt = 1;
        for(int i = 1; i <= m; i++){
            int j = 0;
            int li = 0;
            Collections.sort(work.get(m-i),Comparator.reverseOrder());
            while(cnt > j && li < work.get(m-i).size()){
                if(cnt > q.size()){
                    q.add(work.get(m-i).get(li));
                }else{
                    int prev = q.poll();
                    q.add(Math.max(prev,work.get(m-i).get(li)));
                }
                j++;
                li++;
            }
            cnt++;
        }
        long ans = 0;
        while(q.size() > 0){
            ans += q.poll();
        }
        System.out.println(ans);
    }
}

class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;
    public FastScanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = null;
    }

    public String next() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public String nextLine() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken("\n");
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
         return Double.parseDouble(next());
    }

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }

    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nextLong();
        return a;
    } 
}


Measured memory_bytes: 55732
#include <stdio.h>


int main(void){
    double a, b;
    scanf("%lf", &a);
    scanf("%lf", &b);
    
    if(a > b) {
    printf("GREATER");
    }

    else if(a == b) {
    printf("EQUAL");
    }

    else {
    printf("LESS");
    }

    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    if(n>=0)
    {
        if(n==m)
        {
            printf("Yes");
        }
        else
        {
            printf("No");
        }
    }
    printf("\n");
    return 0;
}


Measured memory_bytes: 256
N, D, A = map(int, input().split())
ys = []
for i in range(N):
    X, H = map(int, input().split())
    ys.append((X,-(-H//A)))
ys.sort(key=lambda x : x[0])
li = dmg = r = 0
hs = [0]*N
for i, (y, h) in enumerate(ys):
    while ys[li][0]+2*D < y:
        dmg -= hs[li]
        li += 1
    hs[i] = max(0, h-dmg)
    dmg += hs[i]
    r += hs[i]
print(r)

Measured memory_bytes: 75992
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n); i++)
using namespace std;
typedef long long ll;
int main(){
  int n;
  cin >> n;
  vector<int> p(n);
  rep(i,n) cin >> p[i];
  int ans =0;
  for(int i=0; i<(n-2);i++){
    if((p[i]>p[i+1])&(p[i+1]>p[i+2])) ans++;
    if((p[i]<p[i+1])&(p[i+1]<p[i+2])) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;cin>>N;
  int t=0,f=0,n=0;
  vector<int>A(N);
  for(int i=0;i<N;i++){int a;cin>>a;f+=(a%4==0);t+=(a%4==2);}n=N-f-t;
  
  if(n+(t!=0)>f+1)cout<<"No";
  else cout<<"Yes";
}

Measured memory_bytes: 640
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
  int s;
  cin >> s;
  int m = 0;
  unordered_set<int> set;
  int ai = s;
  set.insert(ai);

  for (int i = 2; i <= 1000000; i++) {
    if (ai % 2 == 0) {
      ai = ai / 2;
    } else {
      ai = 3 * ai + 1;
    }

    if (set.find(ai) != set.end()) {
      m = i;
      break;
    }
    set.insert(ai);
  }

  cout << m << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int w,h,x,y,r;
  scanf("%d%d%d%d%d",&w,&h,&x,&y,&r);

  if(x+r>w || x-r<0 || y+r>h || y-r<0){
    printf("No\n");
  }else{
    printf("Yes\n");
  }
  return 0;
}

Measured memory_bytes: 1824
#include <bits/stdc++.h>
using namespace std;
typedef long long Int;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,ans,num = 100000;
    cin >> n;
    vector<int> o(n/2),e(n/2);
    for(int i = 0;i < n/2;i ++){
        cin >> o[i];
        cin >> e[i];
    }
    int oc[2][2],ec[2][2];
    sort(o.begin(),o.end());
    sort(e.begin(),e.end());
    for(int i = 0;i < n/2;){
        int cnt = 0,mk = o[i];
        while(o[i] == mk && i < n/2){
            cnt ++;
            i ++;
        }
        if(cnt > oc[0][0]){
            oc[1][0] = oc[0][0];
            oc[0][0] = cnt;
            oc[0][1] = o[i-1];
        }else if(cnt > oc[1][0]){
            oc[1][0] = cnt;
            oc[1][1] = o[i-1];
        }
    }
    for(int i = 0;i < n/2;){
        int cnt = 0,mk = e[i];
        while(e[i] == mk && i < n/2){
            cnt ++;
            i ++;
        }
        if(cnt > ec[0][0]){
            ec[1][0] = ec[0][0];
            ec[0][0] = cnt;
            ec[0][1] = e[i-1];
        }else if(cnt > ec[1][0]){
            ec[1][0] = cnt;
            ec[1][1] = e[i-1];
        }
    }
    if(oc[0][1] != ec[0][1]) ans =n/2 - oc[0][0] + n/2 - ec[0][0];
    else ans = n/2 - oc[0][0] + n/2 - max(oc[1][0],ec[1][0]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
a = int(input())
s = []
for i in range(0,a) :
    d = input()
    s.append(d)
    

c1 = 0
c2 = 0
c3 = 0
c4 = 0

for i in range(0,len(s)) :
    if s[i] == "AC" :
        c1 += 1
    elif s[i] == "WA" :
        c2 += 1
    elif s[i] == "TLE" :
        c3 += 1
    elif s[i] == "RE" :
        c4 += 1
print("AC x",str(c1))
print("WA x",str(c2))
print("TLE x",str(c3))
print("RE x",str(c4))

Measured memory_bytes: 16320
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M = inpl()
cnts = [0]*N
pena = 0
for _ in range(M):
    p,s = input().split()
    p = int(p)-1
    if s == "WA" and cnts[p]!=-1:
        cnts[p] += 1
    elif s == "AC" and cnts[p]!=-1:
        pena += cnts[p]
        cnts[p] = -1


print(cnts.count(-1),pena)


Measured memory_bytes: 4840
import java.util.Scanner;

class Main {

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt();

        while(a!=0 && b!=0) // until either one of them is 0
        {
            int c = b;
            b = a%b;
            a = c;
        }

        System.out.println(a + b);


    }
}


Measured memory_bytes: 26344
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip>
using namespace std;
#define int long long


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

    double a,b,h,m; cin >> a >> b >> h >> m;
    double ax,ay,bx,by;
    double pi = acos(-1);
    bx = b * sin(2 * pi * m / 60);
    by = b * cos(2 * pi * m / 60);
    ax = a * sin(2 * pi * h / 12 + 2 * pi * m / 720);
    ay = a * cos(2 * pi * h / 12 + 2 * pi * m / 720);

    double ans;
    ans = pow((ax-bx)*(ax-bx) + (ay-by)*(ay-by),0.5);
    cout << setprecision(12) << ans << endl;
}

Measured memory_bytes: 4304
#include<bits/stdc++.h>
using namespace std;
int main(){
	//2 a or 4 b legs
	//X animals Y legs
	
	//a+b=X
	//2*a + 4*b = Y
	
	int x,y,a,b;
	cin>>x>>y;
	
	for(int i=0;i<=x;i++){
		a=i;
		b=x-i;
		if((2*a+4*b)==y){
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
}

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


//あらかじめ50層目までのバーガーの高さ、パティの数を計算しておく
ll h[51];
ll p[51];

void calh() {
    h[0] = 1;
    for(ll i=1; i<51; i++) {
        h[i] = 2*h[i-1] + 3;
    }
}

void calp() {
    p[0] = 1;
    for(ll i=1; i<51; i++) {
        p[i] = 2*p[i-1] + 1;
    }
}

//レベルnバーガーの下からx層までに食べるパティを
//再帰関数によって求める
ll calpp(ll n, ll x) {
    if(x <= n) return 0;
    if(n == 0) return 1;
    if(x < h[n-1]+2) return calpp(n-1, x-1);
    //if(x == h[n-1]+2) return calp(n-1, h[n-1]) + 1;
    if(x >= h[n-1]+2) return p[n-1] + 1 + calpp(n-1, x-(h[n-1]+2));
}

int main() {
    ll N, X;
    cin >> N >> X;
    calh();
    calp();

    cout << calpp(N, X) << endl;
    return 0;

}

Measured memory_bytes: 256
H, W = map(int, input().split())
S = [["."] + list(input()) + ["."] for _ in range(H)]
S = [["."]*(W+2)] + S + [["."]*(W+2)]

ans = "Yes"
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i][j] == "#":
            UDLR = [S[i-1][j], S[i+1][j], S[i][j-1], S[i][j+1]]
            if "#" in UDLR:
                pass
            else:
                ans = "No"
                break

print(ans)


Measured memory_bytes: 9132
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>

#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using namespace std;
using vi = vector<int64_t>;
using vvi = vector<vi>;

int main(int argc, const char * argv[]) {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    int64_t w,a,b;
    cin >> w >> a >> b;
    if(b>a){
        cout << (b-a-w>=0?b-a-w:0) << endl;
    }else{
        cout << (a-b-w>=0?a-b-w:0) << endl;
    }
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

namespace IO {
    template <typename _T>
    inline bool read (_T& x) {
        x = 0;
        _T y = 1;
        char c = getchar();
        while ((c < '0' || '9' < c) && c != EOF) {
            if (c == '-') y = -1;
            c = getchar();
        }
        if (c == EOF) return false;
        while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
        x *= y;
        return true;
    }

    template <typename _T>
    inline _T input () {
        _T x = 0, y = 1;
        char c = getchar();
        while ((c < '0' || '9' < c) && c != EOF) {
            if (c == '-') y = -1;
            c = getchar();
        }
        if (c == EOF) return 0;
        while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
        x *= y;
        return x;
    }
};
using namespace IO;

namespace modular {
    const int MOD = 1000000007;

    inline int add (int x, int y) { return (x += y) >= MOD ? x -= MOD : x; }

    inline void inc (int &x, int y) { (x += y) >= MOD ? x -= MOD : 0; }

    inline int mul (int x, int y) { return 1LL * x * y % MOD; }

    inline int qpow (int x, int y) {
        int ans = 1;
        for (; y; y >>= 1, x = mul(x, x)) if (y & 1) ans = mul(ans, x);
        return ans;
    }
};

#define reg register
#define MAX_N 3007
#define FIN(s) freopen(s, "r", stdin)
#define FOUT(s) freopen(s, "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, l, r) for(int i = l; i <= r; ++i)
#define lep(i, l, r) for(int i = l; i < r; ++i)
#define irep(i, r, l) for(int i = r; i >= l; --i)
#define ilep(i, r, l) for(int i = r; i > l; --i)
typedef long long ll;
typedef std::deque<int> deq;

ll N;

struct node {
    deq a, b;
};

node dfs (ll x, int p) {
    node ans;
    if (x == 0) return ans;
    if (x & 1LL) {
        ans = dfs((x - 1LL) >> 1, p + 1);
        ans.a.push_front(p);
        ans.b.push_front(p);
        return ans;
    } else {
        ans = dfs(x - 1LL, p + 1);
        ans.a.push_front(p);
        ans.b.push_back(p);
        return ans;
    }
}

int main () {
#ifdef LOCAL
    FIN("in");
#endif
    read(N);
    node res = dfs(N, 1);
    printf("%d\n", res.a.size() + res.b.size());
    while (!res.a.empty()) {
        printf("%d ", res.a.front());
        res.a.pop_front();
    }
    while (!res.b.empty()) {
        printf("%d ", res.b.front());
        res.b.pop_front();
    } puts("");
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define int long long int
#define endl "\n"
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(c) c.begin(), c.end()
 
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
 
typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
void solve() {
    int n, w, v;
    cin >> n >> w;
    pair<int, int> items[n+1];
    for (int i = 1; i <= n; i++) {
    	int wt, val;
    	cin >> wt >> val;
    	items[i] = {wt, val};
    }
    v = n*1000;
    int dp[n+1][v+1];
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= v; j++) {
    		dp[i][j] = dp[i-1][j];
    		if ((j > items[i].ss) && (dp[i-1][j-items[i].ss] > 0) && (dp[i-1][j-items[i].ss] + items[i].ff <= w)) {
    			if (dp[i][j] == 0)
    				dp[i][j] = dp[i-1][j-items[i].ss] + items[i].ff;
    			dp[i][j] = min(dp[i][j], dp[i-1][j-items[i].ss] + items[i].ff);
    		} else if (j == items[i].ss && (dp[i-1][j-items[i].ss] + items[i].ff <= w)) {
    			if (dp[i][j] == 0)
    				dp[i][j] = dp[i-1][j-items[i].ss] + items[i].ff;
    			dp[i][j] = min(dp[i][j], dp[i-1][j-items[i].ss] + items[i].ff);
    		}
    	}
    }
    for (int j = v; j >= 0; j--) {
    	if (dp[n][j] != 0) {
    		cout << j;
    		return;
    	}
    }
    cout << 0;
   //  for (int i = 1; i <= n; i++) {
   //  	for (int j = 1; j <= 100; j++) {
   // 			cout << dp[i][j] << " ";
   // 		}
   // 		cout << endl;
   // }
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int t = 1;
	// cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

Measured memory_bytes: 82540
n, m = map(int, input().split())


lst_sw = []
for _ in range(m):
    lst_sw.append(list(map(int, input().split())))
lst_p = list(map(int, input().split()))


ans = 0
for bits in range(2 ** n):
    judge = True
    for i in range(m):
        cnt_sw_on = 0
        for j in range(1, len(lst_sw[i])):
            sw = lst_sw[i][j]
            if (1 << (sw - 1)) & bits:
                cnt_sw_on += 1
        if cnt_sw_on % 2 != lst_p[i]:
            judge = False
            break
    if judge:
        ans += 1


print(ans)


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

typedef pair < int , int > Pi;

int main()
{
	int N;
	int V[100005];

	map < int , int > cnt[2];

	cin >> N;

	for ( int i = 0; i < N; i++ ) {
		cin >> V[i];
		cnt[i % 2][V[i]]++;
	}

	priority_queue < Pi > pq[2];

	pq[0].emplace(0, -1);
	pq[1].emplace(0, -2);

	for ( int i = 0; i < 2; i++ ) {
		for ( auto &x : cnt[i] ) {
			pq[i].emplace(x.second, x.first);
		}
	}

	Pi dat1 = pq[0].top();
	pq[0].pop();
	Pi sdat1 = pq[0].top();

	Pi dat2 = pq[1].top();
	pq[1].pop();
	Pi sdat2 = pq[1].top();
	
	if ( dat1.second == dat2.second ) {
		cout << min(N - sdat1.first - dat2.first, N - dat1.first - sdat2.first) << endl;
	} else {
		cout << N - dat1.first - dat2.first << endl;
	}

	return ( 0 );
}


Measured memory_bytes: 6520
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        // 入力データの取得
        Scanner scanner = new Scanner(System.in);
        String inputData = scanner.nextLine();
        scanner.close();

        //データの加工
        String[] editedInputData = inputData.split(" ");
        int smallerTax = Integer.parseInt(editedInputData[0]);
        int biggerTax = Integer.parseInt(editedInputData[1]);

        // 税抜き価格の算出
        double taxA = 0.08;
        double taxB = 0.10;
        int[][] taxAAndB = new int[1000][2];
        for (int index = 0; index < taxAAndB.length; index++) {
            taxAAndB[index][0] = (int) Math.floor((index + 1) * taxA);
            taxAAndB[index][1] = (int) Math.floor((index + 1) * taxB);
        }

        // 判定
        for (int index = 0; index < taxAAndB.length; index++) {
            if (taxAAndB[index][0] == smallerTax && taxAAndB[index][1] == biggerTax) {
                System.out.println(index + 1);
                return;
            }
        }

        System.out.println("-1");
        
    }

}

Measured memory_bytes: 24000
//2714 ???????????\ ???4
import java.util.Scanner;
    public class Main{
        int hozon=1;
        int ichi=0;
    
    public void solve(){
    Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
    while(N!=0){
            for(int cnt=0;cnt<N;cnt++){
            int k=sc.nextInt();
            if(k>=2){
            hozon++;
            }else if(k==1){
            ichi++;
            }
            }
            if(hozon>=2){
                System.out.println(hozon+ichi);
            }else{
                System.out.println("NA");
            }
            hozon=1;
            ichi=0;
            N=sc.nextInt();
        }
    }
    public static void main(String[] args){
        Main obj=new Main();
        obj.solve();
    }
}

Measured memory_bytes: 158308
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


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

	string s;
	cin >> s;

	int n, i, j, k, ct = 0;
	for (auto ch : s) {
		if (ch == 'o') ct++;
	}
	ct += (15 - s.length());

	if (ct >= 8) cout << "YES\n";
	else cout << "NO\n";

	return 0;
}



Measured memory_bytes: 888
#include <bits/stdc++.h>
#define int long long
#define uint unsigned int
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repr(i, a, b) for (int i = a; i >= b; i--)
#define all(a) (a).begin(), (a).end()
#define sz(a) (a).size()
#define pb(a) push_back(a)
#define eb(...) emplace_back(__VA_ARGS__)
#define mp(a, b) make_pair(a, b)
#define mt(...) make_tuple(__VA_ARGS__)
using namespace std;
using pii = pair<int, int>;
constexpr int MOD = 1000000007;
constexpr int INF = 1LL << 30;
constexpr double EPS = 1e-10;

int n;
int a[100010];
int used[100010];
int L, R;
int inv[100010];
int fac[100010];
int finv[100010];

void make() {
  inv[1] = 1;
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  for (int i = 2; i < 100010; i++) {
    inv[i] = MOD - (MOD/i)*inv[MOD%i]%MOD;
    fac[i] = fac[i-1]*i%MOD;
    finv[i] = finv[i-1]*inv[i]%MOD;
  }
}

int comb(int n, int k) {
  if (n < 0 || k < 0 || n < k) return 0;
  return fac[n]*finv[k]%MOD*finv[n-k]%MOD;
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  make();
  fill(used, used+100010, -1);
  cin >> n;
  rep(i, 0, n+1) {
    cin >> a[i];
    if (used[a[i]] >= 0) {
      L = used[a[i]];
      R = n - i;
    } else {
      used[a[i]] = i;
    }
  }

  rep(i, 1, n+2) {
    int sum = comb(n-1, i);
    (sum += comb(n-1, i-2)) %= MOD;
    (sum += comb(n-1, i-1)*2 % MOD) %= MOD;
    (sum += MOD - comb(L+R, i-1)) %= MOD;
    cout << sum << endl;
  }

  return 0;
}

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

const ll mod = 1e9 + 7;

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

int main() {
    ll n, k; cin >> n >> k;
    ll gcd[k+1] = {};
    for (int i = 1; i <= k; i++)
        gcd[i] = fpow(k / i, n);
    for (int i = k / 2; i >= 1; i--)
        for (int j = i + i; j <= k; j += i)
            gcd[i] -= gcd[j];
    for (int i = 1; i <= k; i++)
        gcd[i] = i * gcd[i] % mod;
    cout << accumulate(gcd + 1, gcd + 1 + k, 0LL) % mod;
}


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

typedef long long ll;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll LINF = 1e18;
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define MP make_pair
#define F first
#define S second
#define PB push_back
#define dump(x)  cout << #x << " = " << (x) << endl;	// debug
#define SZ(x) ((ll)(x).size())
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define RFOR(i, a, b) for (ll i = (a); i >= (b); i--)
#define ps(s) cout << #s << endl;
#define pv(v) cout << (v) << endl;
#define pvd(v) cout << setprecision(16) << (v) << endl;
#define ALL(a)  (a).begin(),(a).end()
#define RANGE(a, left, right)  (a).begin()+(left),(a).begin()+(right)	// left to (right-1)


int main() {
	int n;
	cin >> n;
	map<int, int> mp;
	FOR(i, 1, sqrt(n)) {
		FOR(j, 1, sqrt(n)) {
			FOR(k, 1, sqrt(n)) {
				mp[i*i + j * j + k * k + i * j + j * k + k * i]++;
			}
		}
	}
	FOR(i, 1, n) {
		pv(mp[i]);
	}
	return 0;
}

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

int main() {
  string s,t;
  cin >> s >> t;
  int count = 0;

  for(int i = 0; i < s.size(); i++){
    if(s.at(i) != t.at(i)){
      s.at(i) = t.at(i);
      count++;
    }
    else{
      continue;
    }
  }
  cout << count;
}

Measured memory_bytes: 3880
fun longList() = readLine()?.split(" ")?.map(String::toLong) ?: TODO()
fun main(args: Array<String>) {
    val (n, a, b) = longList()
    if (a > b) {
        println("0")
        return
    }
    if (n == 1L) {
        if (a != b) {
            println("0")
        } else {
            println("1")
        }
        return
    }
    if (n == 2L) {
        println("1")
        return
    }
    val free = n - 2
    val count = (b * free) - (a * free) + 1
    println(count.toString())
}

Measured memory_bytes: 37864
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int count;
  int N;
  cin>>N;
  vector<int> d(N);
  for(int i=0;i<N;i++){
    cin>>d.at(i);
  }

  vector<int> num(110,0);
  
  for(int i=0;i<N;i++){
    num.at(d.at(i))++;
  }
  for(int i=0;i<=100;i++){
    if(num.at(i)!=0) count++;
  }

  cout<<count<<endl;

}

Measured memory_bytes: 256
n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

distance = {
    1: lambda: sum([abs(x[i] - y[i]) for i in range(n)]),
    2: lambda: pow(sum([pow(abs(x[j] - y[j]), 2) for j in range(n)]), 1 / 2),
    3: lambda: pow(sum([pow(abs(x[j] - y[j]), 3) for j in range(n)]), 1 / 3),
    4: lambda: max([abs(x[i] - y[i]) for i in range(n)])
}

print(distance[1]())
print(distance[2]())
print(distance[3]())
print(distance[4]())



Measured memory_bytes: 5648
<?php
//error_reporting(0);
//$N = trim(fgets(STDIN));
list($W,$H,$x,$y) =  explode(" ",trim(fgets(STDIN)));
//$L =  explode(" ",trim(fgets(STDIN)));
$pat = 0;
if ($x*2==$W && $y*2==$H) {
  $pat=1;
}
printf("%f %d\n",$W*$H/2,$pat);


Measured memory_bytes: 4604
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main(){
    ll n; cin>>n;
    bool ifokay=true;
    char last;
    map<string, ll> m;
    rep(i,n){
        string s; cin>>s;
        if(m[s]>0) ifokay=false;
        m[s]=1;
        if(i==0) last=s[s.size()-1];
        else{
            if(last!=s[0]) ifokay=false;
            last=s[s.size()-1];
        }
    }
    if(ifokay) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <chrono>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define eps 1e-9

typedef long long ll;

using namespace std;

const int mod = 1e9+7;
const int N = 1e5+5;
int a[N];

int main()

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

    int ans = 0;
    string t = "CODEFESTIVAL2016";
    string s;

    cin >> s;

    for (int i = 0; i < s.size(); i++) {

        if (s[i] != t[i]) ans++;
    }

    cout << ans;

    return 0;
}


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


from sys import stdin
import itertools



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

# read data for n sequences.
temp = stdin.readline().split()
N = int(temp[0])
X = int(temp[1])

data = []
write = stdin.readline().split()
for i in range(N):
    data.append(int(write[i]))
    
count = 1
dis = 0

for d in data:
    dis += d
    if dis <= X:
        count += 1
    else:
        break

print(count)

Measured memory_bytes: 3064
from sys import stdin,stdout
n,k=map(int,stdin.readline().split())
h=[int(l) for l in stdin.readline().split()]
dp=[0,abs(h[0]-h[1])]
for i in range(2,n):
    ans=10**15
    num=i-k
    if num<0:
        num=-1
    else:
        num-=1
    for j in range(i-1,num,-1):
        ans=min(abs(h[i]-h[j])+dp[j],ans)
    dp.append(ans)
print(dp[n-1])


Measured memory_bytes: 57820
#include <bits/stdc++.h>
using namespace std;
int a,b,m;
int aa[100010],bb[100010];
int x[100010],y[100010],c[100010];
int main() {
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin>>a>>b>>m;
	int ma=1e9,mb=1e9;
	for(int i=0; i<a; i++) {
		cin>>aa[i];
		ma=min(ma,aa[i]);
	}
	for(int i=0; i<b; i++) {
		cin>>bb[i];
		mb=min(mb,bb[i]);
	}
	ma+=mb;
	int mn=1e9;
	for(int i=0; i<m; i++) {
		cin>>x[i]>>y[i]>>c[i];
		mn=min(aa[x[i]-1]+bb[y[i]-1]-c[i],mn);
	}
	cout<<min(ma,mn)<<endl;
	return 0;
}/*
*/

Measured memory_bytes: 2176
package main

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

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	i, err := strconv.Atoi(readString())
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() []int {
	n := readInt()
	return readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func vi(n int, args ...int) []int {
	res := make([]int, n)
	if len(args) == 0 {
		return res
	}
	v := args[0]
	if v == 0 {
		return res
	}
	for i := 0; i < n; i++ {
		res[i] = v
	}
	return res
}

func vvi(n int, args ...int) [][]int {
	res := make([][]int, n)
	m := n
	if len(args) > 0 {
		m = args[0]
	}
	v := 0
	if len(args) > 1 {
		v = args[1]
	}
	for i := 0; i < n; i++ {
		res[i] = vi(m, v)
	}
	return res
}

func main() {
	defer stdout.Flush()

	// readString() string
	// readInt() int
	// readIntSlice(n int) []int
	// readLengthAndSlice() []int
	a := readInt()
	b := readInt()

	if a <= 8 && b <= 8 {
		println("Yay!")
	} else {
		println(":(")
	}

}


Measured memory_bytes: 640
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

class UnionFind():
  def __init__(self,sz):
    self.sz=sz
    self.data=[-1]*sz

  def unite(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if x==y:
      return False
    if self.data[x]>self.data[y]:
      x,y=y,x
    self.data[x]+=self.data[y]
    self.data[y]=x
    return True

  def find(self,k):
    if self.data[k]<0:
      return k
    self.data[k]=self.find(self.data[k])
    return self.data[k]

  def size(self,k):
    return -self.data[self.find(k)]

def main():
  n,m,k=LI()
  uf=UnionFind(n)

  friends=[set() for _ in range(n)]
  for _ in range(m):
    a,b=LI()
    a-=1
    b-=1
    friends[a].add(b)
    friends[b].add(a)
    uf.unite(a,b)

  blocks=[set() for _ in range(n)]
  for _ in range(k):
    a,b=LI()
    a-=1
    b-=1
    blocks[a].add(b)
    blocks[b].add(a)

  # for i in range(n):
  #   print(uf.size(i),friends[i])

  ans=[0]*n
  for i in range(n):
    par=uf.find(i)
    _ans=uf.size(i)-1-len(friends[i])
    for x in blocks[i]:
      if par==uf.find(x):
        _ans-=1

    ans[i]=_ans

  return ' '.join([str(x) for x in ans])

# main()
print(main())


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

int main(){
  int N;
  cin >> N;
  
  vector<int> vec(N);
  for(int i = 0;i < N;i++)
    cin >> vec.at(i);
  sort(vec.begin(),vec.end());

  int count = 0;

  for(int i = 0;i < N;i++){
    for(int j = 0;j < i;j++){
      for(int k = 0;k < j;k++){
	if(vec.at(k) != vec.at(j) && vec.at(j) != vec.at(i) && vec.at(k)+vec.at(j) > vec.at(i)){
	  count++;
	}
      }
    }
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 3604
#[allow(unused_macros)]
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( std :: io :: BufReader :: new ( stdin . lock ( ) ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! input_inner { ( $ next : expr ) => { } ; ( $ next : expr , ) => { } ; ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! read_value { ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) } ; ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 } ; ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }

#[allow(unused_macros)]
macro_rules ! vec_md { ( $ init : expr ; $ ( $ dim : expr ) ;* ) => { vec_md ! ( $ ( $ dim ) ;* => $ init ) } ; ( $ head : expr ; $ ( $ tail : expr ) ;* => $ init : expr ) => { vec ! [ vec_md ! ( $ ( $ tail ) ;* => $ init ) ; $ head ] } ; ( $ head : expr => $ init : expr ) => { vec ! [ $ init ; $ head ] } ; }

#[allow(dead_code)]
pub const M: u64 = 1_000_000_007;

fn main() {
    input! {
        n: usize, k: usize,
        a: [usize; n]
    }

    let mut dp = vec_md![0u64;n+1;k+1];
    dp[0][k] = 1;
    for i in 0..n {
        let cum = Cum::new(&dp[i]);
        for j in 0..k+1 {
            dp[i+1][j] += cum.sum(j, std::cmp::min(j+a[i], k)+1);
            dp[i+1][j] %= M;
        }
    }
    println!("{}", dp[n][0]);
}

#[derive(Debug)]
#[allow(dead_code)]
struct Cum {
    s: Vec<u64>,
}
#[allow(dead_code)]
impl Cum {
    fn new(a: &Vec<u64>) -> Cum {
        let mut s = vec![0; a.len() + 1];
        for i in 0..a.len() {
            s[i + 1] = (s[i] + a[i]) % M;
        }
        Cum { s: s }
    }
    #[doc = " [l,r)"]
    fn sum(&self, l: usize, r: usize) -> u64 {
        sub_mod(self.s[r], self.s[l], M)
    }
}

#[allow(dead_code)]
fn sub_mod(a: u64, b: u64, m: u64) -> u64 {
    let mut tmp = (a as i64 - b as i64) % m as i64;
    if tmp < 0 {
        tmp += m as i64;
    }
    tmp as u64
}

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

using namespace std;

int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  int64_t a, b;
  std::cin >> a >> b;
  std::cout << (a - 1) * (b - 1) << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
    int H,i,j,P[10][5],Q[10][5],S,a,b;
    for(;scanf("%d",&H),H;){
        S=0;
        for(i=0;i<10;i++)for(j=0;j<5;j++)P[i][j]=-1;
        for(i=0;i<10;i++)for(j=0;j<5;j++)Q[i][j]=-1;
        
        for(i=10-H;i<10;i++)scanf("%d %d %d %d %d",&P[i][0],&P[i][1],&P[i][2],&P[i][3],&P[i][4]);
        
        //for(i=0;i<10;i++){for(j=0;j<5;j++)printf("%d ",P[i][j]);printf("\n");}
        b=0;
        for(;b==0;){
            b=1;
        for(i=0;i<10;i++)if(P[i][0]==P[i][1]&&P[i][0]==P[i][2]&&P[i][0]==P[i][3]&&P[i][0]==P[i][4]&&P[i][0]!=-1){
            S+=P[i][0]*5;
            P[i][0]=-1; P[i][1]=-1; P[i][2]=-1; P[i][3]=-1; P[i][4]=-1;
        }
        for(i=0;i<10;i++)if(P[i][0]==P[i][1]&&P[i][0]==P[i][2]&&P[i][0]==P[i][3]&&P[i][0]!=-1){
            S+=P[i][0]*4;
            P[i][0]=-1; P[i][1]=-1; P[i][2]=-1; P[i][3]=-1;
        }
        for(i=0;i<10;i++)if(P[i][0]==P[i][1]&&P[i][0]==P[i][2]&&P[i][0]!=-1){
            S+=P[i][0]*3;
            P[i][0]=-1; P[i][1]=-1; P[i][2]=-1;
        }
        for(i=0;i<10;i++)if(P[i][1]==P[i][2]&&P[i][1]==P[i][3]&&P[i][1]==P[i][4]&&P[i][1]!=-1){
            S+=P[i][1]*4;
            P[i][4]=-1; P[i][1]=-1; P[i][2]=-1; P[i][3]=-1;
        }
        for(i=0;i<10;i++)if(P[i][1]==P[i][2]&&P[i][1]==P[i][3]&&P[i][1]!=-1){
            S+=P[i][1]*3;
            P[i][1]=-1; P[i][2]=-1; P[i][3]=-1;
        }
        for(i=0;i<10;i++)if(P[i][2]==P[i][3]&&P[i][2]==P[i][4]&&P[i][2]!=-1){
            S+=P[i][2]*3;
            P[i][3]=-1; P[i][4]=-1; P[i][2]=-1;
        }
        //for(i=0;i<10;i++){for(j=0;j<5;j++)printf("%d ",P[i][j]);printf("\n");}
        a=0;
        for(;;){
            //for(i=0;i<10;i++)for(j=0;j<5;j++)if(Q[i][j]!=P[i][j])goto yare;
            if(a==1)break;
            a=1;
            yare:;
            
            for(i=0;i<9;i++)for(j=0;j<5;j++)if(P[i][j]!=-1&&P[i+1][j]==-1){
                P[i+1][j]=P[i][j];P[i][j]=-1;a=0;b=0;
            }
            
        //for(i=0;i<10;i++)for(j=0;j<5;j++)Q[i][j]=P[i][j];
        }
        
        //for(i=0;i<10;i++){for(j=0;j<5;j++)printf("%d ",P[i][j]);printf("\n");}
            
            
    }
        printf("%d\n",S);
    }
    return 0;
}

Measured memory_bytes: 1028
data = [[[0 for r in range(10)] for f in range(3)] for b in range(4)]

n = int(input())
for nc in range(n):
    (b, f, r, v) = [int(i) for i in input().split()]
    data[b - 1][f - 1][r - 1] += v



for b in range(4):
    for f in range(3):
        for r in range(10):
            print(' {0}'.format(data[b][f][r]), end='')
        print()
    print('#' * 20) if b < 4 -1 else print(end='')

Measured memory_bytes: 6724
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
ll f[maxn],len1,len2;
ll s1[maxn],s2[maxn],n,k;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
	for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
inline void sol(){
	n=read();k=read();int s=-1;
	for(register int i=1;i<=n;++i){
		f[i]=read();
		if(f[i]>=0&&s==-1)s=i;
	}if(s==-1)s=n+1;
	for(register int i=s;i<=n;++i)s1[++len1]=f[i];
	for(register int i=s-1;i;--i)s2[++len2]=abs(f[i]);
	ll ans=9999999999;
	for(register int i=1;i<=len1;++i){
		if(i>k)break;
		if(i==k)ans=min(ans,s1[i]);
		else if(k-i<=len2)ans=min(ans,(s1[i]<<1)+s2[k-i]);
	}
	for(register int i=1;i<=len2;++i){
		if(i>k)break;
		if(i==k)ans=min(ans,s2[i]);
		else if(k-i<=len1)ans=min(ans,(s2[i]<<1)+s1[k-i]);
	}cout<<ans<<endl;
}
int main(){
	//freopen("shit.in","r",stdin);
	//freopen("shit.out","w",stdout);
	sol();
	return 0;
}

Measured memory_bytes: 1792
INF, MOD = float("inf"), 1e9 + 7
MAX, MIN = -INF, INF
dx1, dy1, dx2, dy2 = [-1, 0, 1, 0], [0, -1, 0, 1], [-1, 0, 1, -1, 1, -1, 0, 1], [-1, -1, -1, 0, 0, 1, 1, 1]

def get_int():
    return int(input())

def get_int_list():
    return list(map(int, input().split()))

def mins(x, y):
    x = min(x, y)

def maxs(x, y):
    x = max(x, y)

while(True):
    try:
        n = get_int()
        a = get_int_list()
        print(*(a[::-2] + a[1::2]) if n % 2 else a[::-2] + a[::2])
    except EOFError:
        exit()


Measured memory_bytes: 25156
///
// File:  alds1_10_a.cpp
// Author: ymiyamoto
//
// Created on Tue Oct 17 00:57:42 2017
//

#include <cstdint>
#include <iostream>

using namespace std;
#define SIZE 100
static uint64_t mem[SIZE];

uint64_t fib(uint32_t n)
{
  if (n == 0) {
    return mem[0] = 1;
  } else if (n == 1) {
    return mem[1] = 1;
  } else {
    uint64_t n1, n2;

    if (mem[n - 2] == 0) {
      n2 = mem[n - 2] = fib(n - 2);
    } else {
      n2 = mem[n - 2];
    }

    if (mem[n - 1] == 0) {
      n1 = mem[n - 1] = fib(n - 1);
    } else {
      n1 = mem[n - 1];
    }
    return n1 + n2;
  }
}

int32_t main()
{
  uint32_t n;
  cin >> n;

  cout << fib(n) << endl;
  return 0;
}

Measured memory_bytes: 3088
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
const long long INFLL = 1LL << 60;
const int INFINT = 1 << 30;
const long long MOD = 1e9 + 7;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int A, B;
    cin >> A >> B;
    cout << (B + A - 3) / (A - 1) << endl;
}


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

#define ll long long
#define lli long long int
#define loop(i,x,n) for(lli i=x; i<=n; i++)
#define rloop(i,n,x) for(lli i=n; i>=x; i--)

typedef vector<ll> v64;
typedef vector<pair<ll,ll>> vp64;
typedef vector<bool> vbo;
typedef set<ll> s64;
typedef set<bool> sbo;
typedef unordered_set<ll> us64;
typedef map<ll,ll> m64;
typedef unordered_map<ll,ll> um64;

int main(){
    long long n;
    cin>>n;
    // ll ans = 0;
    // if(n&1){
    //     // n--;
    //     ans = ((n-1)/2);
    //     ans *= n;
    //     // ans++;
    // }   
    // else{
    //     ans = (n/2);
    //     ans*=n-1;
    // }
    n--;
    cout<<((n)*(n+1))/2;
    return 0;
}

Measured memory_bytes: 256