akhauriyash/Code-Regression huggingface dataset:
#![allow(unused_imports)]

use proconio::{input, fastout};
use proconio::marker::*;

#[fastout]
fn main() {
    input! {
    s: Chars
    }
    let ans = match s[0] {
        'S' => "Cloudy",
        'C' => "Rainy",
        _ => "Sunny"
    };
    println!("{}", ans);
}


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

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;

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

constexpr llong mod = 1e9+7;
constexpr llong inf = mod * mod;

int main() {
  llong N;
  vector<vector<lpair>> A;

  cin >> N;
  A.resize(N + 1);
  for (int i = 1; i <= N; i++) {
    llong n;
    cin >> n;
    A[i].resize(n);
    for (auto &in: A[i]) {
      cin >> in.first >> in.second;
    }
  }

  int ans = 0;
  for (int i = 0; i < (1<<N); i++) {
    vector<int> res(N + 1);
    for (int j = 0; j < N; j++) {
      res[j + 1] = (i>>j)&1;
    }

    bool check = true;
    for (int j = 0; j < N; j++) {
      if (!((i>>j)&1)) continue;
      for (auto a: A[j + 1]) {
        check &= res[a.first] == a.second;
      }
    }

    if (check) {
      ans = max(ans, __builtin_popcount(i));
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
 
int main() {
	fastio;
	ll k,n;
	cin>>k>>n;
	vector<ll> a(n,0);
	ll ans = 0;
	for(ll i=0;i<n;i++){
		cin>>a[i];
	}
	vector<ll> dif;
	for(ll i=1;i<n;i++){
		dif.push_back(a[i]-a[i-1]);
	}
	dif.push_back(k-a[n-1]+a[0]);
	ll red = 0;
	for(ll i=0;i<dif.size();i++){
		ans += dif[i];
		red = max(red,dif[i]);
	}
	cout<<ans-red<<"\n";
	
}

Measured memory_bytes: 3956
#include <iostream>
#include <string>
using namespace std;

int main() {
	string str_s, str_p;
	int i,j;
	bool able=false;
	getline(cin,str_s);
	getline(cin,str_p);
	for(i=0; i<(int)str_p.length()-1; ++i) {
		str_s+=str_s[i];
	}
	for(i=0; i<(int)str_s.length()-(int)str_p.length()+1;++i) {
		for(j=0; j<(int)str_p.length(); ++j) {
			if(str_s[i+j]!=str_p[j]) {
				break;
			}
		}
		if(j==(int)str_p.length()) {
			able=true;
		}
	}
	cout << (able?"Yes":"No") << endl;
	return 0;
}

Measured memory_bytes: 3192
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace ConsoleApp
{
    class Program
    {
        
        static void Main(string[] args)
        {
            var arr = ReadLine().Split().Select(long.Parse).ToArray();

            long a = arr[0];
            long b = arr[1];
            long k = arr[2];

            a -= k;
            if(a < 0){
                b += a;
                a = 0;
                if(b < 0)
                    b = 0;
            }

            WriteLine(a + " " + b);
        }

       

    }

}


Measured memory_bytes: 13396
#include<bits/stdc++.h>
#include<string>
using namespace std;
int main()
{
  string s;
  cin>>s;
  int c=0;
  for(int i=0;i<4;i++)
  {
      if(s[i]=='+')
        c++;
      else
        c--;
  }
  cout<<c<<endl;


    return 0;

}









Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using ll = long long;
using ld = long double;
using namespace std;
const int INF = 1e9+100;
const ll INF64 = 7e18l;
const int mod = 1000000007;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(), (a).end()
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


int main(){
    FIN;

    ll n; cin >> n;
    vector<ll> h(n+1,0);
    for(ll i=1;i<=n;i++) cin >> h[i];

    for(ll k=1;k<n;k++){
        if(h[k-1] == h[k]){
            if(h[k] > h[k+1]) {cout << "No" << endl; return 0;}
        }
/*
        if(h[k-1] < h[k]){
            if(h[k] > h[k+1]) h[k]--;
            if(h[k] > h[k+1]) {cout << "No" << endl; return 0;}//低くしてもだめならNo
        }
*/
        if(h[k-1] < h[k]) h[k]--;
        if(h[k] > h[k+1]) {cout << "No" << endl; return 0;}
    }

    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

const int MOD = 1000000007, INF = 1111111111; 
using namespace std;
typedef long long lint;

int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	vector<string> s(N);
	for (int i = 0; i < N; i++) cin >> s[i];

	int alast = 0, bfirst = 0, both = 0,ans = 0;
	for (int i = 0; i < N; i++) {
		if (s[i][0] == 'B') bfirst++;
		if (s[i].back() == 'A') alast++;
		if (s[i][0] == 'B'&&s[i].back() == 'A') both++;
		for (int j = 1; j < s[i].length(); j++) {
			
			if (s[i][j] == 'B'&& s[i][j - 1] == 'A') ans++;
		}
	}

	cout << ans + min(alast, bfirst) + min(0, max(max(alast, bfirst),1) - both - 1);

	return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 998244353;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); } string to_string(string x){ return x; }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + " "; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd_calc(T a, T b){ if(b){ return gcd_calc(b, a % b); }else{ return a; }}
template<class T> T gcd(T a, T b){ if(a < b) swap(a, b); return gcd_calc(a, b); }
template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }
inline int at(int x, int k){ return (x >> k) & 1; }
random_device rnd;

int main(){
    double ans = 0;
    int N;
    cin >> N;
    for(int i = 0; i < N; i++){
        double A;
        cin >> A;
        ans += 1 / A;
    }
    fcout << 1 / ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>

int main() {
  using std::vector;  
  int r, c;
  std::cin >> r >> c;
  vector<vector<int>> table(r+1, vector<int>(c+1, 0));
  
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      std::cin >> table[i][j];
      table[i][c] += table[i][j];
      table[r][j] += table[i][j];
    }
  }
  
  for (int i = 0; i < r; i++) {
    table[r][c] += table[i][c];
  }
  
  for (int i = 0; i < r+1; i++) {
    for (int j = 0; j < c+1; j++) {
      if (j != 0) std::cout << " ";
      std::cout << table[i][j];
    }
    std::cout << "\n";
  }
  
  return 0;
}

