akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define modulo 998244353
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 10000000000000000


int main(){
	
	int A,B,C;
	cin>>A>>B>>C;
	
	if(A==B&&B==C&&A%2==0){
		cout<<-1<<endl;
		return 0;
	}
	
	int ans = 0;
	while(A%2==0&&B%2==0&&C%2==0){
		int a = B/2 + C/2;
		int b = A/2+C/2;
		int c = A/2+B/2;
		A=a;
		B=b;
		C=c;
		ans++;
	}
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
#include<iostream>
#include<string>
using namespace std;
#define rep(i, n) for (int i = 0; i <(int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
int main(){
   int n;cin>>n;
   int a,b;cin>>a>>b;
   if((abs(a-b)-1)%2!=0)cout<<"Alice"<<endl;
   else cout<<"Borys"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
template<class T, class Compare = less<T> >
using MaxHeap = priority_queue<T, vector<T>, Compare>;
template<class T, class Compare = greater<T> >
using MinHeap = priority_queue<T, vector<T>, Compare>;
using llong = long long;


llong n, k, q;
llong a[100005];
llong cnt[100005];

int main() {
    cin >> n >> k >> q;
    for (int i = 0; i < q; i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }

    for (int i = 1; i <= n; i++) {
        llong pnt = k - (q - cnt[i]);

        if (pnt <= 0) cout << "No" << endl;
        else cout << "Yes" << endl;
    }

    return 0;
}


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

#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#define dumpv(...)
#endif

#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;

void solve() {
  int H, W, h, w;
  cin >> H >> W >> h >> w;
  if (H % h == 0 && W % w == 0) {
    cout << "No" << endl;
    return;
  }
  if (H % h != 0) {
    vector<vector<int>> m(H, vector<int>(W, -H));
    for (int y = 0; y < H; y += h) {
      rep(x, W) m[y][x] = H * (h - 1) - 1;
    }
    cout << "Yes" << endl;
    rep(y, H) {
      rep(x, W) cout << m[y][x] << " ";
      cout << endl;
    }
  } else {
    vector<vector<int>> m(H, vector<int>(W, -W));
    for (int x = 0; x < W; x += w) {
      rep(y, H) m[y][x] = W * (w - 1) - 1;
    }
    cout << "Yes" << endl;
    rep(y, H) {
      rep(x, W) cout << m[y][x] << " ";
      cout << endl;
    }
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  // freopen("temp.1", "r", stdin);
  solve();
  return 0;
}

Measured memory_bytes: 2432
/*
 Author:Alokit Kumar
   */
  #include<bits/stdc++.h>
  using namespace std;
  #define int long long 
  int32_t main()
  {
    int n,i,j,k,l;
    cin>>n;
    int a[n+1],b[n+1],c[n];
    for(i=1;i<=n;i++) cin>>a[i];
    for(i=1;i<=n;i++) cin>>b[i];
    for(i=1;i<n;i++) cin>>c[i];
    int s=b[a[1]];
    for(i=2;i<=n;i++)
    {
      s+=b[a[i]];
      if((a[i]-1)==a[i-1])
       s+=c[a[i-1]];
    }
    cout<<s;
  }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  loop(i,0,n)
#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define vi vector<int>
#define vl vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>

int main(){
    int n;
    cin>>n;
    string ans="Yes";
    vl v(n);
    rep(i,n)cin>>v[i];
    ll int m=0;
    rep(i,n){
        if(v[i]>m)v[i]--;
        else if(v[i]<m){
            ans="No";
            break;
        }
        if(v[i]>m)m=v[i];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const ll inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;

int N, M, ans, cnt;

vector<vector<int>> G;
vector<bool> visited;

void dfs(int now)
{
    visited[now] = true;
    cnt++;
    if (cnt == N)
    {
        ans++;
    }
    for (int i = 0; i < G[now].size(); i++)
    {
        int next = G[now][i];
        if (visited[next] == false)
            dfs(next);
    }
    visited[now] = false;
    cnt--;
}

int main()
{
    cin >> N >> M;
    G = vector<vector<int>>(N);
    visited = vector<bool>(N, false);
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        //cout << a << " " << b << endl;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(0);
    cout << ans << endl;
}

Measured memory_bytes: 256
N = int(input())

result = (1 + N) * N / 2

n3 = (N // 3)
sum3 = (3 + 3 * n3) * n3 / 2

n5 = (N // 5)
sum5 = (5 + 5 * n5) * n5 / 2

n15 = (N // 15)
sum15 = (15 + 15 * n15) * n15 / 2

print(int(result - sum3 - sum5 + sum15))

Measured memory_bytes: 61904
import java.io.InputStream;
import java.io.IOException;
import java.util.NoSuchElementException;

public class Main {
    public static void main(String[] args) {
        final MyScanner sc = new MyScanner();
        final int a = sc.nextInt();
        final int answer = a + a * a + a * a * a;
        System.out.println(answer);
    }
}

class MyScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int pointer = 0;
    private int bufLength = 0;

    private boolean hasNextByte() {
        if (pointer < bufLength) {
            return true;
        } else {
            pointer = 0;
            try {
                bufLength = in.read(buffer);
            } catch (final IOException e) {
                e.printStackTrace();
            }
            if (bufLength <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte()) {
            return buffer[pointer++];
        } else {
            return -1;
        }
    }

    private static boolean isNumberChar(final int c) {
        return '0' <= c && c <= '9';
    }

    private static boolean isPrintableChar(final int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[pointer])) {
            pointer++;
        }
        return hasNextByte();
    }

    public String next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        final StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        long num = 0;
        boolean isNegative = false;
        int b = readByte();
        if (b == '-') {
            isNegative = true;
            b = readByte();
        }
        if (!isNumberChar(b)) {
            throw new NumberFormatException();
        }
        while (true) {
            if (isNumberChar(b)) {
                num *= 10;
                num += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return isNegative ? -num : num;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        final long temp = nextLong();
        if (temp < Integer.MIN_VALUE || Integer.MAX_VALUE < temp) {
            throw new NumberFormatException();
        }
        return (int) temp;
    }

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


Measured memory_bytes: 32376
using System;

public class Program
{
    public static long loop;

    static long n;

    static long[] l;

    static long lMax = 1;
    static long lMin = 1000;

    static string output;

    public static void Main(string[] args)
    {
        loop = 0;

        Input();
        Proc();
        Output();
    }

    static void Input()
    {
        string[] input = null;

        // スペース区切りの整数の入力(横、個別)
        input = Console.ReadLine().Split(' ');

        n = long.Parse(input[0]);

        // スペース区切りの整数の入力(横、配列)
        input = Console.ReadLine().Split(' ');

        l = new long[n];
        for (long idx = 0; idx < n; idx++)
        {
            l[idx] = long.Parse(input[idx]);
        }
    }

    static void Proc()
    {

        Array.Sort(l);

        long result = 0;

        for (long idxA = 0; idxA < n - 2; idxA++)
        {
            long a = l[idxA];

            for (long idxB = idxA + 1; idxB < n - 1; idxB++)
            {
                long b = l[idxB];

                long idxResult = BinarySearch(ref l, idxB, n, a + b);
                result += idxResult - idxB;
            }
        }

        output = result.ToString();
    }

    static long BinarySearch(ref long[] searchArray, long idxLeft, long idxRight, long targetValue)
    {
        if (idxLeft >= idxRight - 1)
        {
            return idxLeft;
        }

        long idxNow = (idxLeft + idxRight) / 2;
        long arrayValue = searchArray[idxNow];

        if (arrayValue < targetValue)
        {
            idxLeft = idxNow;
        }
        else
        {
            idxRight = idxNow;
        }

        long result = BinarySearch(ref searchArray, idxLeft, idxRight, targetValue);

        return result;
    }

    static void Output()
    {
        // 出力
        Console.WriteLine(output);
        output = string.Empty;
    }
}


Measured memory_bytes: 11348
#include <stdio.h>
 
int main()
{
  int r[200000];
  int n, i, j, max, min;
   
  scanf("%d", &n);
   
  for( i = 0; i < n ; i++ )
  {
    scanf("%d\n", &r[i] );
  }
   
  min = r[0];
  max = r[1] - r[0];
  for (j = 1; j <= n-1 ; j++)
  {
   
    if ( max < r[j] -min )
    {
      max = r[j] - min;
    }
    if ( min > r[j] )
    {
      min = r[j];
    }
     
  }
   printf("%d\n", max);
   
  return 0;
}

Measured memory_bytes: 3484
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n,h[20],c=0; cin>>n;
  for(int i=0;i<n;i++){
    cin>>h[i];
    bool f=true;
    for(int j=0;j<i;j++) if(h[i]<h[j]){f=false; break;}
    if(f) c++;
  }
  cout<<c;
}

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

#define ll long long
#define pb push_back
#define pf push_front
#define mp make_pair
#define endl "\n" 
#define all(c) c.begin(),c.end()
#define present(c,element) (c.find(element)!=c.end())
#define cpresent(c,element) (find(c,element)!=c.end())
#define fi(i,n) for(int i=0;i<int(n);i++)
#define tr(i,a) for(auto i:a)
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
const double PI=acos(-1);
const ll mod=1e9+7;



int32_t main()
{
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);

int test=1;
//cin>>test;
while(test--)
{
	ll n,a,b,c;
	cin>>n>>a>>b>>c;
	string s[n];
	vector<char> v;
	for(int i=0;i<n;i++)
		cin>>s[i];
	for(int i=0;i<n;i++)
	{
		if(s[i]=="AB")
		{
			if(a==0&&b==0){cout<<"No\n";return 0;}
			else if(a==1&&b==1&&i<n-1)
			{
				if(s[i+1]=="AC"){a+=1;b-=1;v.pb('A');}
				else {a-=1;b+=1;v.pb('B');}
			}
			else {if(a>b){a-=1;b+=1;v.pb('B');}else{a+=1;b-=1;v.pb('A');}}
		}
		else if(s[i]=="AC")
		{
			if(a==0&&c==0){cout<<"No\n";return 0;}
			else if(a==1&&c==1&&i<n-1)
			{
				if(s[i+1]=="AB"){a+=1;c-=1;v.pb('A');}
				else {a-=1;c+=1;v.pb('C');}
			}
			else {if(a>c){a-=1;c+=1;v.pb('C');}else{a+=1;c-=1;v.pb('A');}}
		}
		else
		{
			if(c==0&&b==0){cout<<"No\n";return 0;}
			else if(c==1&&b==1&&i<n-1)
			{
				if(s[i+1]=="AC"){c+=1;b-=1;v.pb('C');}
				else {c-=1;b+=1;v.pb('B');}
			}
			else {if(c>b){c-=1;b+=1;v.pb('B');}else{c+=1;b-=1;v.pb('C');}}
		}
	}
	cout<<"Yes\n";
	for(int i=0;i<n;i++)
		cout<<v[i]<<endl;
	
}
return 0;
}










Measured memory_bytes: 6924
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main(void){
	for(;;){
        int t,n;
        cin>>t;
        if(t==0)break;
        cin>>n;
        int a,b;
        int w=0;
        for(int i=0;i<n;i++){
            cin>>a>>b;
            w+=b-a;
        }
        if(w>=t)cout<<"OK"<<endl;
        else cout<<t-w<<endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,j,n) for(int i = j; i < n; i++)
#define RFOR(i,j,n) for(int i = j-1; i >= n; i--)
#define PREC(n) fixed << setprecision(n)
#define print_array(v) REP(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define _LIBCPP_DEBUG 0
using namespace std;
int64_t MOD = 1000000007;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  bool f = false;
  if(abs(c - a) <= d) f = true;
  if(abs(b - a) <= d && abs(c - b) <= d) f = true;
  YesorNo(f);
  return 0;
}
//templete by private_yusuke

Measured memory_bytes: 256
using System;
using System.Collections.Generic;

namespace C
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse (Console.ReadLine ());
            var hashSet = new HashSet<string> (N);
            for (var i = 0; i < N; i++) {
                hashSet.Add (Console.ReadLine ());
            }
            Console.WriteLine (hashSet.Count);
        }
    }
}


Measured memory_bytes: 41068
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int M = 10000001;
ll a[M];
int main() {
    int N;
    cin >> N;
    fill(a, a + M, 1);
    for (ll i = 2; i < M; i++) {
        for (ll j = 1; i * j < M; j++) {
            a[i * j]++;
        }
    }
    ll ans = 0;
    for (ll i = 1; i <= N; i++) {
        ans += i * a[i];
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 81752
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ULL = unsigned long long;
using LL = long long;
using pii = pair<int, int>;
const int MAX_M = 2e5;
int N, M, K;
vector<int> books_A, books_B;
LL pref_sum_B[MAX_M + 1];


int main()
{
    cin.sync_with_stdio(0);

    cin >> N >> M >> K;

    for (int i = 0; i < N; ++i)
    {
        int book_A;
        cin >> book_A;

        books_A.emplace_back(book_A);
    }
    for (int i = 0; i < M; ++i)
    {
        int book_B;
        cin >> book_B;

        books_B.emplace_back(book_B);
        if (i == 0)
        {
            pref_sum_B[i] = book_B;
        }
        else
        {
            pref_sum_B[i] = pref_sum_B[i - 1] + book_B;
        }
    }

    LL cur_pref_sum_A = 0;
    int res_nr_books = 0;
    for (int i = 0; ; ++i)
    {
        res_nr_books = max(res_nr_books, i + int(upper_bound(pref_sum_B, pref_sum_B + M, K - cur_pref_sum_A) - pref_sum_B));
        if (i == N || cur_pref_sum_A + books_A[i] > K)
        {
            break;
        }
        cur_pref_sum_A += books_A[i];
    }

    cout << res_nr_books;
}

Measured memory_bytes: 6620
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>

#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define all(v) (v).begin(), (v).end()
#define rev(s) (s).rbegin(), (s).rend()
#define MP make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;

int ytoi(int y){
	return (y*365+y/4-y/100+y/400);
}

int md[] = {0, 31, 28, 31, 30, 31, 30,
			31, 31, 30, 31, 30, 31};

int daycount(int y, int m, int d){
	int res = 0;
	res += ytoi(y-1);
	res += md[m-1];
	res += d;
	res += (((y%4 == 0 && y%100) || y%400 == 0) && m >= 3);

	return res;
}

int main(){
	for(int i = 1; i <= 12; i++) md[i] += md[i-1];

	int y1, m1, d1, y2, m2, d2;
	while(cin >> y1 >>m1 >> d1 >> y2 >> m2 >> d2, y1 >= 0){
		cout << daycount(y2, m2, d2) - daycount(y1, m1, d1) << endl;
	}

	return 0;
}

Measured memory_bytes: 1160
# coding:utf-8
# C - Grand Garden

N = int(input())
h =  [int(i) for i in input().split()]
h += [0]
ans = 0
add = False

while True:
    mini_ans = 0
    for i in range(N+1):
        if h[i] != 0:
            h[i] -= 1
            add = True
        else:
            if add:
                mini_ans += 1
            add = False
    if mini_ans == 0:
        break
    else:
        ans += mini_ans

print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
using namespace std;
const double PI = acos(-1.0);
const string alp = "abcdefghijklmnopqrstuvwxyz";
const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string HEX = "0123456789ABCDEF";
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

int main(void) {
    int n,z,w;
    cin >> n >> z >> w;
    vector <int> a;
    REP(i,n){
        cin >> z;
        a.push_back(z);
    }
    int m = 0;
    if (n!=1){
        if (m<abs(a[n-1]-w)) m = abs(a[n-1]-w);
        if (m<abs(a[n-1]-a[n-2])) m = abs(a[n-1]-a[n-2]);
    } else {
        m = abs(a[n-1]-w);
    }
    cout << m;
}


Measured memory_bytes: 256
import java.util.*;
import java.lang.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String str = sc.next();
    int n = str.length();
    str = str.substring(0,n-1);
    n = n-1 ;
    String str1,str2;
    int m = 0;
    if(n%2==1){
      str = str.substring(0,n-1);
    }
    for(int a=0;a<=n/2;a++){
      m = str.length();
      str1 = str.substring(0,m/2);
      str2 = str.substring(m/2,m);
      if(str1.equals(str2)){
        System.out.println(m);
        break;
      }else{
        str = str.substring(0,m-2);
      }
    }
  }
}


Measured memory_bytes: 23764
#include "bits/stdc++.h"
using namespace std;
#define int long long
int mod=1e9+7;
 
signed main(){
	int h,w,k;
	cin>>h>>w>>k;
	vector<string> a(h);
	for(int i=0;i<h;i++)cin>>a[i];
	
	queue<int> qx;
	queue<int> qy;
	vector<vector<int> > used(h,vector<int>(w,-1));
	
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(a[i][j]=='S'){
				qx.push(j);
				qy.push(i);
				used[i][j]=0;
			}
		}
	}
	
	int px[]={1,0,-1,0};
	int py[]={0,-1,0,1};
	
	int ans=1e9;
	
	
	while(!qx.empty()){
		int x=qx.front();
		int y=qy.front();
		qx.pop();
		qy.pop();
		if(used[y][x]<=k)ans=min(ans,min(x,min(y,min(w-x-1,h-y-1))));
		for(int i=0;i<4;i++){
			int nx=x+px[i];
			int ny=y+py[i];
			if(nx>=0&&ny>=0&&nx<w&&ny<h&&a[ny][nx]=='.'&&used[ny][nx]==-1){
				used[ny][nx]=used[y][x]+1;
				qx.push(nx);
				qy.push(ny);
			}
		}
	}
	
	int tmp=1;
	if(ans%k!=0)tmp++;
	tmp+=ans/k;
	cout<<tmp<<endl;
}

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

ll mod=1e9+7;

ll add(ll a,ll b){
  return (a+b+mod+mod)%mod;
}

ll mul(ll a,ll b){
  return (a*b)%mod;
}

ll mpow(ll a,ll b){
  ll res=1;
  for(int i=0;i<b;i++)res=mul(res,a);
  return res;
}


ll d,s,t[301];
ll sum=0;


int dp[2][2][900001];

int main(){
  
  cin>>d;
  for(int i=0;i<d;i++){
    cin>>t[i];
    sum+=t[i];
  }

  cin>>s;
  dp[0][0][0]=1;

  ll ans=0;
  
  for(int i=0;i<=d;i++){
    int ai=i&1;
    int bi=1-ai;
    fill( (ll*) dp[bi], (ll*)dp[bi+1],0);
    for(int j=0;j<2;j++){
      for(int k=0;k<=s;k++){

        if(i==d){
          if(j==0)ans=add(ans, mul( dp[ai][j][k],mpow(s-k,d) ) );
          else ans=add(ans, -mul( dp[ai][j][k],mpow(s-k,d) ) );
        }
        
        dp[bi][j][k]+=dp[ai][j][k];
        dp[bi][j][k]%=mod;
        if(k+t[i]<=s){
          dp[bi][1-j][k+t[i]]+=dp[ai][j][k];
          dp[bi][1-j][k+t[i]]%=mod;
        }
        
      }
    }
  }
  
  cout<<ans<<endl;
  
  return 0;
}

Measured memory_bytes: 15224
#include "bits/stdc++.h"
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/operators.hpp>
#include <boost/dynamic_bitset.hpp>
namespace adaptor = boost::adaptors;
using index_t = std::size_t;

void Main()
{
	std::int64_t N;
	int M;
	std::cin >> N >> M;
	for (auto i : boost::irange(M))
	{
		std::int64_t a;
		std::cin >> a;
		N -= a;
	}
	std::cout << std::max(N, std::int64_t(-1)) << std::endl;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}

Measured memory_bytes: 3656
n = gets.to_i
a = gets.split(" ").map(&:to_i)

cnt = 0

loop do
  ok = true
  n.times do |i|
    if a[i].odd?
      ok = false
      break
    end
    a[i] /= 2
  end
  break if !ok
  cnt += 1
end

puts cnt


Measured memory_bytes: 1788
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define INF 1e16
typedef long long ll;
typedef pair<int,int> P;

bool ok[110];

int a[4][4];

int main(void){
    int n;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            cin>>a[i][j];
        }
    }
    cin>>n;
    for(int i=0;i<n;i++){
        int b;
        cin>>b;
        ok[b]=true;
    }
    for(int i=0;i<3;i++){
        bool flag = true;
        for(int j=0;j<3;j++){
            if(!ok[a[i][j]])flag=false;
        }
        if(flag){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    for(int i=0;i<3;i++){
        bool flag = true;
        for(int j=0;j<3;j++){
            if(!ok[a[j][i]])flag=false;
        }
        if(flag){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    bool flag = true;
    for(int i=0;i<3;i++){
        if(!ok[a[i][i]])flag=false;
    }
    if(flag){
        cout<<"Yes"<<endl;
        return 0;
    }
    flag = true;
    if(ok[a[0][2]]){
        if(ok[a[1][1]]){
            if(ok[a[2][0]]){
                cout<<"Yes"<<endl;
                return 0;
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <stack>
#include <queue>
#include <bitset>
#include <numeric>
#ifdef DEBUG
#include "./Lib/debug.hpp"
#else
#define dump(...)
#pragma GCC optimize ("O3")
template<class T>inline auto d_val(T a, T b) { return a; }
#endif

/* (=＾o＾=) */
#define int ll

/* macro */
#define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i)
#define RFOR(i, b, e) for(ll i = (ll)(e-1); i >= (ll)(b); --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define REPC(x,c) for(const auto& x:(c))
#define REPI2(it,b,e) for(auto it = (b); it != (e); ++it)
#define REPI(it,c) REPI2(it, (c).begin(), (c).end())
#define RREPI(it,c) REPI2(it, (c).rbegin(), (c).rend())
#define REPI_ERACE2(it, b, e) for(auto it = (b); it != (e);)
#define REPI_ERACE(it, c) REPI_ERACE2(it, (c).begin(), (c).end())
#define ALL(x) (x).begin(),(x).end()
#define cauto const auto&
/* macro func */
#define SORT(x) do{sort(ALL(x));}while(false)
#define RSORT(x) do{sort((x).rbegin(),(x).rend());}while(false)
#define UNIQUE(v) do{v.erase( unique(v.begin(), v.end()), v.end() );}while(false)
#define MAX(x,y) do{x = std::max(x,y);}while(false)
#define MIN(x,y) do{x = std::min(x,y);}while(false)
#define BR do{cout<<"\n";}while(false)

/* type define */
using ll = long long;
using PAIR = std::pair<ll, ll>;
using VS = std::vector<std::string>;
using VL = std::vector<long long>;
using VVL = std::vector<VL>;
using VVVL = std::vector<VVL>;
using VD = std::vector<double>;

/* using std */
using std::cout;
constexpr char endl = '\n';
using std::cin;
using std::sort;
using std::pair;
using std::string;
using std::stack;
using std::queue;
using std::vector;
using std::list;
using std::map;
using std::unordered_map;
using std::multimap;
using std::unordered_multimap;
using std::set;
using std::unordered_set;
using std::unordered_multiset;
using std::multiset;
using std::bitset;
using std::priority_queue;

/* constant value */
constexpr ll MOD = 1000000007;
//constexpr ll MOD = 998244353;

/* Initial processing  */
struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; }_Preprocessing;

/* define hash */
namespace std { template <>	class hash<std::pair<ll, ll>> { public:	size_t operator()(const std::pair<ll, ll>& x) const { return hash<ll>()(1000000000 * x.first + x.second); } }; }

/* input */
template<class T> std::istream& operator >> (std::istream& is, vector<T>& vec) { for (T& x : vec) is >> x; return is; }

//=============================================================================================


signed main() {
	ll n, k;
	cin >> n >> k;
	cout << (n + 2 * k) / (2 * k + 1) << endl;
}

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

template <typename T>
void update(T &x, const T &y) {
	if (x > y) x = y;
}

const int MAX_N = 110, INF = 0x3f3f3f3f;

int n, m;
char s[MAX_N][MAX_N];
int dp[MAX_N][MAX_N];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%s", s[i] + 1);
	}

	dp[1][1] = s[1][1] == '#';
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (i == 1 && j == 1)
				continue;
			dp[i][j] = INF;
			if (i > 1) {
				if (s[i - 1][j] == s[i][j])
					update(dp[i][j], dp[i - 1][j]);
				else
					update(dp[i][j], dp[i - 1][j] + (s[i][j] == '#'));
			}
			if (j > 1) {
				if (s[i][j - 1] == s[i][j])
					update(dp[i][j], dp[i][j - 1]);
				else
					update(dp[i][j], dp[i][j - 1] + (s[i][j] == '#'));	
			}
		}
	}
	printf("%d\n", dp[n][m]);
}

Measured memory_bytes: 3872
n, m   = map(int, input().split())
has    = [False for _ in range(n)]
has[0] = True  
count  = [1     for _ in range(n)]

for _ in range(m):
    x, y = map(int, input().split())
    x -= 1; y-= 1
    
    count[x] -= 1
    count[y] += 1
    
    if has[x] == True:
        has[y] = True
        if count[x] == 0:
            has[x] = False
ans = 0
for x in has:
    if x == True: ans += 1
print(ans)        

Measured memory_bytes: 4656
str = gets.chomp
rstr = str.reverse
h1 = str.slice(0, (str.size-1)/2)
h2 = str.slice((str.size+1) / 2, (str.size-1)/2)
puts (str == str.reverse && h1 == h1.reverse && h2 == h2.reverse) ? "Yes" : "No"

Measured memory_bytes: 1788
#include<stdio.h>
 
int main(){
  int i, n, max, min;
  int num[10000];
  long long sum = 0;
 
  scanf("%d", &n);
 
  for(i=0; i<n; i++){
      scanf("%d", &num[i]);
      sum += num[i];
  }
    min = num[0];
    max = num[0];
 
    for(i=0;i<n;i++){
        if(max < num[i])
        max = num[i];
        if(min > num[i])
        min = num[i];
    }
 
  printf("%d %d %lld\n", min, max, sum);
 
 return 0;
}

Measured memory_bytes: 1780
def power(a, k):
    N = len(a)
    r = [[1 if i==j else 0 for i in range(N)] for j in range(N)]
    while k:
        if k & 1:
            r = mul(r, a)
        k >>= 1
        a = mul(a, a)
    return r
def mul(a, b):
    return [[sum(ay * by for ay, by in zip(ax, bx)) % (10**9 + 7) for bx in zip(*b)] for ax in a]
def main():
    N, K = map(int, input().split())
    l = []
    for _ in range(N):
        l.append(list(map(int, input().split())))
    lt = [i for i in zip(*l)]
    return sum(mul([[1]*N], power(lt, K))[0])
    #return l
#print(main())
print(main() % (10**9 + 7))


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

int main() {
	long n,m,i,j,k;
	cin >> n >> m;
	j=-1;
	k=0;
	for(i=0; i<m; i++){
		j++;
		if(n%2==0 && ((n-j)-(i+1))*2<=n && k==0){
			j++; k++;
		}
		cout << i+1 << ' ' << n-j << endl;
		
	}
}

Measured memory_bytes: 3648
N = int(input())
S = input()

ans, tmp = 0, 0
for i in range(N):
    for j in range(N - i):
        if S[j] == S[i + j]:
            tmp += 1
        else:
            ans, tmp = max(ans, min(tmp, i)), 0
    ans, tmp = max(ans, min(tmp, i)), 0

print(ans)


Measured memory_bytes: 41564
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define sz(v) (int)v.size() 
#define all(v) v.begin(), v.end()
void dbg_out() { cerr << "\b\b]\n"; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){ cerr << H << ", "; dbg_out(T...);}
#define watch(...) cerr << "[" << #__VA_ARGS__ << "]: [", dbg_out(__VA_ARGS__)


/****************************** CODE IS HERE ***********************************/


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

    int n; cin >> n;
    cout << (n ^ 1);

    return 0;
}



Measured memory_bytes: 3600
memo = dict()

def rec(i, d, l, m, N, L):
    if i == L:
        return 1
    if (i, d, l, m) in memo:
        return memo[i, d, l, m]
    ret = 0
    if l == 0:
        if m == 0:
            for dd in range(10):
                if abs(dd - d) <= 1:
                    ret += rec(i+1, dd, l, m, N, L)
        else:
            n = int(N[i])
            for dd in range(n):
                if abs(dd - d) <= 1:
                    ret += rec(i+1, dd, l, 0, N, L)
            if abs(d - n) <= 1:
                ret += rec(i+1, n, l, 1, N, L)
    elif l == 1:
        if m == 0:
            ret += rec(i+1, 0, 1, m, N, L)
            for dd in range(1, 10):
                ret += rec(i+1, dd, 0, m, N, L)
        elif m == 1:
            n = int(N[i])
            for dd in range(n):
                ret += rec(i+1, dd, dd == 0, 0, N, L)
            ret += rec(i+1, n, n == 0, 1, N, L)

    memo[i, d, l, m] = ret
    return ret


def main() -> None:
    K = int(input())
    # memo.clear()
    # N = 3234566667
    # print(rec(0, 0, 1, 1, str(N), len(str(N))))
    left, right = 0, 10 ** 10
    while left + 1 < right:
        mid = (left + right) // 2
        L = len(str(mid))
        memo.clear()
        cnt = rec(0, 0, 1, 1, str(mid), len(str(mid))) - 1
        if cnt >= K:
            right = mid
        else:
            left = mid
    print(right)


if __name__ == '__main__':
    main()


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


struct node{
    node(int n,ll d){
        num = n;
        cost = d;
    }
    int num;
    ll cost;
};
vector<vector<struct node>> graph(100001);

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

    int n; cin >> n;
    int a,b; ll c; rep(i,n-1){
        cin >> a >> b >> c;
        a--; b--;
        graph[a].emplace_back(b,c);
        graph[b].emplace_back(a,c); // how?
    }

    int Q, K; cin >> Q >> K;
    vector<ll> k_dist(n,-1);    
    queue<pair<int,ll>> q;
    q.emplace(K-1,0);

    while(!q.empty()){
        int now = q.front().first;
        ll dist = q.front().second;
        q.pop();
        k_dist[now] = dist;

        rep(i,graph[now].size()){
            int next = graph[now][i].num;
            if(k_dist[next] != -1) continue;
            q.emplace(next, dist + graph[now][i].cost);
        }
    }

    int x,y;
    rep(i,Q){
        cin >> x >> y;
        x--; y--;
        cout << k_dist[x] + k_dist[y] << "\n";
    }
}

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

