akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iomanip>


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

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

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

#define rep(i, a, b) for (int i=a; i<(b); i++)
#define rp(i, a) for (int i=0; i<(a); i++)
#define repd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define rpd(i,a) for (int i = (a)-1; i >= 0; i--)

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

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy

ll a[MX+10];
ll isUsed[MX+10];
ll fak(ll x){
    ll t = 1;
    rep(i,1,x+1) t = (t*i)%MOD;
    return t;
}


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout << std::setprecision(9);
    cout << std::fixed;

    ll n,m;
    cin >> n >> m;
    if(abs(n-m) > 1) {cout <<0<<endl;return 0;}
    if(abs(n-m) == 1){
        n = (n+m+1)/2;
        cout << (fak(n)*fak(n-1))%MOD<<endl;return 0;
    }
    ll ans = fak(n);
    ans = (ans*ans)%MOD;
    ans = (2*ans)%MOD;
    cout << ans << endl;
    return 0;
}

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


Measured memory_bytes: 256
#!/usr/bin/env python3

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

a, b = map(int, readline().split())

def f(x):
    s = 0
    for i in range(x // 4 * 4, x + 1):
        s ^= i
    return s

print(f(a - 1) ^ f(b))


Measured memory_bytes: 2940
#include <algorithm>　　　 //STL 通用算法
#include <bitset>　　　　　//STL 位集容器
#include <cctype>         //字符处理
#include <cerrno> 　　　　 //定义错误码
#include <cfloat>　　　　 //浮点数处理
#include <ciso646>         //对应各种运算符的宏
#include <climits> 　　　　//定义各种数据类型最值的常量
#include <clocale> 　　　　//定义本地化函数
#include <cmath> 　　　　　//定义数学函数
#include <complex>　　　　 //复数类
#include <csignal>         //信号机制支持
#include <csetjmp>         //异常处理支持
#include <cstdarg>         //不定参数列表支持
#include <cstddef>         //常用常量
#include <cstdio> 　　　　 //定义输入／输出函数
#include <cstdlib> 　　　　//定义杂项函数及内存分配函数
#include <cstring> 　　　　//字符串处理
#include <ctime> 　　　　　//定义关于时间的函数
#include <cwchar> 　　　　 //宽字符处理及输入／输出
#include <cwctype> 　　　　//宽字符分类
#include <deque>　　　　　 //STL 双端队列容器
#include <exception>　　　 //异常处理类
#include <fstream> 　　　 //文件输入／输出
#include <functional>　　　//STL 定义运算函数（代替运算符）
#include <limits> 　　　　 //定义各种数据类型最值常量
#include <list>　　　　　　//STL 线性列表容器
#include <locale>         //本地化特定信息
#include <map>　　　　　　 //STL 映射容器
#include <memory>         //STL通过分配器进行的内存分配
#include<new>            //动态内存分配
#include <numeric>         //STL常用的数字操作
#include <iomanip> 　　　 //参数化输入／输出
#include <ios>　　　　　　 //基本输入／输出支持
#include <iosfwd>　　　　　//输入／输出系统使用的前置声明
#include <iostream> 　　　//数据流输入／输出
#include <istream>　　　　 //基本输入流
#include <iterator>        //STL迭代器
#include <ostream>　　　　 //基本输出流
#include <queue>　　　　　 //STL 队列容器
#include <set>　　　　　　 //STL 集合容器
#include <sstream>　　　　 //基于字符串的流
#include <stack>　　　　　 //STL 堆栈容器
#include <stdexcept>　　　 //标准异常类
#include <streambuf>　　　 //底层输入／输出支持
#include <string>　　　　　//字符串类
#include <typeinfo>        //运行期间类型信息
#include <utility>　　　　 //STL 通用模板类
#include <valarray>        //对包含值的数组的操作
#include <vector>　　　　　//STL 动态数组容器
#define ll long long
using namespace std;
const int N=1000010;
ll n,top,minn,ans;
ll a[N],st[N],r[N],l[N];
int main(){
	scanf("%lld",&n);
	for (int i=1; i<=n; i++)
		scanf("%lld",&a[i]);
	for (int i=1; i<=n; i++){
		r[i]=n+1;
		l[i]=0;
	}
	for (int i=1; i<=n; i++){
		while (top&&a[st[top]]>a[i])
			r[st[top--]]=i;
		l[i]=st[top];
		st[++top]=i;
	}
	for (int i=1; i<=n; i++)
		ans+=(r[i]-i)*(i-l[i])*a[i];
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 9296
#include <iostream>
#include <vector>
#include<map>
#include<string>
#include<algorithm>
#include<sstream>
#include<cmath>
#include<typeinfo>
#include<queue>
#include<iomanip>
using namespace std;
int main() {
	int N;
	cin >> N;
	vector<int> a(N),b(N),c(N);
	for (int i = 0; i < N; i++) {
		cin >> a[i]>>b[i]>>c[i];
	}
	vector<vector<int>> dp(N,vector<int>(3,0));
	char past;
	dp[0][0] = a[0];
	dp[0][1] = b[0];
	dp[0][2] = c[0];
	for (int i = 0; i < N-1; i++) {
		dp[i + 1][0] = max(dp[i][1] + a[i+1], dp[i][2] + a[i+1]);
		dp[i + 1][1] = max(dp[i][0] + b[i+1], dp[i][2] + b[i+1]);
		dp[i + 1][2] = max(dp[i][0] + c[i+1], dp[i][1] + c[i+1]);
	}
	int max = 0;
	for (int i = 0; i < 3; i++) {
		if (max < dp[N - 1][i]) {
			max = dp[N - 1][i];
		}
	}
	cout << max<<endl;
}

Measured memory_bytes: 6912
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define double long double
using namespace std;
signed main(){
  int a;
  cin>>a;
  if(a<1200)
    cout<<"ABC";
  else if(a<2800)
    cout<<"ARC";
  else
    cout<<"AGC";
}

Measured memory_bytes: 256
import math
import queue
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=qb
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
def dq():
	return queue.deque()
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1

n = readInt()

def f(a,b):
	return math.floor(math.log10(max(a,b))+1)

ans = f(0,n)
for i in range(1,math.floor(pow(n,0.5)+1)):
	if n%i==0:
		ans = min(ans,f(i,n//i))

print(ans)

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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define pb push_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define BiSearchRangeNum(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y)turn idx;

int main() {
  int N, W;
  cin >> N >> W;
  vector<ll> w(N), v(N);
  vector<ll> dp(100001, 1e18);
  rep(i, 0, N) {
    cin >> w[i] >> v[i];
  }
  dp[0] = 0;

  rep(i, 0, N) {
    for (int j = 100000; j >= 0; j--) {
      if (j >= v[i]) {
        dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
      }
    }
  }

  for (int j = 100000; j >= 0; j--) {
    if (dp[j] <= W) {
      cout << j << endl;
      return 0;
    }
  }

  return 0;
};


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define piii pair<int,pii>
#define pll pair<ll,ll>
#define plii pair<ll,pii>
#define vi vector<int>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mx 100001
#define eps 0.00000000001
#define mod 1000000007
#define pi acos(-1)
#define inf 100000000
#define loop(i,b,n) for(int i=b;i<n;++i)
#define rev_loop(i,b,n) for(int i=b;i>=n;--i)
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int main()
{
    fio;
    ll n,x;
    cin>>n>>x;
    vector<ll> v1;
    ll a1,ans=0;
    loop(i,0,n)
    {
        cin>>a1;
        v1.pb(a1);
    }
    if(v1[0]>x)
    {
        ans+=v1[0]-x;
        v1[0]=x;
    }
    loop(i,1,n)
    {
        if(v1[i]+v1[i-1]>x)
        {
            ans+=(v1[i]+v1[i-1]-x);
            v1[i] -=(v1[i]+v1[i-1]-x);
        }
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 4248
#define _LIBCPP_DEBUG 0
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1e9 + 7;

int main(void) {

    int N, W; cin>>N>>W;
    vector<vector<ll>> item(N+1, vector<ll>(2, 0));
    vector<vector<ll>> ans(N+1,vector<ll>(W+1,0));
    for (int i = 1; i <= N; ++i) {
        cin >> item[i][0] >> item[i][1];
    }

    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= W; ++j) {
            if(j>=item[i][0]){
                int tmp = ans[i-1][j-item[i][0]]+item[i][1];
                ans[i][j] = max(ans[i-1][j-item[i][0]]+item[i][1],ans[i-1][j]);
            }else{
                ans[i][j] = max(ans[i][j-1],ans[i-1][j]);
            }
        }
    }


    cout<<ans[N][W]<<endl;
    return 0;
}

Measured memory_bytes: 80256
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); ++i)

int N;
int A[212345];

int main() {

	scanf("%d", &N);
	rep(i, N) scanf("%d", &A[i]);

	vector<int> nzero;
	vector<int> zero_count;

	int count = 0;
	rep(i, N) {
		if (A[i]) {
			nzero.push_back(A[i]);
			zero_count.push_back(count);
			count = 0;
		}
		else count++;
	}
	zero_count.push_back(count);

	ll ans = (ll)zero_count[0] * (zero_count[0] + 1) / 2;

	rep(l, nzero.size()) {
		int xorr = 0, sum = 0;
		for (int r = l; r < l + 21 && r < nzero.size(); ++r) {
			xorr ^= nzero[r];
			sum += nzero[r];
			if (xorr == sum) ans += (ll)(zero_count[l] + 1) * (zero_count[r + 1] + 1);
			else break;
		}
		ans += (ll)zero_count[l + 1] * (zero_count[l + 1] + 1) / 2;
	}

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

	return 0;
}


Measured memory_bytes: 2804
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
const ll MOD = 1e9+7;


int main(){
  string s;
  cin >> s;
  int sz = s.size();
  vector<pair<char, int>> A(26);
  if(sz<26){
      int p = 0;
    for(char c = 'a'; c<='z'; c++){
      A[p].first = c;
      A[p].second = 0;
      p++;
    }
    rep(i, sz){
      rep(j, 26){
        if(s.at(i)==A[j].first) {A[j].second = 1; break;}
      }
    }
    rep(i, 26){
      if(A[i].second==0) {s = s+A[i].first; break;}
    }
    cout << s << endl;
  }
  
  else {
    //vector<char> P;
    if(s=="zyxwvutsrqponmlkjihgfedcba") cout << -1 << endl;
    else {
      int r, g, e;
      vector<char> P;
      char v;
      for(r=25; r>=0; r--){
        if(s.at(r)<s.at(r-1)){
          P.push_back(s.at(r));
          //s.pop();
        }
        else {P.push_back(s.at(r));v=s.at(r-1); g=r; break;}
      }
    
    string o = "";
    int l=P.size();
    char m;  
    sort(P.begin(), P.end());  
    rep(i, l){
      if(P.at(i)>v) {m = P.at(i); break;}
    }  
    //cout << m << endl;  
    rep(i, g){
      if(i==g-1) o = o+m;
      else o = o+s.at(i); 
    }
    cout << o << endl;  
    }
  }
}

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

using namespace std;

int m, k;
int a[2000001];

int main(){
	scanf("%d%d", &m, &k);

	if(k >= (1 << m) || (m == 1 && k == 1)) printf("-1\n");
	else {
		if(m == 1 && k == 0){
			printf("0 0 1 1\n");
			exit(0);
		}

		int n = 1 << (m + 1);

		a[n / 2 - 1] = k;

		int ct = 0;
		for(int i = 0; i < (n / 2 - 1); i++){
			if(ct == k) ct++;
			a[i] = ct;
			++ct;
		}

		ct = (1 << m) - 1;
		for(int i = n/2; i < n - 1; i++){
			if(ct == k) --ct;

			a[i] = ct;
			--ct;
		}
		a[n - 1] = k;

		for(int i = 0; i < n; i++) printf("%d ", a[i]);

		printf("\n");
	}
	
	return 0;
}

Measured memory_bytes: 2816
#include <iostream>
#include <queue>

using namespace std;

const int INF = 100000000;
const int MAX_X = 1000, MAX_Y = 1000, MAX_N = 9;
typedef pair<int, int> P;

int X, Y, N;
char grid[MAX_X+5][MAX_Y+5];
int dp[MAX_X+5][MAX_Y+5];
P chease_pos[MAX_X+5];
int dx[4] = {1, 0, -1,  0};
int dy[4] = {0, 1,  0, -1};

int bfs(P start_pos, P end_pos) {
    // search the min path from start_pos to end_pos
    queue<P> que;

    // initialize
    for(int i = 0; i < X; i++) {
        for(int j = 0; j < Y; j++) {
            dp[i][j] = INF;
        }
    }

    // first push
    que.push(start_pos);
    dp[start_pos.first][start_pos.second] = 0;

    while(que.size()) {
        // pop
        P p = que.front(); que.pop();

        // stop condition
        if(p.first == end_pos.first &&
           p.second == end_pos.second) {
            break;
        }

        // search
        for(int i = 0; i < 4; i++) {
            int nx = p.first+dx[i];
            int ny = p.second+dy[i];

            // grid check
            if(nx >= 0 && nx < X && ny >= 0 && ny < Y) {
                // check  X or not
                if(grid[nx][ny] != 'X') {
                    // whether first visit or not
                    if(dp[nx][ny] == INF) {
                        dp[nx][ny] = dp[p.first][p.second] + 1;
                        que.push(P(nx, ny));
                    }
                }
            }
        }

    }

    return dp[end_pos.first][end_pos.second];
}

int solve() {
    // input
    cin >> X >> Y >> N;
    for(int i = 0; i < X; i++) {
        cin >> grid[i];
    }

    P start_pos, end_pos;
    // search where chease exists and start_pos
    for(int i = 0; i < X; i++) {
        for(int j = 0; j < Y; j++) {
            if(grid[i][j] == 'S') {
                start_pos = P(i, j);
            } else if(grid[i][j] != 'X' && grid[i][j] != '.') {
                int num = (int)grid[i][j] - (int)'0';
                chease_pos[num] = P(i, j);
            }
        }
    }

    int count = 0;
    for(int i = 0; i < N; i++) {
        // set pos
        if(i != 0) {
            start_pos = end_pos;
        }
        end_pos = chease_pos[i+1];

        // bfs
        count += bfs(start_pos, end_pos);
    }

    cout << count << endl;
    return 0;
}


int main() {
    solve();
    return 0;
}

Measured memory_bytes: 6160
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <numeric>
#include <string>
#include <cassert>
#include <bitset>

using namespace std;
typedef long long ll;

// comb(n, 2)
int func(int n) {
  return n * (n - 1) / 2;
}

int main() {
  int N, M;
  cin >> N >> M;
  int ans = func(N) + func(M);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import copy
def prime_decomposition(n, table):
  i = 2
  while i * i <= n:
    c = 0
    while n % i == 0:
      n /= i
      c+=1
    if c!=0:
        if i not in table:
            table[i] = c
        else:
            table[i] += c
    i += 1
  if n > 1:
    if int(n) not in table:
        table[int(n)] = 1
    else:
        table[int(n)] += 1
  return table

table = {}
for i in range(int(input().strip())):
    table = prime_decomposition(i+1, table)

def find_224(ns, ttt, depth, counter):
    n_ttt = copy.deepcopy(ttt)
    if ns[depth] == 4:
        ccc = 0
        for i in n_ttt:
            if n_ttt[i] >= 4:
                ccc += 1
        return (ccc * (ccc -1) )// 2

    counter = 0
    for i in ttt:
        if ttt[i] >= ns[depth]:
            tmp = n_ttt[i]
            del n_ttt[i]
            counter += find_224(ns, n_ttt, depth + 1, counter)
            n_ttt[i] = tmp
    return counter

def find_n(ns, ttt, depth, counter):
    n_ttt = copy.deepcopy(ttt)
    counter = 0
    for i in ttt:
        if ttt[i] >= ns[depth]:
            if len(ns) == depth + 1:
                counter += 1
            else:
                tmp = n_ttt[i]
                del n_ttt[i]
                counter += find_n(ns, n_ttt, depth + 1, counter)
                n_ttt[i] = tmp
    return counter

# 553
res = 0
res += find_224([2, 4], table, 0, 0)

res += find_n([14, 4], table, 0, 0)
res += find_n([24, 2], table, 0, 0)
res += find_n([74], table, 0, 0)
print(res)


Measured memory_bytes: 38384
l = input().split()

W = int(l[0])
H = int(l[1])
x = int(l[2])
y = int(l[3])
r = int(l[4])

if x+r<=W and x-r>=0 and y+r<=H and y-r>=0:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 5596
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <new>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef int64_t i64;

static const int NMAX = 200000;

static int N;
static int B[NMAX];
static vector<int> E[NMAX], R[NMAX];
static int O[NMAX];
static int A[NMAX];
static vector<int> C;
static int _;
static vector<int> M;

static bool test(int a) {
  A[C[0]] = a;
  for(int i = 1; i <= C.size(); i++) {
    auto u = C[i != C.size() ? i : 0];
    _++;
    for(auto v : E[u]) M[A[v]] = _;
    int b;
    for(b = 0; M[b] == _; b++);
    A[u] = b;
  }
  return A[C[0]] == a;
}

static bool test() {
  _++;
  for(auto v : E[C[0]]) if(A[v] >= 0) M[A[v]] = _;
  int a;
  for(a = 0; M[a] == _; a++);
  if(test(a)) return true;
  for(a++; M[a] == _; a++);
  return test(a);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> B[i]; B[i]--;
    E[B[i]].push_back(i);
    R[i].push_back(B[i]);
    O[B[i]]++;
    A[i] = -1;
  }
  M.resize(N);
  {
    vector<int> s;
    for(int i = 0; i < N; i++) if(O[i] == 0) s.push_back(i);
    while(!s.empty()) {
      auto u = s.back();
      s.pop_back();
      _++;
      for(auto v : E[u]) M[A[v]] = _;
      int a;
      for(a = 0; M[a] == _; a++);
      A[u] = a;
      for(auto w : R[u]) if(--O[w] == 0) s.push_back(w);
    }
  }
  for(int i = 0; i < N; i++) {
    if(A[i] != -1) continue;
    for(int j = i; A[j] == -1; j = B[j]) {
      C.push_back(j);
      A[j] = -2;
    }
    if(!test()) {
      cout << "IMPOSSIBLE" << endl;
      return 0;
    }
    C.clear();
  }
  cout << "POSSIBLE" << endl;
  return 0;
}

Measured memory_bytes: 25228
open Scanf
open Printf
open Array

let bit k =
  let r = init 40 (fun i -> let p = 1 lsl i in k land p / p)
  in mapi (fun i _ -> r.(39-i)) r
let print_iarr a = iter (printf "%d ") a; print_newline ()

let () = scanf " %d %d" @@ fun n k ->
  let a = init n (fun _ -> scanf " %d" @@ fun v -> v) in
  let count = make_matrix 2 40 0 in
  iter (fun v ->
    let b = bit v in
    iteri (fun i w ->
      count.(w).(i) <- count.(w).(i) + 1
    ) b;
  ) a;
  (* print_iarr count.(0);
  print_iarr count.(1); *)
  let score i c = (1 lsl (39-i)) * c in
  let each =
    init 40 (fun i -> score i @@ max count.(0).(i) count.(1).(i))
  in
  (* print_iarr each; *)
  let cml = map (fun v -> v) each in
  for i=38 downto 0 do
    cml.(i) <- cml.(i) + cml.(i+1)
  done;
  (* print_iarr cml; *)
  let r = ref 0 in
  let sum = ref 0 in
  bit k |> iteri (fun i v ->
    if v=1 then (
      let c = !sum + score i count.(1).(i)
        + if i+1>=40 then 0 else cml.(i+1)
      in r := max !r c
    );
    sum := !sum + score i count.(1-v).(i);
  );
  print_int @@ max !r !sum




Measured memory_bytes: 5248
#include<iostream>
#include<cstdio>
#include<algorithm>
typedef long long ll;
const int MAXN=1e5+5;

int n,a[MAXN];

int main()
{
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",a+i);
	std::sort(a+1,a+n+1);
	int x,y;
	for(i=n;i;i--) if(a[i]==a[i-1]) {x=a[i],i-=2;break;}
	for(;i;i--) if(a[i]==a[i-1]) {y=a[i],i-=2;break;}
	printf("%lld",(ll)x*y);
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i)
#define all(a) (a).begin(), (a).end()

int N;

int f(int n) {
  if (n / 10 == 0) return n;
  return f(n / 10);
}

int main() {
  cin >> N;
  vector<ll> dp(N + 1, 0);
  for (int i = 1; i <= N; ++i) {
    ll diff = 0;

    int l = (i % 10);
    if (l == 0) {
      dp[i] = dp[i - 1];
      continue;
    }
    int d = 1;
    int r = i;
    while (r / 10 != 0) {
      d++;
      r /= 10;
    }
    if (l == r) {
      diff += 1 + (l != i);  // 1桁
      if (d >= 2) {
        diff += ((pow(10, d - 2) - 1) / 9) * 2;
        diff += ((i - pow(10, d - 1) * r - l) / 10) * 2;
        diff += 1;
      }
    } else {
      diff += 2 * (pow(10, d - 1 - (l > r)) - 1) / 9;
    }

    dp[i] = diff + dp[i - 1];
  }

  cout << dp[N] << endl;

  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define _for(i,b,e) for (common_type_t<decltype(b),decltype(e)> i = (b), i ## __end = (e); i < i ## __end; ++ i)
#define FOR(...)   _for (__VA_ARGS__)
#define rep(i,n)   FOR (i, size_t{}, n)
#define ALL(x)     begin (x), end (x)
using namespace std;
using ll = int64_t;

auto main () -> int
{
  cin.tie (nullptr);
  ios::sync_with_stdio (false);

  ll n;
  cin >> n;
  set <ll> ans;
  if (n == 2)
  {
    cout << 1 << endl;
    return 0;
  }

  for (ll k = 2; k * k <= n; ++ k)
  {
    if (n % k == 0)
    {
      auto x = n;
      while (x % k == 0) x /= k;
      if (x % k == 1) ans.emplace (k);
    }
    else if (n % k == 1)
    {
      ans.emplace (k);
    }
    if (n - 1 == n / k * k)
    {
      ans.emplace (n / k);
    }
  }
  ans.emplace (n - 1);
  ans.emplace (n);
#ifdef LOCAL
  for (auto && elem : ans)
  {
    cerr << elem << endl;
  }
#endif
  cout << ans.size () << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
const int maxn = 1e5 + 10;

int a[maxn];

int divide(int L, int R){
	if (L > R)
		return 0;
	if (R - L + 1 <= 2)
		return 1;
	int dec = L, inc = L;
	for (int i = L + 1; i <= R; i++){
		if (a[i] > a[i - 1])
			break;
		dec = i;
	}
	for (int i = L + 1; i <= R; i++){
		if (a[i] < a[i - 1])
			break;
		inc = i;
	}
	return divide(max(dec, inc) + 1, R) + 1;
}

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	cout << divide(1, n) << endl;
}


Measured memory_bytes: 1280
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn read_col<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

fn main() {
    let n: usize = read();
    let av: Vec<u32> = read_vec();
    let mut ans: u32 = 0;
    for a in av {
        ans += a - 1;
    }
    println!("{}", ans);
}


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

// 配列の出力
void trace(int A[], int n) {
  for (int i=0; i<n; i++) {
    if (i != n-1) {
      cout << A[i] << " ";  
    } else {
      cout << A[i] << endl;
    }
  }
}

// 挿入ソート(0オリジン配列)
void insertionSort(int A[], int n) {
  for (int i=1; i<n; i++) {
    int v = A[i];
    int j = i-1;
    while (j >= 0 && A[j] > v) {
      A[j+1] = A[j];
      j--;
    }
    A[j+1] = v;
    trace(A, n);
  }
}

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

  trace(A, n);
  insertionSort(A, n);

  return 0;
}


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

int main(){
    char in[4];
    cin >> in;

    int n = 0;
    for(int i = 0;i < 4;i++){
        if(in[i] == '+'){
            n++;
        }else if(in[i] == '-'){
            n--;
        }
    }
    cout << n << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

int main() {
    ll K;
    cin >> K;
    ll now = 7;
    if (now % K == 0) {
        cout << 1 << endl;
        return 0;
    }

    rep(i, 10000000) {
        now *= 10;
        now += 7;
        if (now % K == 0) {
            cout << i+2 << endl;
            return 0;
        }
        now%=K;
    }
    cout << -1 << endl;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#define fastio cin.tie(0); ios::sync_with_stdio(0)
#define multitc int _t; cin>>_t; while(_t--)
#define arrin(arr, n, type) arr.assign(n,type()); for(auto& i : arr) cin>>i;
#define all(x) (x).begin(), (x).end()
const int dir[9][2] = {{0,-1},{-1,0},{0,1},{1,0},{1,1},{-1,-1},{1,-1},{-1,1},{0,0}};
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll INF = 1e15+7;
const ll MOD = 998244353;
using namespace std;
using namespace __gnu_pbds;
int nextInt(){int x; cin>>x; return x;}
ll nextLong(){ll x; cin>>x; return x;}
template<typename T>
void arrin2d(vector<vector<T>>& arr, int y, int x)
{
    arr.assign(y,vector<T>(x));
    for(int i=0;i<y;++i)
    {
        for(int j=0;j<x;++j)
        {
            cin>>arr[i][j];
        }
    }
}
 
//using template
//code goes here
 
ll x, y, a, b, c;
vector<ll> p, q, r;
int main()
{
    fastio;
    cin>>x>>y>>a>>b>>c;
    arrin(p,a,ll);
    arrin(q,b,ll);
    arrin(r,c,ll);
    sort(p.rbegin(),p.rend());
    sort(q.rbegin(),q.rend());
    sort(r.rbegin(),r.rend());
    priority_queue<ll,vector<ll>,greater<ll>> apq, bpq;
    ll sum = 0;
    for(int i=0;i<x;++i)
    {
        apq.push(p[i]);
        sum += p[i];
    }
    for(int j=0;j<y;++j)
    {
        bpq.push(q[j]);
        sum += q[j];
    }
    for(int i=0;i<c;++i)
    {
        bool dea = apq.top() < bpq.top();
        if(dea)
        {
            if(apq.top() < r[i])
            {
                sum -= apq.top();
                apq.pop();
                sum += r[i];
                apq.push(r[i]);
            }
        }
        else
        {
            if(bpq.top() < r[i])
            {
                sum -= bpq.top();
                bpq.pop();
                sum += r[i];
                bpq.push(r[i]);
            }
        }
    }
    cout<<sum;
}

Measured memory_bytes: 4852
K, N = map(int, input().split())
A = list(map(int, input().split()))

lenmax = 0
for i in range(N-1):
    a = A[i+1] - A[i]
    #print(a)
    if a > lenmax:
        lenmax = a

#print(A[len(A)-1],A[0])
if K - (A[len(A)-1] - A[0]) > lenmax:
    lenmax = K - (A[len(A)-1] - A[0])

print(K-lenmax)

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

int main() {
	int n;
	cin>>n;
	pair<int,int>p[n+3];
	for(int i=0;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		p[i]={x,y};
	}
	sort(p,p+n);
	cout<<p[n-1].first+p[n-1].second;
	return 0;
}

Measured memory_bytes: 1024
#pragma region template 2.4
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pq_asc = priority_queue<T, vector<T>, greater<T>>;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP1(i, n) for (ll i = 1; i <= (n); ++i)
#define FOR(i, a) for (auto &i : a)
#define CH(f, x, y) x = f(x, y)
#define IN(T, x) \
    T x;         \
    cin >> x;
#define AIN(T, a, n) \
    vector<T> a(n);  \
    FOR(i, a)        \
    cin >> i;
#define A2IN(T1, a, T2, b, n) \
    vector<T1> a(n);          \
    vector<T2> b(n);          \
    REP(i, n)                 \
    cin >> a[i] >> b[i];
#define OUT(x) cout << (x) << endl;
#define FOUT(x) cout << fixed << setprecision(15) << (x) << endl;
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define DUMPA(a)          \
    cout << #a << " = {"; \
    JOUT(ALL(a), ", ", cout) << "}" << endl;

template <typename T>
ostream &JOUT(T s, T e, string sep = " ", ostream &os = cout)
{
    if (s != e)
    {
        os << *s;
        ++s;
    }
    while (s != e)
    {
        os << sep << *s;
        ++s;
    }
    return os;
}

ostream &YES(bool cond, string yes = "Yes", string no = "No", ostream &os = cout)
{
    if (cond)
    {
        os << yes << endl;
    }
    else
    {
        os << no << endl;
    }
    return os;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << '[';
    JOUT(ALL(v), ", ", os) << ']';
    return os;
}

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#pragma endregion template

int main()
{
    IN(ll, N);
    AIN(ll, L, N);
    SORT(L);
    ll s = 0;
    REP(i, N - 1)
    {
        s += L[i];
    }
    YES(L[N - 1] < s);
}

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

void solve(long long N, long long A, long long B) {
    if (B < A) {
        cout << 0 << endl;
        return;
    }
    if (N == 1) {
        if (A != B) {
            cout << 0 << endl;
            return;
        } else {
            cout << 1 << endl;
            return;
        }
    }
    ll min = (N - 1) * A + B;
    ll max = (N - 1) * B + A;
    cout << (max - min) + 1 << endl;
    return;
}

int main() {
    long long N;
    scanf("%lld", &N);
    long long A;
    scanf("%lld", &A);
    long long B;
    scanf("%lld", &B);
    solve(N, A, B);
    return 0;
}


Measured memory_bytes: 256
def enc(k,m):
    a = list(m.encode("ascii"))
    for i in range(0,len(a)):
        if ord('a') <= a[i] <= ord('z') - k:
            a[i] = a[i] + k
        elif ord('z') - k < a[i] <= ord('z'):
            a[i] = a[i] + k - (ord('z') - ord('a') + 1)
        elif ord('A') <= a[i] <= ord('Z') - k:
            a[i] = a[i] + k
        elif ord('Z') - k < a[i] <= ord('Z'):
            a[i] = a[i] + k - (ord('Z') - ord('A') + 1)
        else:
            pass
    b = bytes(a).decode("ascii")
    return b


N = int(input())
S = input()
print(enc(N,S))

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
int n,a,b,i,im,ii,ans=0;
int main()
{
	cin>>n>>a>>b;
	for (i=1;i<=n;i++)
	{
		im=0;
		ii=i;
		while(ii!=0)
		{
			im+=ii%10;
			ii/=10;
		}
		if(im>=a&&im<=b)
			ans+=i;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
# 10分くらい
# 999を99と間違って理解.よく読め！

a,b = map(int, input().split())

l= [1]
for i in range(1,1000):
    x = l[i-1] + i+1
    l.append(x)

for j in range(len(l)-1):
    if l[j+1] - l[j] == b-a:
        print(l[j] - a)
        break


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

using namespace std;
typedef long long ll;
using Graph =vector<int>;
typedef pair<int,int> P;
const ll MAX_N=131072;
const ll INF=1000000;
const ll MOD=1000000007;
ll dp[51][51][2510];
int main(){
  int N,A;cin>>N>>A;
  int x[N];
  rep(i,N) cin>>x[i];
  dp[0][0][0]=1;
  for(int i=1;i<=N;++i){
    for(int j=0;j<=i;++j){
      rep(k,2501){
        dp[i][j][k]+=dp[i-1][j][k];
        if (i-1>=0 && j-1>=0 && k-x[i-1]>=0) dp[i][j][k]+=dp[i-1][j-1][k-x[i-1]];
      }
    }
  }
  ll ans=0;
  for(int j=1;j<=N;++j){
    ans+=dp[N][j][A*j];
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 49280
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

int cnt[100002];

int main()
{
#ifdef LOCAL_JUDGE
    freopen("A.in", "r", stdin);
#endif
    int n;
    while (scanf("%d", &n) == 1) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0, a; i < n; ++ i) {
            scanf("%d", &a);
            for (int j = 0; j < 3; ++ j) {
                cnt[a + j] ++;
            }
        }
        printf("%d\n", *std::max_element(cnt, cnt + 100002));
    }
}

Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;

#ifdef ENABLE_LL
#define int long long
#endif

#ifdef ENABLE_LL
#define I "%lld"
#define II "%lld%lld"
#define III "%lld%lld%lld"
#define IIII "%lld%lld%lld%lld"
#define IN "%lld\n"
#define IIN "%lld%lld\n"
#define IIIN "%lld%lld%lld\n"
#define IIIIN "%lld%lld%lld%lld\n"
#else
#define I "%d"
#define II "%d%d"
#define III "%d%d%d"
#define IIII "%d%d%d%d"
#define IN "%d\n"
#define IIN "%d%d\n"
#define IIIN "%d%d%d\n"
#define IIIIN "%d%d%d%d\n"
#endif

#ifdef __LOCALE__
#define see(a) std::cout << #a << "=" << a << std::endl
#define ses(a) std::cout << #a << "=" << a << " " 
#else
#define see(a) //std::cout << #a << "=" << a << std::endl
#define ses(a)
#endif
#define repe(a,b) for (int a=0;a<(int)b.size();a++)
#define rep(i,n) for (int i=0;i<n;i++)
#define repa(i,n) for (int i=1;i<=n;i++)
#define repi(i,a,b) for (int i=a;i<=b;i++) 
#define repb(i,a,b) for (int i=a;i>=b;i--)
typedef pair < int , int > pr;
typedef pair < pr  , int > prr;
#define L first
#define R second
template <class T> inline bool checkMin(T& a , T b) { return (a > b ? a=b,1 : 0); }
template <class T> inline bool checkMax(T& a , T b) { return (a < b ? a=b,1 : 0); }
class Scanner{ private: istream& ist;public: Scanner(istream& in):ist(in){} string next(){ string r; ist >> r; return r; } string nextLine(){ string r; getline(ist,r); return r; } int nextInt(){ int r; ist >> r; return r; } double nextDouble(){ double r; ist >> r; return r; }};
Scanner sc(cin);

void init() {
    int n, k;
    scanf(II,&n,&k);
    puts(n*500 >=k ? "Yes" : "No");
}

void solve() {

}


#ifdef ENABLE_LL
#undef int
#endif
int main(){
    init();
    solve();
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {

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

        String abcd = sc.next();
        int n = abcd.length() - 1;
        StringBuilder res = null;
        for (int bit = 0; bit < (1 << n); bit++) {
            res = new StringBuilder();
            char num = abcd.charAt(0);
            res.append(num);
            int ans = num - '0';
            for (int i = 0; i < n; i++) {
                num = abcd.charAt(i + 1);
                if (((bit>> i) & 1 ) == 1) {
                    res.append('+');
                    res.append(num);
                    ans += num - '0';
                } else {
                    res.append('-');
                    res.append(num);
                    ans -= num - '0';
                }
            }
            if (ans == 7) {
                break;
            }
        }
        System.out.println(res.toString() + "=7");
    }
}


Measured memory_bytes: 23764
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())

U = 10**6 + 100
div = np.arange(1,U,dtype=np.int64)
div = div[N%div==0]

div = np.union1d(div,N//div)

answer = (div + (N//div)).min() - 2
print(answer)

Measured memory_bytes: 29032
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  double A,B,H,M;
  cin >> A >> B >> H >> M;
   
  double kakuA = 0.5*3.14159265358979 - 2 * 3.14159265358979 / 12.0 * (H+M/60);
  double kakuB = 0.5*3.14159265358979 - 2 * 3.14159265358979 / 60.0 * M;
   
  double xa = A*cos(kakuA);
  double ya = A*sin(kakuA);
  double xb = B*cos(kakuB);
  double yb = B*sin(kakuB);
  
  double ans = pow(xa-xb,2) + pow(ya-yb,2);
  ans = sqrt(ans);
  //cout << xa <<endl;
  //cout << ya <<endl;
  //cout << xb <<endl;
  //cout << yb <<endl;

  cout << std::setprecision(10) << ans << endl;
  return 0;
}

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

int main(){
    string s;
    cin >> s;
    bool b = true;
    for(int i = 0; i < s.length(); i++){
        if(i%2 == 0)    b &= (s[i] != 'L');
        else            b &= (s[i] != 'R');
    }
    cout << (b ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int D = sc.nextInt();
    int[][] X = new int[N+1][D+1];
    int[][] p = new int[N+1][N+1];
    int count =0;
    for (int i =1; i<=N; i++) {
      for (int j =1; j<=D; j++) {
        X[i][j] = sc.nextInt();
      }
    }
    for (int i=1; i<=N; i++) {
      for (int j=i+1; j<=N; j++) {
        for (int k=1; k<=D; k++) {
          p[i][j] += (X[i][k] - X[j][k]) * (X[i][k] - X[j][k]);
        }
        for (int l=1; l<=150; l++) {
          if(p[i][j] == l * l) {
            count++;
            break;
          }
        }
      }
    }
    System.out.println(count);
  }
}

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

using namespace std;

typedef pair< int,int > PII;
typedef long long int lo;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(lo i=1;i<=n;i++)
#define mid (bas+son)/2

const lo MAX = -1000000000000000000; 
const lo MIN = 1000000000000000000; 
const lo inf = 1000000000; 
const lo KOK = 100000; 
const lo LOG = 30; 
const lo li = 1000005; 
const lo mod = 1000000007; 

lo n,m,cev,b,a[li],dp[li],k;
string s;
vector<int> v;

lo f(lo sira){
	lo cevap=MIN;
	if(sira>n) return MIN;
	if(sira==n) return 0;
	if(~dp[sira]) return dp[sira];
	for(int i=1;i<=k;i++){
		cevap=min(cevap,(f(sira+i)+abs(a[sira+i]-a[sira])));
	}
	//~ cout<<sira<<" "<<cevap<<endl;
	return dp[sira]=cevap;
}

int main(){
	memset(dp,-1,sizeof(dp));
	scanf("%lld %lld",&n,&k);
	FOR{
		scanf("%lld",&a[i]);
	}
	printf("%lld\n",f(1));
	return 0;
}


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

int main() {
	int n;
	cin>>n;
	int a[n];
	int count=0;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	
	for(int i=0;i<n-2;i++)
	{
			if(a[i+1]>a[i] && a[i+1]<a[i+2] || a[i+1]<a[i] && a[i+1]>a[i+2])
			{  
				count++;
			}
			else
			{
				continue;
			}
	}
	cout<<count<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007
#define MODA 998244353
#define MAXN 3002

using namespace std;

typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

long long modinv(long long a, long long m=MOD) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
    /*MODの割り算の際に
    a/＝b;
    を
    a *= modinv(b,MOD);
    とする。
        */
}

ll N,S;

ll A[MAXN];

ll dp[MAXN][MAXN];

int main(){
    ll mod = 998244353;
    cin >> N >> S;
    rep(i,N) cin >> A[i];
    rep(i,N+1)rep(j,S+1) dp[i][j] = 0;
    dp[0][0] = 1;
    rep(i,N) {
        rep(j,S+1) {
            dp[i+1][j] += 2* dp[i][j];
            dp[i+1][j] %= mod;
            if(j+A[i] <= S) {
                dp[i+1][j+A[i]] += dp[i][j];
                dp[i+1][j+A[i]] %= mod;
            }
        }
    }
    cout << dp[N][S] << endl;;
    
    return 0;
}

Measured memory_bytes: 73984
#include <iostream>
using namespace std;
int main(){
	int A,B,C,D;
	cin >> A >> B >> C >> D;
	while(1){
		C -= B;
		if(C<=0){
			cout << "Yes" << endl;
			return 0;
		}
		A -= D;
		if(A<=0){
			cout << "No" << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 3636
#include <iostream>
using namespace std;
int main(void){
    
    int a,b,c,d,e;
    d = 0;
    e = 0;
    cin >>a>>b>>c;
    
    while(1){
        if(d >= c){
            break;
        }
        d = a+d;
        e = e+1;
        if(e%7 == 0){
            d = d+b;
        }
        
        
    }
    cout <<e<<endl;
}



Measured memory_bytes: 3112
# n = 2*10**5
# X = "10"*10**5
n = int(input())
X = input()
c = 0
cnt = 0
for i,x in enumerate(X):
    c += (1<<(n-i-1))*int(x)
    cnt += int(x)

amari_cnt_p = c % (cnt+1)
if cnt != 1:
    amari_cnt_m = c % (cnt-1)

dp = []
for d in range(n):
    if cnt == 1 and X[d] == '1':
      dp.append(-1)
      continue

    if X[d] == "0":
        amari = (amari_cnt_p + pow(2,n-d-1,cnt+1))%(cnt+1)
    else:
        if cnt != 1:
            amari = (amari_cnt_m - pow(2,n-d-1,cnt-1))%(cnt-1)
        else:
            amari = 0
    dp.append(amari)

memo = [-1]*(2*10**5+10)
memo[0] = 1
def calc(n):
    if n == -1:
        return 0
    if n == 0:
        return 1
    if memo[n] != -1:
        return memo[n]
    cnt = 1
    while n > 0:
        c = bin(n).count("1")
        n %= c
        cnt += 1
    memo[n] = cnt
    return cnt

for d in dp:
    ans = calc(d)
    print(ans)


Measured memory_bytes: 113544
# 焼きなまし（1000から線形に落とす）

from time import time
from math import exp
key = 1
rnd_mod = 12345678901234567891
rnd_x = 9876543210987654321 + 1234567890123456789 * key % rnd_mod
def rnd():
    global rnd_x
    rnd_x = rnd_x**2 % rnd_mod
    return (rnd_x>>10) % (1<<40)
def randrange(a, b=-1):
    if b > 0: return randrange(b-a) + a
    return rnd() % a

def calc():
    s = 0
    last = [-1] * 26
    for i, t in enumerate(A):
        s += S[i][t]
        last[t] = i
        for j, c in enumerate(C):
            s -= c * (i - last[j])
    return s

sTime = time()
D = int(input())
C = [int(a) for a in input().split()]
S = [[int(a) for a in input().split()] for _ in range(D)]
A = [randrange(26) for _ in range(D)]
# A = [0] * D
# A = [0, 16, 12, 13, 12]
# A = [0, 16, 12, 13, 19]
ans = calc()
# print("ans =", ans)
loop = 0
while 1:
    if loop % 100 == 0:
        tt = time() - sTime
        if tt > 1.8:
            break
        T = 4000 - 3500 * tt / 1.8
    loop += 1
    d = randrange(D)
    i = A[d]
    for k in range(d)[::-1]:
        if A[k] == i:
            prev = k
            break
    else:
        prev = -1
    for k in range(d + 1, D):
        if A[k] == i:
            prev_ne = k
            break
    else:
        prev_ne = D
    for j in range(26):
        t = S[d][j] - S[d][i]
        for k in range(d)[::-1]:
            if A[k] == j:
                new = k
                break
        else:
            new = -1
        for k in range(d + 1, D):
            if A[k] == j:
                new_ne = k
                break
        else:
            new_ne = D
        t += C[j] * (d - new) * (new_ne - d) - C[i] * (d - prev) * (prev_ne - d)
        if (T < 1 and t > 0) or (T >= 1 and randrange(1 << 10) < exp(max(min(t / T, 0), -10)) * (1 << 10)):
            A[d] = j
            ans += t
            prev, prev_ne = new, new_ne
            i = j
            if 0:
                print("A =", A)
                print("ans =", ans)
                print("calc =", calc())
            
            

print(*[a + 1 for a in A], sep = "\n")
if 0:
    print(ans)
    print("A =", A)


Measured memory_bytes: 77716
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

N, D = map(int, input().split())

x = []
for i in range(N):
    x.append(list(map(int, input().split())))

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

ans = 0
for i in range(N):
    for j in range(i+1,N):
        d = 0
        for k in range(D):
            d += (x[i][k] - x[j][k])**2
        if abs(math.sqrt(d) - int(math.sqrt(d))) < 10**(-9):

            ans += 1
print(ans)


Measured memory_bytes: 78016
#include<stdio.h>
 
int main() {
	int d[2], m[2], checker = 0;
	scanf("%d %d", &m[0], &d[0]);
	scanf("%d %d", &m[1], &d[1]);
	if (m[0]+1 == m[1]) {
		if (d[1] == 1) {
			checker = 1;
		}
	}
	else if (m[0] == 12) {
		if (d[0] == 31) {
			checker = 1;
		}
	}
	printf("%d", checker);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	vector<vector<int>> c(3, vector<int>(3));
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> c.at(i).at(j);
		}
	}

	bool flag = true;
	int diff1 = c.at(1).at(0) - c.at(0).at(0);
	int diff2 = c.at(2).at(0) - c.at(0).at(0);
	for (int i = 0; i < 3; i++) {
		if(c.at(0).at(i) + diff1 != c.at(1).at(i)) flag = false;
		if(c.at(0).at(i) + diff2 != c.at(2).at(i)) flag = false;
	}

	if(flag == true) cout << "Yes" << endl;
	else cout << "No" << endl;

 	return 0;
 }

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <math.h>
#include <algorithm>

using namespace std;

int a[3];

int main(){
    int ans;

    cin >> a[0] >> a[1] >> a[2];
    sort(a, a + 3);

    ans = a[2] - a[1];
    ans += a[1] - a[0];

    cout << ans;

    return 0;
}

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

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()

#define MOO(i, a, b) for(int i=a; i<b; i++)
#define M00(i, a) for(int i=0; i<a; i++)
#define MOOd(i,a,b) for(int i = (b)-1; i >= a; i--)
#define M00d(i,a) for(int i = (a)-1; i>=0; i--)

#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << '\n', 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << "\n";
#define _ << " _ " <<

template<class T> bool ckmin(T& a, const T& b) {return b < a ? a = b, 1 : 0;}
template<class T> bool ckmax(T& a, const T& b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;

bool overflow(ll a, ll b) {
    unsigned long long aa = a;
    unsigned long long bb = b;
    ll val = aa*bb;
    if(aa == val/bb) return 0;
    return 1;
}

ll x, k, d;

int main() { FAST
    cin >> x >> k >> d;
    if(x > 0) x = -x;
    if(!overflow(k, d) && x+k*d <= 0) {
        finish(abs(x+k*d));
    }
    ll y = (-x/d)+1;
    assert(x+y*d > 0);
    assert(x+(y-1)*d <= 0);
    if(y%2 == k%2) {
        finish(x+y*d);
    } else {
        finish(abs(x+(y-1)*d));
    }
}



Measured memory_bytes: 3636