Measured memory_bytes: 1248
#include <algorithm>
#include <iostream>
#include <vector>
#include <numeric>
#include <string>
#include <stdio.h>
#include <set>
#include <cmath>
#include <iomanip>
using namespace std;
 
int main(){
    long long N, K, score, pre_score;
    cin >> N >> K;
    //score = 1;
    vector<long long> A(N);
    for (int i=0; i<N; i++){
        cin >> A[i];
    }
    for (int i=0; i<K; i++){
        score *= A[i];
    }
    for (int i=K; i<N; i++){
        //pre_score = score;
        //score = score * A[i];
        //score = score / A[i-K];
        if (A[i-K] < A[i]){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 4840
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
	int ans, n, v[21], c[21];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> c[i];
	}
	ans = 0;
	for (int i = 0; i < n; i++) {
		if (v[i] > c[i]) {
			ans += v[i] - c[i];
		}
	}
	cout << ans;
	cin >> n;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>

typedef unsigned long long ULL;
typedef long long LL;

using namespace std;

int main(){
    int N;
    int i;
    ULL count;
    ULL *A,*B;

    cin >> N;
    A = new ULL[N+1];
    B = new ULL[N];

    for(i=0;i<N+1;i++){
        cin >> A[i];
    }
    for(i=0;i<N;i++){
        cin >> B[i];
    }
    count = 0;
    for(i=0;i<N;i++){
        if( A[i] > B[i]){
            count += B[i];
            A[i] -= B[i];
        }else{
            count += A[i];
            B[i] -= A[i];
            A[i] = 0;
            if( A[i+1] > B[i]){
                count += B[i];
                A[i+1] -= B[i];
            }else{
                count += A[i+1];
                A[i+1] = 0;
            }
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll t;
	cin>>t;
	if(t>=30)
	{
		cout<<"Yes";
	}
	else
		cout<<"No";
	return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=(n);i<(int)N;i++)
#define p(s) cout<<(s)<<endl
#define ck(n,a,b) ((a)<=(n)&&(n)<(b))
#define F first
#define S second
typedef long long ll;
using namespace std;
const int inf=1e9;


int main() {
	int n;
	string s,left="",right="";
	cin>>n>>s;
	int cnt=0;
	REP(i,0,n){
		if(s[i]=='(') cnt++;
		else{
			if(cnt==0)left+='(';
			else cnt--;
		}
	}
	cnt=0;
	for(int i=n-1;i>=0;i--){
		if(s[i]==')') cnt++;
		else{
			if(cnt==0)right+=')';
			else cnt--;
		}
	}
	string ans=left+s+right;
	p(ans);
	return 0;
}


Measured memory_bytes: 256
/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner sc = new Scanner(System.in);
		
		String a = sc.nextLine();
		int n =  Integer.parseInt(a);
		String s = sc.nextLine();
		
		String[] arr = s.split(" ");
		
		StringBuffer sb = new StringBuffer("");
		
		for(int i = 0; i<n;i++){
			sb.append(arr[0].charAt(i));
			sb.append(arr[1].charAt(i));
		}
		
		System.out.println(sb.toString());
	}
}

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


int main(){
    int x, y; cin >> x >> y;
    if(x % y == 0){
        cout << -1 << endl;
    } else {
        cout << x << endl;
    }
}

Measured memory_bytes: 256
n,a,b,k=map(int,input().split())
mod=998244353
import math
def lcm(x, y):
  return (x * y) // math.gcd(x, y)
g=math.gcd(a,b)
if k%g!=0:
  print(0)
  exit()
k//=g
a//=g
b//=g

# コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
for i in range(2,n+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

def func(na,nb):
  ret=1
  ret*=cmb(n,na,mod)
  ret%=mod
  ret*=cmb(n,nb,mod)
  ret%=mod
  return ret

def func0(na,nb):
  ret=0
  if na<nb:na,nb=nb,na
  for nc in range(min(nb,n)+1):
    # 緑がnc 他がna-nc,nb-nc個ずつ
    reti=1
    if 0<=nc<=n and 0<=na-nc<=n and  0<=nb-nc<=n:
      reti*=g1[n]
      reti%=mod
      reti*=g2[nc]
      reti%=mod
      reti*=g2[na-nc]
      reti%=mod
      reti*=g2[nb-nc]
      reti%=mod
      reti*=g2[n+nc-na-nb]
      reti%=mod
      ret+=reti
  return ret
pat=[]
for i in range(1+k//a):
  if (k-a*i)%b==0:
    pat.append([i,(k-a*i)//b])
    break
na=pat[0][0]
nb=pat[0][1]
while nb-a>=0:
  na+=b
  nb-=a
  pat.append([na,nb])
ans=0
for na,nb in pat:
  if na>n or nb>n:continue
  ans+=func(na,nb)
  ans%=mod
print(ans)


Measured memory_bytes: 134932
#include<bits/stdc++.h>
using namespace std;
int main() {
	int A[3];
	for (int i = 0; i < 3; i++) {
		cin >> A[i];
	}
	sort(A, A + 3);
	int N;
	cin >> N;

	for (int i = 1; i <= N; i++) {
		A[2] *= 2;
	}

	cout << A[0] + A[1] + A[2] << endl;
	return 0;

}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String args[]){
        Scanner stdIn = new Scanner(System.in);
        int n = stdIn.nextInt();
        
        if(n % 1000 == 0){
            System.out.println(0);
        }else{
            System.out.println(1000 - (n % 1000));
        }
    }
}


Measured memory_bytes: 35676
#include <iostream>

using namespace std;

int main() {
	int n; cin >> n;
	for (int t = 0; t < n; ++t) {
		int a[10];
		for (int i = 0; i < 10; ++i) cin >> a[i];

		bool ans = false;
		for (int k = 0; k < (1 << 10); ++k) {
			int top[2] = {-1, -1};
			bool f = true;
			for (int i = 0; i < 10; ++i) {
				int tid = k & (1 << i) ? 1 : 0;
				if (a[i] < top[tid]) {
					f = false;
					break;
				}
				top[tid] = a[i];
			}
			ans |= f;
		}

		if (ans) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
#include <queue>
#include <cstring>

#define mp make_pair
#define pb push_back
#define p push

#define FOR(a, c) for(int a = 0;a<c;a++)
#define ll long long int

#define getI(a) scanf("%d",&a)
#define getII(a, b) scanf("%d%d",&a,&b)
#define getIII(a, b, c) scanf("%d%d%d",&a,&b,&c)
#define getL(a) scanf("%lld",&a)
#define getLL(a, b) scanf("%lld%lld",&a,&b)
#define getLLL(a, b, c) scanf("%lld%lld%lld",&a,&b,&c)
#define BEND(c) (c).begin(),(c).end()
#define BEND2(c) (c).rbegin(),(c).rend()
#define fi first
#define se second
#define pi 3.1415926535897932384626
#define getS(a) scanf("%s",a)
#define pfi(a) printf("%d",a);
#define pfii(a, b) printf("%d%d",a,b);
#define pfl(a) printf("%lld",a);
#define pfll(a, b) printf("%lld%lld",a,b);
#define pfd(a) printf("%lf",a);
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);

#define sag (sol|1)
#define sol (root<<1)
#define ort (bas+son)/2
#define SIZE  ( int)(1e9 + 7)
#define MAXN (ll) (1e5+5)

using namespace std;

typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector <vector<int>> vvi;
typedef vector<long long> vl;
typedef vector <pair<int, int>> vpi;
typedef vector <pair<long long, long long>> vpl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector <vi> graph;

int main(){
    IOS
    int n ,k;
    cin >>n>>k;
    int r , p ,s ;
    cin >>r >> s >>p;
    string t ;
     cin >> t;
    string s2 =t;
    char c;

    for (int i = 0; i <k ; ++i) {
        c= t[i];
        if(t[i] == 'r')s2[i]='p';
        if(t[i] == 'p')s2[i]='s';
        if(t[i] == 's')s2[i]='r';
        for (int j = i; j <n ; j+=k) {
            if ( j <k){
                continue;
            }
            if(t[j] != c){
               if(t[j] == 'r')s2[j]='p';
               if(t[j] == 'p')s2[j]='s';
               if(t[j] == 's')s2[j]='r';
               c=t[j];
            }else{
                s2[j]='0';

                c ='0';
            }


        }
    }

    if(t[n-1] == 'r')c='p';
    if(t[n-1] == 'p')c='s';
    if(t[n-1] == 's')c='r';

    if(s2[n-1 -k] != c){
        s2[n-1]=c;
    }

    ll res =0;
    for (int l = 0; l <n ; ++l) {
        ll tt = l;
        if(s2[tt]=='r'){
            if(s2[tt] != t[tt])
            res+=r;
        }else if(s2[tt]=='s'){
            if(s2[tt] != t[tt])
            res+=s;
        }else if(s2[tt]=='p'){
            if(s2[tt] != t[tt])
            res+=p;
        }
        //cout <<res;
    }

    //cout << s2 <<"\n";
    cout << res;
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main(){
  int n,x,y=0,itung=0;
  cin >> n >> x;
  int arr[n+10];
  int awal;
  for(int i=0;i<n;i++){
    cin >> arr[i];
    if(i==0){
      y+=arr[i];
      awal=y;
      itung+=2;
    }
    else{
      y+=arr[i];
      if(y>x){
        break;
      }
      itung++; 
    }
  }
  cout << itung << endl;
}


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

using namespace std;

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

	vector<int> vi;
	int mx = 0;

	for (int i = 0; i < n; i++) {
		int p;
		cin >> p;
		vi.push_back(p);

		mx = max(p, mx);
	}

	vector<long long> div(mx + 1);

	for (int i = 0; i < n; i++) {
		for (int j = 1; j * vi[i] <= mx; j++) {
			div[j * vi[i]]++;
		}
	}

	int c = 0;

	for (int i = 0; i < n; i++) {
		if (div[vi[i]] == 1) c++;
	}

	cout << c;
}


Measured memory_bytes: 11948
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define IN freopen("in.txt", "r", stdin);
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;


int main(){
    IOS;
    int x;cin>>x;
    cout<<360/__gcd(x,360)<<endl;



    return 0;
}

Measured memory_bytes: 3612
<?php
	fscanf(STDIN, "%d", $n);
	for ($i=0; $i<$n; $i++) {
      fscanf(STDIN, "%s %d", $s, $p);
	  $data[] = array('s'=>$s, 'p'=>$p, 'i'=>$i);
    }
	$sc = array_column($data, 's');
	$pc = array_column($data, 'p');
	array_multisort($sc, SORT_ASC, $pc, SORT_DESC, $data);
	for ($i=0; $i<$n; $i++) {
      echo $data[$i]['i'] + 1 . "\n";
    }
?>
	

Measured memory_bytes: 4728
#include <iostream>
#include <string>
using namespace std;

int main(){
  string S;
  cin >> S;
  int price = 700;
  for(int i = 0; i < S.size(); i++){
    if(S[i] == 'o'){
      price += 100;
    }
  }
  cout << price << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define int long long
#define pb push_back
#define mod 1000000007
#define setbits(x) __builtin_popcountll(x)
#define zerobits(x) __builtin_ctzll(x)
#define inf 1e18
#define pre(x,y) fixed<<setprecision(y)<<x
#define pq priority_queue<int>
#define mpq priority_queue<int,vector<int>,greater<int>>
#define gcd(x,y) __gcd(x,y)
#define mp make_pair

int p[21][21];
int dp[21][1<<21];

int matching(int n,int i,int mask)
{
	if(i==n)
	{
		if(mask==(1<<n)-1) return 1;
		else return 0;
	}
	else if(dp[i][mask]!=-1) return dp[i][mask];
	else
	{
		int ans=0;
		for(int j=0;j<n;j++)
		{
			if(p[i][j])
			{
				int tempmask=1<<j;
				if(!(tempmask&mask))
				{
					ans+=matching(n,i+1,mask|tempmask);
					ans%=mod;
				}
			}
		}
		return dp[i][mask]=ans;
	}
}


int32_t main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,i,j,k;
    cin>>n;
    for(i=0;i<n;i++)
    {
    	for(j=0;j<n;j++) cin>>p[i][j];
    }
    memset(dp,-1,sizeof(dp));
    cout<<matching(n,0,0)<<endl;
	return 0;
}


Measured memory_bytes: 347672
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val n = sc.nextInt()
  val games = List.fill(n, 2)(sc.next())
  val referee = createReferee
  games.foreach(judge(_, referee))
  println(referee(0).taro + " " + referee(0).hanako)

  def createReferee: (Int) => ScoreSet = {
    // (taro, hanako)
    var score = ScoreSet(0, 0)
    // 0:output, 1: taro-win, 2: hanako-win, 3: draw
    (judge: Int) => {
      judge match {
        case 0 => score
        case 1 => score = ScoreSet(score.taro + 3, score.hanako); score
        case 2 => score = ScoreSet(score.taro, score.hanako + 3); score
        case 3 => score = ScoreSet(score.taro + 1, score.hanako + 1); score
      }
    }
  }

  def judge(game: List[String], referee: (Int) => ScoreSet): ScoreSet = {
    game match {
      case _ if game(0) == game(1) => referee(3)
      case _ if game.sorted == game => referee(2)
      case _ if game.sorted != game => referee(1)
    }
  }

  case class ScoreSet(taro: Int, hanako: Int)

}

Measured memory_bytes: 51764
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <cstdint>
#include <bits/stdc++.h>
#include <queue>
#include <set>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_r(i, n) for (int i = n - 1; i >= 0; i--)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((ll)(x).size())
#define bit(n) (1LL << (n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());

#define INF bit(60)
#define pb push_back
#define mod 1000000007

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

using namespace std;
using uif = uint_fast64_t;
using ll = long long int;

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

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

#define FACSIZE 2002

ll invfac[FACSIZE];
ll fac[FACSIZE];

ll mod_pow(ll, ll);
ll mod_add(ll, ll);
ll mod_mul(ll, ll);
ll mod_div(ll, ll);
void make_fact(ll);
void make_invfact(ll);

int main(void)
{

  ll n, m;
  cin >> n >> m;
  string s;
  cin >> s;

  vector<ll> vec(n + 1, INT_MAX);
  vec[0] = n;
  ll path = 1;
  ll bp = n;
  ll flagEn = false;
  while (bp > 0)
  {
    for (ll i = 1; i <= m; i++)
    {
      if (bp - i >= 0 && s[bp - i] != '1' && vec[path] > bp - i)
      {
        vec[path] = bp - i;
        if (bp - i == 0)
        {
          flagEn = true;
          break;
        }
      }
    }
    if (flagEn)
      break;
    bp = vec[path++];
    if (bp == INT_MAX)
    {
      cout << -1 << endl;
      return 0;
    }
    //cout << bp << endl;
  }
  /*
  for (ll i = 0; i < path + 1; i++)
  {
    cout << vec[i] << endl;
  }
  */
  for (ll i = path - 1; i >= 0; i--)
  {
    cout << vec[i] - vec[i + 1] << " ";
  }
  cout << endl;

  return 0;
}

ll mod_pow(ll x, ll r)
{
  if (r == 0)
    return 1;
  else if (r == 1)
    return x % mod;
  else if (r % 2 == 0)
  {
    ll t = mod_pow(x, r / 2) % mod;
    return t * t % mod;
  }
  else
  {
    ll t = mod_pow(x, r / 2) % mod;
    ll k = t * t % mod;
    return k * x % mod;
  }
}
ll mod_add(ll a, ll b)
{
  return (a + b) % mod;
}

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

ll mod_div(ll a, ll b)
{
  return mod_mul(a, mod_pow(b, mod - 2));
}

void make_fact(ll n)
{
  fac[0] = 1;
  rep(i, n)
  {
    fac[i + 1] = mod_mul(fac[i], i + 1);
  }
}

void make_invfact(ll n)
{
  invfac[n] = mod_pow(fac[n], mod - 2);
  for (int i = n - 1; i >= 0; i--)
  {
    invfac[i] = mod_mul(invfac[i + 1], i + 1);
  }
}

Measured memory_bytes: 1408
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << ' ' << '=' << ' ' << (x) << endl;
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
typedef vector<ll> vec;
typedef vector<P> pvec;
typedef vector<vector<ll>> vvec;
typedef vector<vector<P>> pvvec;
typedef priority_queue<ll> PQI;
typedef priority_queue<P> PQP;
typedef priority_queue<ll,vector<ll>,greater<ll>> PQIG;
typedef priority_queue<P,vector<P>,greater<P>> PQPG;
const vector<int> dx = {0, -1, 0, 1, 1, 1, -1, -1};
const vector<int> dy = {1, 0, -1, 0, 1, -1, 1, -1};
const int MOD = (1000000007);
// const int MOD = (998244353);
// const int INF = (1 << 30); // 1073741824
const int INF = (1LL << 60); // 1152921504606846976
const double EPS = (1 >> 30);
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; }



signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    //---------------------------------------------
    
    int n,m,q;
    cin>>n>>m>>q;
    vvec a(n+1,vec (n+1));
    rep(i,m){
        int x,y;cin>>x>>y;
        a[x][y]++;
    }
    rep(i,n+1){
        rep(j,n){
            a[i][j+1]+=a[i][j];
        }
    }
    rep(j,n+1){
        rep(i,n){
            a[i+1][j]+=a[i][j];
        }
    }
    
    
    rep(i,q){
        int x,y;   
        cin>>x>>y;
        if(x<y) swap(x,y);
        int ans=0;
        ans+=a[x][x];
        // debug(a[x][x]);
        ans-=a[x][y-1];
        // debug(a[x][y-1]);
        ans-=a[y-1][x];
        // debug(a[y-1][x]);
        ans+=a[y-1][y-1];
        // debug(a[y-1][y-1]);
        cout<<ans<<endl;
    }
    
}

Measured memory_bytes: 2944
int pow(int base, int ex){
  	int ans = 1;
  	for(int i=0; i<ex; i++){
      ans *= base;
    }
  return ans;
}

int main(){
	int N,K,digit;

	scanf("%d %d",&N, &K);
  	
  	for(digit=0; N>=pow(K,digit); digit++);
  	if(1==N)digit=1;
    printf("%d", digit);
  
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<map>
#include<string.h>
#include<queue>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<cstdlib>
#include<math.h>
#include<set>
#include<array>
using namespace std;

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



#define rep(n) for(int i=0;i<n;i++)
typedef pair<int, int> pii;

typedef long long ll;
typedef pair<ll, ll>pll;
const int MOD = 1000000007;
const int INFi = 1 << 29;
const long long INF = 1LL << 60;

int N;
long long h[110000];


// DP テーブル
long long dp[110000];

int main() {
	int N, K; cin >> N >> K;
	for (int i = 0; i < N; ++i) cin >> h[i];

	// 初期化 (最小化問題なので INF に初期化)
	for (int i = 0; i < 110000; ++i) dp[i] = INF;

	// 初期条件
	dp[0] = 0;

	// ループ
	for (int i = 0; i < N; ++i) {
		for (int j = 1; j <= K; ++j) {
			chmin(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
		}
	}

	// 答え
	cout << dp[N - 1] << endl;
}





Measured memory_bytes: 1920
#include <stdio.h>
int main(void)
{
	int N, A, B;
	scanf("%d", &N);
	if (N == 1) {
		printf("Hello World");
	}
	else {
		scanf("%d %d", &A, &B);
		printf("%d", A + B);
	}
	return 0;
}

Measured memory_bytes: 128
#include<cstring>
#include<queue>
#include<bitset>
#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
char s[10000];
int p[2], n;
vector < int > d[2];
bitset < 30000 > inq;
bool check(int k) {
	queue < int > q, q2; q.push(0); inq.reset();
	for (int i = 0; i < d[k].size(); ++i, swap(q, q2))
		for (int u, v; !q.empty();) {
			u = q.front(); q.pop(); inq[u+10000] = 0;
			v = u + d[k][i];
			if (!inq[v+10000]) q2.push(v), inq[v+10000] = 1;
			v = u - d[k][i];
			if (!inq[v+10000]) q2.push(v), inq[v+10000] = 1;
		}
	for (; !q.empty(); q.pop())
		if (q.front() == p[k]) return true;
	return false;
}
int main() {
	scanf("%s", s);
	scanf("%d%d", &p[0], &p[1]);
	n = strlen(s);
	for (int fir = 1, m = 0, i = 0, t = 0; i < n; ++i) {
		if (s[i] == 'F') ++m;
		if (s[i] == 'T' || i == n - 1) {
			if (fir) p[0] -= m, m = fir = 0;
			if (m) d[t].push_back(m);
			m = 0, t ^= 1;
		}
	} puts(check(0) && check(1) ? "Yes" : "No");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

#define ll long long

struct edge {
    int to;
    ll cost;
};

vector<edge> tree[100010];
ll cost_k[100010];//Kからのコスト

void dfs(int v, int par, ll dist) {//parは親ノード(一つ前の頂点)
    cost_k[v] = dist;

    for (int i = 0; i < (int)tree[v].size(); i++) {
        if (tree[v][i].to == par)continue;
        dfs(tree[v][i].to, v, dist + tree[v][i].cost);
    }
}

int main(void) {
    int N;
    cin >> N;

    for (int i = 0; i < N - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        tree[a].push_back({ b, c });
        tree[b].push_back({ a, c });
    }
    int Q, K;
    cin >> Q >> K;
    K--;

    dfs(K, -1, 0);//Kに親ノードはないので-1
    for (int i = 0; i < Q; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        cout << cost_k[x] + cost_k[y] << endl;
    }
}

Measured memory_bytes: 17408
s = list(input())
s_r = list(reversed(s))
n = int((len(s) - 1) / 2)
ss = s[:n]
ss_r = list(reversed(ss))
if s == s_r:
    if ss == ss_r:
        print('Yes')
    else:
        print('No')
else:
    print('No')

Measured memory_bytes: 3060
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {
    static Node root;

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

    public void run() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        IntStream.range(0, N).forEach(i -> {
            String cmd = sc.next();
            if (cmd.equals("insert")) {
                int id = sc.nextInt();
                insert(new Node(id));
            } else if(cmd.equals("print")) {
                print();
            }
        });
    }


    class Node {
        int id;
        Node parent = null, left = null, right = null;

        Node(int id) {
            this.id = id;
        }
    }

    private void insert(Node node) {
        Node parent = null;
        Node position = root;

        while(position != null) {
            parent = position;
            if(node.id < position.id) {
                position = position.left;
            } else {
                position = position.right;
            }
        }

        node.parent = parent;

        if (parent == null) {
            root = node;
        } else {
           if(node.id < parent.id) {
               parent.left = node;
           } else {
               parent.right = node;
           }
        }
    }

    private void print() {
        inOrder(root);
        System.out.println();
        preOrder(root);
        System.out.println();
    }

    private void preOrder(Node node) {
        if(node == null) {
            return;
        }
        System.out.print(" "  + node.id);
        preOrder(node.left);
        preOrder(node.right);
    }

    private void inOrder(Node node) {
        if(node == null) {
            return;
        }
        inOrder(node.left);
        System.out.print(" " + node.id);
        inOrder(node.right);
    }
}



Measured memory_bytes: 244824
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define INF LLONG_MAX/3
int n,w;
int a[110],b[110];
int dp[110][100010];
signed main(){
      cin>>n>>w;
      rep(i,n)cin>>a[i]>>b[i];
      rep(i,n){
		  rep(j,100010){
			 if(j+a[i]<=w)dp[i+1][j+a[i]]=max(dp[i+1][j+a[i]],dp[i][j]+b[i]);
			dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
		  }
	  }
	  int ans=0;
	  rep(i,w+1){
		  ans=max(ans,dp[n][i]);
		  }
		  cout<<ans<<endl;
		  return 0;
		  
}

Measured memory_bytes: 79360
#include "bits/stdc++.h"
using namespace std;
long long a[200001];
int main()
{
	int n;
	long long mi = 1ll << 62;
	scanf("%d", &n);	
	for(int i = 1; i <= n; ++i)
	{
		scanf("%lld", &a[i]);
		a[i] += a[i - 1];
	}
	for(int i = 1; i < n; ++i)
	{
		mi = min(mi, abs(a[n] - a[i] - (a[i] - a[0])));
	}
	printf("%lld\n", mi);
}

Measured memory_bytes: 1792
#include <cstdio>
int count=0;

void merge(int *A, int left, int mid, int right){
	int n1,n2,i,j,k;
	int *L, *R;
	n1 = mid - left;
	n2 = right - mid;
	L = new int[n1+1];
	R = new int[n2+1];

	for(i=0;i<n1;i++){
		L[i] = A[left+i];
	}
	for(i=0;i<n2;i++){
		R[i] = A[mid+i];
	}
	
	L[n1] = 1000000000;
	R[n2] = 1000000000;
	i=0;
	j=0;
	for (k=left; k<right;k++){
		count ++;
		if(L[i]<=R[j]){
			A[k] = L[i];
			i++;
		}
		else{
			A[k]=R[j];
			j++;
		}
	}
	delete L;
	delete R;
}


void mergeSort(int *A, int left, int right){
	int mid;
	if(left+1 < right){
		mid = (left+right)/2;
		mergeSort(A, left, mid);
		mergeSort(A, mid, right);
		merge(A, left, mid, right);
	}
}

int main(void){
	int i,n;
	int *A;

	std::scanf("%d", &n);
	A = new int[n];
	for(i=0;i<n;i++){
		std::scanf("%d", &A[i]);
	}
	mergeSort(A, 0, n);
	for(i=0;i<n-1;i++){
		std::printf("%d ", A[i]);
	}
	std::printf("%d\n", A[n-1]);
	std::printf("%d\n", count);
	
	delete A;
	return 0;
}

Measured memory_bytes: 6324
from __future__ import print_function

import sys
sys.setrecursionlimit(500000)

import re
import array
import copy
import functools
import operator

import math
import string
import fractions
from fractions import Fraction

import collections
import itertools
import bisect

import random
import time

import heapq
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace
from queue import PriorityQueue as pq
from queue import Queue

from itertools import accumulate

from collections import deque
from collections import Counter

from operator import mul
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


mod=1000000007
def combinations_count_mod(n, r):
    r = min(r, n - r)
    numer = reduce(lambda x,y: x*y%mod, range(n, n - r, -1), 1)
    denom = pow( reduce(lambda x,y: x*y%mod, range(1, r + 1), 1) , mod-2, mod)
    return numer * denom % mod


def main():
    n = int(input().strip())
    a = list(map(int, input().strip().split()))
    for i in range(n):
        if a[i]==0:
            print(0)
            return

    ans=1
    for i in range(n):
        ans = ans*a[i]
        if ans>10**18:
            print(-1)
            return
    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 92848
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<utility>
#include<stack>
#include<map>
#include<set>
#include<assert.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll INF = mod * mod;

typedef pair<int, int> P;
typedef pair<ll, ll> LP;

#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define stop char nyaa;cin>>nyaa;


void solve() {
	int n; cin >> n;
	vector<int> p(n);
	rep(i, n)cin >> p[i];
	int cnt = 0;
	rep1(i, n - 2) {
		vector<int> z = { p[i],p[i - 1],p[i + 1] };
		sort(z.begin(), z.end());
		if (z[1] == p[i])cnt++;
	}
	cout << cnt << endl;
}


signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//cout<<fixed<<setprecision(10);
	solve();
	//stop
	return 0;
}

Measured memory_bytes: 256
/********************************************************************************
	
	Code by a weak man who named CYJian, and he hopes the code can get more points.

	Algorithm: 

 ********************************************************************************/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

//{{{ FAST IO AND SOME FUNCTIONS
const int __SIZE = 1 << 18;
char ibuf[__SIZE], *iS, *iT;

#define ge (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
#define ri read_int()
#define rl read_ll()
#define FILE(s) freopen(s"in", "r", stdin), freopen(s"out", "w", stdout)

template<typename T>
inline void read(T &x) {
	char ch, t = 0; x = 0;
	while(!isdigit(ch = ge)) t |= ch == '-';
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
	x = t ? -x : x;
}
inline int read_int() { int x; return read(x), x; }
inline ll read_ll() { ll x; return read(x), x; }

template<typename T> inline void chkmin(T&a, T b) { a = a < b ? a : b; }
template<typename T> inline void chkmax(T&a, T b) { a = a > b ? a : b; }
//}}}

int bel[210];
ll a[210];
ll b[70];

inline int Insert(ll x) {
	ll bs = 1ll << 60;
	for(int i = 60; ~i; i--, bs >>= 1)
		if(x & bs) {
			if(b[i]) x ^= b[i];
			else return b[i] = x, 1;
		}
	return 0;
}

int main() {
#ifdef LOCAL
	FILE("");
#endif

	int Case = ri;
	while(Case--) {
		int n = ri;
		for(int i = 1; i <= n; i++) a[i] = rl;
		for(int i = 1; i <= n; i++) {
			char ch = ge;
			while(!isdigit(ch)) ch = ge;
			bel[i] = ch - '0';
		} int res = 0;
		for(int i = n; i >= 1; i--) {
			int ok = Insert(a[i]);
			if(bel[i] && ok) res = 1;
		} printf("%d\n", res);
		memset(b, 0, sizeof(b));
	}
	return 0;
}

Measured memory_bytes: 3916
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define pb push_back
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
#define MOD 998244353
typedef double ld;
#define PI 3.14159265


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

    int n , m , x;
    cin >> n >> m >> x;
    int arr[n + 1];
    int v;
    memset(arr , 0 , sizeof(arr));
    for(int i = 0 ; i < m ; i++) cin >> v , arr[v] = 1;
    int ans1 = 0 , ans2 = 0;
    for(int i = x - 1 ; i >= 0 ; i--) {
        ans1 += arr[i];
    }
    for(int i = x ; i <= n ; i++) {
        ans2 += arr[i];
    }
    cout << min(ans1 , ans2) << endl;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define N 1000000
#define A_IN 1000000000
int cnt=0;
int n;
int*G;
int A[N];
int c=0;
void insertionSort(int A[], int n, int g){
  int i,v,j;
  for(i=g;i<n;i++){
    v=A[i];
    j=i-g;
    while(j>=0 && A[j]>v){
      A[j+g]=A[j];
      j-=g;
      cnt++;
    }
    A[j+g]=v;
  }
}

void shellSort(int A[],int n){
  int i=0,q;
  cnt=0;
  G=(int *)malloc(n * sizeof(int));
 
  for(q=1;;){
    if(q>n) break;
    G[i]=q;
    i++;
    q=3*q+1;
  }
  c=i;
  for(i=c-1;i>=0;i--){
    insertionSort(A,n,G[i]);
  }
}


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

  printf("%d\n",c);

  for(i=c-1;i>=0;i--){
    printf("%d",G[i]);
    if(i) printf(" ");
  }
  printf("\n");
  printf("%d\n",cnt);
  for(i=0;i<n;i++)printf("%d\n",A[i]);

  free(G);
  
  return 0;
}



Measured memory_bytes: 5600
#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);

    int sx,sy,tx,ty; cin >> sx >> sy >> tx >> ty;

    for(int i = 0;i < tx - sx;i ++) cout << 'R';
    for(int i = 0;i < ty - sy;i ++) cout << 'U';
    for(int i = 0;i < tx - sx;i ++) cout << 'L';
    for(int i = 0;i < ty - sy;i ++) cout << 'D';

    cout << 'D';

    for(int i = 0;i < tx - sx + 1;i ++) cout << 'R';
    for(int i = 0;i < ty - sy + 1;i ++) cout << 'U';
    cout << "LU";
    for(int i = 0;i < tx - sx + 1;i ++) cout << 'L';
    for(int i = 0;i < ty - sy + 1;i ++) cout << 'D';
    cout << 'R';

    cout << endl;
}

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

#define F first
#define S second
#define PB push_back
#define all(x) x.begin(), x.end()

typedef long long ll; 
typedef double ld;

const int N = 1000 + 10, M = 1000 + 10; 

int a[N];

ll solve(vector<ll>& v, ll id, ll k)
{
	if(id==-1) return 0;
	vector<ll> v2;
	for(auto u : v)
		if(u&(1ll<<id))
			v2.PB(u);
	if(v2.size()>=k) return (1ll<<id) + solve(v2,id-1,k);
	return solve(v,id-1,k);
}

int32_t main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, k;
	cin>> n >> k;
	vector<ll> v;
	for(int i = 0; i < n; i++)
	{
		cin>> a[i];
		ll sum = 0;
		for(int j = i; j > -1; j--) sum += a[j], v.PB(sum);
	}
		
	cout<< solve(v, 50, k) << endl;
}