// aを常に小さい値にする　大きい値にする
template<class T> bool chmin(T &a, T b){
    if(a>b) {
        a = b;
        return true;
    }
    return false;

}
template<class T> void chmax(T &a, T b){ if(a<b) a = b; }

// 二分探索 前方のindexを返すもの（自分自身を含む） 前方: -INF側のこと
template<class T> int former(const vector<T> &v, T x){
    return upper_bound(v.begin(), v.end(), x) - v.begin() -1; // upper_bound : keyより大きい要素の内の一番左側のイテレータを返す
}
// 二分探索 後方のindexを返すもの（自分自身を含む）後方: INF側のこと
template<class T> int latter(const vector<T> &v, T x){
    return lower_bound(v.begin(), v.end(), x) - v.begin(); // lower_bound : key以上の要素の内の一番左側のイテレータを返す
}

/*
 *
 * */

int main() {

    int N;
    cin >> N;
    int V[N], C[N];

    rep(i,N){
        cin >> V[i];
    }
    rep(i, N){
        cin >> C[i];
    }

    int ans = 0;
    // V－Cが正のものしか選ばなくてよいのでそれだけを選ぶようにする
    rep(i, N){
        if(V[i] - C[i]>0){
            ans += V[i] - C[i];
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
"""
author : halo2halo
date : 18,Oct,2019
"""

import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

S = readline().rstrip()
T = readline().rstrip()
ans = 0
for i in range(3):
    if S[i] == T[i]:
        ans += 1


print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int> > g;
vector<vector<int> > w;
vector<int> d;
void dfs(int s, int f, int we) {
	d[s] = we;
	for (int i = 0; i < g[s].size(); i++) {
		if (g[s][i] != f) {
			dfs(g[s][i], s, we + w[s][i]);
		}
	}
}
signed main() {
	int N;
	cin >> N;
	g.resize(N);
	w.resize(N);
	d.resize(N);
	int a, b, c;
	for (int i = 0; i < N - 1; i++) {
		cin >> a >> b >> c;
		a--;
		b--;
		g[a].push_back(b);
		g[b].push_back(a);
		w[a].push_back(c);
		w[b].push_back(c);
	}
	int q, k;
	cin >> q >> k;
	k--;
	dfs(k, -1, 0);
	for (int i = 0; i < q; i++) {
		cin >> a >> b;
		a--;
		b--;
		cout << (d[a]+d[b]) << endl;
	}
	return 0;

}

Measured memory_bytes: 18176
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <utility>
#include <functional>

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

using namespace std;

typedef long long int lli;
typedef pair<int,int> pii;

const double PI = acos(-1);
const int inf = 1 << 30;

int lis(vector<int> &v) {
    vector<int> ans(v.size(), inf);
    REP (i, 0, v.size()) {
        (*lower_bound(ans.begin(), ans.end(), v[i])) = v[i];
    }
    return lower_bound(ans.begin(), ans.end(), inf) - ans.begin();
}

int main () {
    lli sx, sy, gx, gy;
    int N;
    cin >> sx >> sy >> gx >> gy;
    cin >> N;
    vector<pii> XY(N);
    REP (i, 0, N) cin >> XY[i].first >> XY[i].second;
    if (sx > gx) {
        swap(sx, gx);
        swap(sy, gy);
    }
    int sign = (sy - gy) > 0 ? -1 : 1;
    double ans = 100 * (abs(sx - gx) + abs(sy - gy));
    vector<pii> lim;
    REP (i, 0, N) {
        if (min(sx, gx) <= XY[i].first && XY[i].first <= max(sx, gx) && min(sy, gy) <= XY[i].second && XY[i].second <= max(sy, gy)) {
            lim.push_back(XY[i]);
        }
    }
    sort(lim.begin(), lim.end());
    vector<int> temp;
    REP (i, 0, lim.size()) {
        temp.push_back(sign * lim[i].second);
    }
    int m = lis(temp);

    if (m - 1 == abs(sx - gx) || m - 1 == abs(sy - gy)) {
        ans += (10 * PI - 20) - (20 - 5 * PI) * (m - 1);
    } else {
        ans -= (20 - 5 * PI) * m;
    }
    cout << fixed << setprecision(15) << ans << endl;
    return 0;
}


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

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

using namespace std;

signed main(){
	int n; cin >> n;
	vector<int> p(n);
	for(auto &e : p)cin >> e;
	sort(ALL(p));
	p.back() /= 2;
	int ans = 0;
	for(auto e: p)ans += e;
	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<queue>

#define MAX_K 10

using namespace std;

struct dial{
	dial():depth(0){
		for(int i = 0; i < MAX_K; ++i)
			d[i] = -1;
	}
	char depth;
	char d[MAX_K];
	int diff(const dial &t)const{
		int ret = 0;
		for(int i = 0; i < MAX_K; ++i){
			if( d[i] != t.d[i] )
				++ret;
		}
		return ret;
	}
};

bool DialLock(int limit, int K, const dial &now, const dial &unlock){
	if( now.depth > limit )
		return false;

	if( 0 == unlock.diff( now ) ){
		return true;
	}
		
	for(int i = 0; i < K; ++i){
		int rot;
		if( now.d[i] != unlock.d[i] ){
			dial t = now;
			
			++t.depth;
			rot = unlock.d[i] - now.d[i];
			rot += (rot<0?MAX_K:0);
			
			for(int m = 0; m < K - i; ++m){
				t.d[i+m]=(now.d[i+m]+rot)%MAX_K;
				if( DialLock(limit,K,t,unlock) )
					return true;
			}
			
			break;
		}
	}
	return false;
}
/*
int _DialLock(int K, const dial &init, const dial &unlock){
	int ret = 0;
	queue<dial> qd;
	
	qd.push( init );
	while( !qd.empty() ){
		dial now=qd.front();
		qd.pop();
		
		for(int i = 0; i < K; ++i){
			cout << now.d[i] << ' ';
		}
		cout << endl;

		if( 0 == unlock.diff( now ) ){
			ret = now.depth;
			break;
		}
		
		for(int i = 0; i < K; ++i){
			int rot;
			if( now.d[i] != unlock.d[i] ){
				dial t = now;
				
				++t.depth;
				rot = unlock.d[i] - now.d[i];
				rot += (rot<0?MAX_K:0);
				
				for(int m = 0; m < K - i; ++m){
					t.d[i+m]=(now.d[i+m]+rot)%MAX_K;
					qd.push( t );
				}
				
				break;
			}
		}
	}
	
	return ret;
}
*/

int main(){
	while( true ){
		int k;
		string a,b;
		dial init,unlock;

		cin >> k;
		if( k == 0 )
			break;
		cin >> a >> b;
		for(int i = 0; i < k; ++i){
			init.d[i] = a[i] - '0';
			unlock.d[i] = b[i] - '0';
		}
		init.depth=0;

		for(int i = 0; i <= k; ++i){
			if( DialLock( i, k, init, unlock ) ){
				cout << i << endl;
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 924
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        string input = Console.ReadLine();
        bool flag = true;
        for(int i = 0; i < input.Length; i++)
        {
            if (i % 2 == 1&& input[i] == 'R') { flag = false; }
            if (i % 2 == 0&& input[i] == 'L') { flag = false; }
        }
        if (flag == false) { Console.WriteLine("No"); }
        else { Console.WriteLine("Yes"); }
    }
}


Measured memory_bytes: 13140
N, M = map(int, input().split())

data = {}

for _ in range(M):
  p_i, result = map(str, input().split())
  if int(p_i) not in data.keys():
    data[int(p_i)] = [False if result == "WA" else True]
  else:
    data[int(p_i)].append(False if result == "WA" else True)

correct_answers = 0
penalties = 0
for prob in data.keys():
  if True in data[prob]:
    i = 0
    correct_answers += 1
    while not data[prob][i]:
      penalties += 1
      i+= 1
    
print(correct_answers, penalties)

Measured memory_bytes: 23184
def main():
    n = int(input())
    res = 0
    for (a, k) in [map(int, input().split()) for _ in range(n)]:
        while a > k and a % k != 0:
            m = a // k
            x = (a - k * m - 1) // (m + 1)
            a -= max(1, x) * (m + 1)
        res ^= a // k
    print('Takahashi' if res != 0 else 'Aoki')


if __name__ == '__main__':
    main()

Measured memory_bytes: 3188
import java.util.*;
import java.util.function.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    String S = sc.next();
    String T = sc.next();
    sc.close();

    StringBuilder buf = new StringBuilder();
    for (int i = 0; i < N; i++) {
      buf.append(S.charAt(i));
      buf.append(T.charAt(i));
    }
    System.out.println(buf);
  }
}

Measured memory_bytes: 21844
#include <stdio.h>
int main(void){
  int a, b, w, x, y;
  scanf("%d%d%d", &w, &a, &b);
  if(a>=b){
    x=a;
    y=b;
  }else{
    x=b;
    y=a;
  }
  if(y+w>=x){
    printf("0\n");
  }else{
    printf("%d\n", x-y-w);
  }
  return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
int main()
{
    long long n,num=0;
    scanf("%lld",&n);
    if(n%2==1)
    {
        printf("0\n");

    }
    else
    {
        n=n/2;
        n=n/5;
        while(n)
        {
            num=num+n;
            n=n/5;
        }

       printf("%lld\n",num);


    }
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(c) c.begin(),c.end()
#define show(x) cout << #x << " " << x << endl;
typedef long long ll;
ll mod=1e9+7;
vector<ll> ika;
typedef vector<ll> vl;
typedef vector<vl> vv;
vv pro(vv a, vv b){
	vv ret(2,vl(2,0));
	rep(i,2) rep(j,2) rep(k,2) ret[i][j]+=a[i][k]*b[k][j];
	rep(i,2) rep(j,2) ret[i][j]%=mod;
	return ret;
}
ll f(ll a){
	a--;
	vv now(2,vl(2,0)),pw(2,vl(2,1));
	now[0][0]=1,now[1][1]=1,pw[1][1]=0;
	for(int i=0;(a>>i)>0;i++){
		if((a>>i)&1) now=pro(now,pw);
		pw=pro(pw,pw);
	}
	return now[0][0];
}
int main(){
	ll k;
	cin >> k;
	ll lb=-1,ub=2*1e9;
	while(ub-lb>1){
		ll m=(ub+lb)/2;
		ll x=(m/2)*(m/2+1);
		if(m%2==0) x+=m/2+1;
		else x+=2*(m/2+1);
		if(x<k) lb=m;
		else ub=m;
	}
	ll x=ub+4,al=(lb/2)*(lb/2+1),kc=k;
//	show(x);
	if(lb%2==0) al+=lb/2+1;
	else al+=(lb/2+1)*2;
//	show(al);
	k-=al;
	k=x/2-k;
	ll a,b;
	if(k<=(x-2)/4) a=2*k+1,b=x-a;
	else{
		k-=(x-2)/4;
		a=x/4*2-k*2+2,b=x-a;
	}
	if(kc==1) a=2,b=2;
	cout << f(a)*f(b)%mod << endl;
}

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

using namespace std;
using ll = long long;

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << #x << ": " << x << endl;
#define popcnt __builtin_popcount

struct UF {
    vector<int> v;

    UF(int n) : v(n, -1) {}

    int find(int x) { return v[x] < 0 ? x : v[x] = find(v[x]); }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (-v[x] < -v[y]) swap(x, y);
        v[x] += v[y];
        v[y] = x;
        return;
    }

    bool root(int x) { return v[x] < 0; }

    bool same(int x, int y) { return find(x) == find(y); }

    int size(int x) { return -v[find(x)]; }
};

int main() {
    int n, m;
    cin >> n >> m;
    UF uf(n + 10);
    vector<ll> ans;
    vector<int> a(m), b(m);
    for (int i = 0; i < m; ++i) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
    }

    ll cur = (ll) n * (n - 1) / 2;
    for (int i = m - 1; i >= 0; --i) {
        ans.push_back(max(0LL, cur));
        if(!uf.same(a[i], b[i])){
            cur-=((ll)uf.size(a[i])*uf.size(b[i]));
            uf.unite(a[i], b[i]);
        }
    }

    reverse(all(ans));
    for (ll x : ans) {
        cout << x << endl;
    }

    return 0;
}

Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(),(a).end()
#define debug(x) cerr<<(#x)<<": "<<(x)<<endl

typedef long long ll;

bool check(ll n, ll k){
    if (n == 1) return true;
    if (n < k) return false;
    if (n % k == 0) {
        return check(n/k,k);
    } else {
        return check(n%k,k);
    }
}

vector<ll> get_div(ll n){
    vector<ll> res;
    for (ll d = 2; d*d <= n; d++) {
        if(n % d == 0){
            res.push_back(d);
            if (d < n/d) {
                res.push_back(n/d);
            }
        }
    }
    return res;
}

int main(void){
    ll n;
    cin >> n;
    if (n == 2) {
        cout << 1 << endl;
        return 0;
    }
    vector<ll> cand = {n, n-1};
    auto div1 = get_div(n);
    cand.insert(cand.end(), all(div1));
    auto div2 = get_div(n-1);
    cand.insert(cand.end(), all(div2));
    set<ll> res;
    for (ll d : cand){
        if (check(n,d)) res.insert(d);
    }
    cout << res.size() << endl;
    return 0;
}


Measured memory_bytes: 384
#include<stdio.h>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
 
using namespace std;
 
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
 
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
 
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
 
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;



int main(int argc, char const *argv[])
{
	int a,b,c,n;
	cin >> a >> b;
	int res = a*b;
	if(res%2==0)cout<<"Even"<<endl;
	else cout << "Odd" <<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL; 
const int MOD = 1000003;
LL mpow(LL a, LL x) {
	if (x == 0) return 1;
	LL t = mpow(a, x >> 1);
	if (x % 2 == 0) return t * t % MOD;
	return t * t % MOD * a % MOD;
}
int q, x, d, n;
LL fac[MOD << 1];
int main() {
	fac[0] = 1;
	for (int i = 1; i < (MOD << 1); i ++) {
		fac[i] = fac[i-1] * i % MOD;
	}

	scanf("%d", &q);
	while (q --) {
		scanf("%d%d%d", &x,&d,&n);
		if (d == 0) {
			printf("%lld\n", mpow(x, n)); continue;
		}
		if (x == 0) {
			printf("0\n"); continue;
		}
		int k = 1LL * x * mpow(d, MOD-2) % MOD;
		if (k + (n-1) >= MOD) {
			printf("0\n"); continue;
		}
		//printf("[%d, %d]\n", k, k+n-1);
		LL ans = 1LL * mpow(d, n) * fac[k + n - 1] % MOD * ((k>=1)?mpow(fac[k-1], MOD-2):1) % MOD; 
		printf("%lld\n", ans);
	}
}

Measured memory_bytes: 16512
#include<stdio.h>

int main(){
    int n;
    int d[100];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&d[i]);
    }

    int out=0;
    int count=0;

    for(int i=count;i<n;i++){
        for(int k=count+1;k<n;k++){
            out=out+d[i]*d[k];
        }
        count++;
    }
    printf("%d\n",out);

    return 0;
}

Measured memory_bytes: 128
/*input
4 100000
100000 100000 100000 100000
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = (ll)1e9 + 7;
int n, k, a[105];
ll dp[105][100005];
ll pref[105][100005];

int main(){
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i++){
		scanf("%d", a + i);
	}
	for(int i = k; i >= max(0, k - a[1]); i--){
		dp[1][i] = 1;
	}
	for(int i = 0; i <= k; i++){
		pref[1][i] = dp[1][i];
		if(i != 0) pref[1][i] += pref[1][i - 1];
		pref[1][i] %= MOD;
	}
	for(int i = 2; i <= n; i++){
		for(int j = 0; j <= k; j++){
			dp[i][j] = pref[i - 1][min(k, j + a[i])] % MOD;
			if(j != 0) dp[i][j] -= pref[i - 1][j - 1];
			dp[i][j] = (dp[i][j] + MOD) % MOD;
			pref[i][j] = dp[i][j];
			if(j != 0) pref[i][j] += pref[i][j - 1];
			pref[i][j] %= MOD;
		}
	}
	printf("%lld\n", dp[n][0]);
	return 0;
}

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

int main() {
    int n, k, s;
    cin >> n >> k >> s;

    rep(i, k) {
        cout << s << " ";
    }
    int sub = (s == 123 ? 100 : 123);
    rep(i, n - k) {
        cout << sub << (i == n - k - 1 ? "\n" : " ");
    }
}

Measured memory_bytes: 1280