Measured memory_bytes: 11244
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define downque(que)  priority_queue<ll> que;
#define upque(que) priority_queue<ll, vector<int>, greater<int>> que;
typedef long long ll;
const int MOD = 1e9+7;


int main(){
 int x; cin>>x;
 //A＾bのときbに対するAの値に限りがある
 int max_c=1;
 FOR(b,2,11){
   FOR(a,1,x){
    int c=pow(a,b);
    if(c>x)break;
    if(max_c<c)max_c=c;
   }
    
 }
    cout<<max_c<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
const int mod = 1e9 + 7;
const int maxn = 200105;

ll dp[1001][20001];
void go() {
	int n;
	cin >> n;
	vector<pair<pair<int,int>,int>>v;
	f(n) {
		int x, y, z;
		cin >> x >> y >> z;
		v.pb({{x,y},z});
	}
	sort(all(v),[](pair<pair<int,int>,int>x,pair<pair<int,int>,int>y) {
		return x.F.F + x.F.S < y.F.F + y.F.S;
	});
	int ptr = 0;
	ll mx = 0;
	for (auto &i : v) {
		int lim = i.F.S;
		for (int j = 0 ; j <= 20000 ; j++) {
			dp[ptr + 1][j] = max(dp[ptr][j], dp[ptr+1][j]);
			if (j<=lim) {
				dp[ptr+1][j + i.F.F] = dp[ptr][j] + i.S;
				mx = max(mx, dp[ptr][j] + i.S);
			}
		}
		ptr++;
	}
	cout << mx << '\n';
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int c = 0;
    int t;
    if (!c) {
        t = 1;
    }
    else {
        cin >> t;
    }
    while (t--) {
        go();
    }
    
}

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

int main()
{
    ll n ,m;
    cin>>n>>m;
    set<ll> s;
    for(int i=0;i<m;i++)
    {
        ll temp;
        cin>>temp;
        s.insert( temp);
    }
    ll * dp = new ll [n+1]();
    dp[0] =1;
    for(int i=1;i<=n;i++)
    {
        if( s.count(i) )
            continue;
        dp[i] = (dp[i] + dp[i-1] ) % 1000000007;
        if( i-2 >=0 )
        {
            dp[i] = (dp[i] + dp[i-2] ) % 1000000007;
        }
    }
    cout<<dp[n];
}

Measured memory_bytes: 9052
import java.util.Scanner;

public class Main {

	static Scanner scanner;

	public static void main(String[] args) {
	    scanner = new Scanner(System.in);
	    String s=gs();

	    //System.out.print("No");
	    if (s.length() >= 4 && s.substring(0, 4).equals("YAKI")) {
	    	System.out.print("Yes");
	    }else {
	    	System.out.print("No");
	    }


	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set
#define pll pair<ll, ll>
#define vll vector<ll>
#define mll map<ll, ll>

using namespace std;

const ll MOD = 1000000007LL;
const ll INF = (1LL << 60LL);

int main() {
  // std::cout << std::fixed << std::setprecision(10);

  ll a;
  scanf("%lld", &a);

  cout << (a + a * a + a * a * a) << endl;
}


Measured memory_bytes: 3680
// Author: HarshKumar

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const ll N = 1e6 + 6, M = 1e9 + 7;
ll p(ll a, ll b = M - 2, ll m = M)
{
    ll r = 1;
    while (b)
    {
        if (b % 2)
            r = r * a % m;
        a = a * a % m;
        b /= 2;
    }
    return r;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    ll n;
    cin >> n;
    cout << (p(10, n) - 2 * p(9, n) % M + p(8, n) + 10 * M) % M << '\n';
}

Measured memory_bytes: 3636