akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}

int main(){
  int n;
  cin >> n;
  int ans = 0;
  int count = 0;
  while(true){
    if(count * count > n){
      cout << ans << endl;
      return 0;
    }
    ans = count * count;
    count++;
  }
  return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Spyderエディタ

これは一時的なスクリプトファイルです
"""

class Dice():
    
    #      e[4]
    # e[3] e[0] e[2] e[5]
    #      e[1]

    #      m[4]
    # m[3] m[0] m[2]
    #      m[1]
    #      m[5]
    
    def __init__(self, nums):
        self.pos = nums
    
    def rot_E(self):
        e = self.pos
        self.pos = [e[3], e[1], e[0], e[5], e[4], e[2]]

    def rot_W(self):
        e = self.pos
        self.pos = [e[2], e[1], e[5], e[0], e[4], e[3]]

    def rot_S(self):
        e = self.pos
        self.pos = [e[4], e[0], e[2], e[3], e[5], e[1]]

    def rot_N(self):
        e = self.pos
        self.pos = [e[1], e[5], e[2], e[3], e[0], e[4]]
        
    def rot_CW(self):
        e = self.pos
        self.pos = [e[0], e[2], e[4], e[1], e[3], e[5]]

    def rot_CCW(self):
        e = self.pos
        self.pos = [e[0], e[3], e[1], e[4], e[2], e[5]]

        
    def top(self):
        return self.pos[0]

    def face(self):
        return self.pos[1]

    def right(self, tf=None):
        # tf = (t,f) : 上面 / 正面のラベル

        if tf == None:
            print(self.pos[2])
            return

        t = self.pos.index(tf[0])  # 上面（の扱いになっている）のラベルを取得
        f = self.pos.index(tf[1])  # 前面（の扱いになっている）のラベルを取得
        
        # u,f,r
        dr = [(1,2,4,3),(0,3,5,2),(0,1,5,4),(0,4,5,1),(0,2,5,3),(1,3,4,2)]
        r = (dr[t].index(f) + 1) % 4
        print(self.pos[dr[t][r]])
        return

    def left(self):
        print(self.pos[3])
        return

    def back(self):
        print(self.pos[4])
        return

    def bottom(self):
        print(self.pos[5])
        return

    def fit_top(x):
        if x == 0:
            d2.rot_S()
            d2.rot_S()
        if x == 1:
            d2.rot_N()
        if x == 3:
            d2.rot_axis()
            d2.rot_axis()
        if x == 4:
            d2.rot_S()
        if x == 5:
            d2.rot_axis()
            d2.rot_axis()
            d2.rot_axis()

    
    def position(self, x):
        return self.pos.index(x)
    
# 各方向を総当りでチェックする

d1 = Dice([int(x) for x in input().split()])
d2 = Dice([int(x) for x in input().split()])

check_f = False
# 上面からスタート

for _ in range(4):
    d2.rot_CW()
    if d1.pos == d2.pos:
        check_f = True

d2.rot_N()
for _ in range(4):
    d2.rot_CW()
    if d1.pos == d2.pos:
        check_f = True
d2.rot_S()

d2.rot_W()
for _ in range(4):
    d2.rot_CW()
    if d1.pos == d2.pos:
        check_f = True
d2.rot_E()

d2.rot_S()
for _ in range(4):
    d2.rot_CW()
    if d1.pos == d2.pos:
        check_f = True
d2.rot_N()

d2.rot_E()
for _ in range(4):
    d2.rot_CW()
    if d1.pos == d2.pos:
        check_f = True
d2.rot_W()

d2.rot_E()
d2.rot_E()
for _ in range(4):
    d2.rot_CW()
    if d1.pos == d2.pos:
        check_f = True
d2.rot_W()
d2.rot_W()

if check_f:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 5672
#include <bits/stdc++.h>
#ifdef __DEBUG__
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
#else
    #define DBG(X)
    #define SAY(X)
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dx[]={1, 0, -1, 0, 1,-1, 1,-1};
int dy[]={0, 1, 0, -1, 1, 1,-1,-1};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);

inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const map<T, S> p) { for (auto el : p) cout << "[" << el.first << ";" << el.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const deque<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const set<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

int H,W;
vector<string> A;
void input(){
    fast_io();
    cin >> H >> W;
    for (int i = 0; i < H; i++)
    {
        string s; cin >> s;
        A.push_back(s);
    }
}

vector<vector<bool>> visited;
void dfs(int i, int j){
    visited[i][j] = true;
    int cnt = 0;
    for (int k = 0; k < 2; k++)
    {
        int x = i+dx[k];
        int y = j+dy[k];
        if(x<0 || x>=H) continue;
        if(y<0 || y>=W) continue;
        if(A[x][y]=='#') cnt++;
    }
    if(cnt!=1) return;

    for (int k = 0; k < 2; k++)
    {
        int x = i+dx[k];
        int y = j+dy[k];
        if(x<0 || x>=H) continue;
        if(y<0 || y>=W) continue;
        if(A[x][y]=='#') dfs(x,y);
    }
}

bool solve(){
    visited.assign(H,vector<bool>(W,false));
    dfs(0,0);
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            if(A[i][j]=='#' && !visited[i][j]) return false;
            if(A[i][j]!='#' && visited[i][j]) return false;
        }
    }    
    return visited[H-1][W-1];
}

bool WAsolve(){
    for (int i = 0; i < H-1; i++)
    {
        for (int j = 0; j < W-1; j++)
        {
            if(A[i][j]=='#'){
                if(A[i+1][j]=='#' && A[i][j+1]=='#') return false;
                else if(A[i+1][j]=='.' && A[i][j+1]=='.') return false;
            }
        }
        
    }
    return true;
}   

int main()
{
    input();
    cout << (solve()?"Possible":"Impossible") << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define getMat(x, n, m, val) vector<vector<ll>> x(n, vector<ll> (m, val))
#define setp fixed<<setprecision
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll M=1000000000+7;
 
ll power(ll x,ll n)
{
    ll result=1;
    while(n>0)
    {
        if(n % 2 ==1)
            result=(result * x)%M;
        x=(x*x)%M;
        n=n/2;
    }
    return result;
}

int main(){
    ll t=1;
    // cin>>t;
    while(t--){
        char c;
        cin>>c;
        if(c>='A' && c<='Z')cout<<'A';
        else cout<<'a';
        cout<<endl;
    }
    return 0;
}

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

int main(){
    int h; cin >> h;
    
    // heapは1オリジンとする
    vector<int> heap(h+1); 

    //ヒープの読み込み
    for(int i = 1; i < h+1; i++){
        cin >> heap.at(i);
    }

    for(int i = 1; i < h + 1; i++){
        cout << "node " << i << ": key = " << heap.at(i);

        if(i != 1){  // parentの存在判定
            cout << ", parent key = " << heap.at(i / 2);
        }
        if(2*i < h+1){
            cout << ", left key = " << heap.at(2 * i);
        }
        if(2 * i + 1 < h+1){
            cout << ", right key = " << heap.at(2 * i + 1);
        }

        cout << ", " <<  endl;
    }
}


Measured memory_bytes: 3104
n = int(input())

vec_x = (int(x) for x in input().split())
vec_y = (int(x) for x in input().split())

# calc each abs
abs_vec = [abs(int(x) - int(y)) for x, y in zip(vec_x, vec_y)]

for p in range(1, 4):
    print(sum(x ** p for x in abs_vec) ** float(1 / p))

print(max(abs_vec))

Measured memory_bytes: 7788
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]
    MOD = 10**9+7
    from math import factorial
    N = II()
    X = LMIIS()
    # f = factorial(N-1)
    # def calc(k,slimes):
    #     # print(slimes)
    #     if k == N-1:
    #         return 0
    #     r = 0
    #     # for i in range(N-k-1):
    #     #     slimes2 = slimes[:]
    #     #     r = (slimes2[i+1]-slimes2[i]) / float(N-k-1)
    #     #     slimes2.pop(i)
    #     #     r += calc(k+1,slimes2) % MOD
    #     i = N-k-2
    #     slimes2 = slimes[:]
    #     print(i,slimes2)
    #     r = (slimes2[i+1]-slimes2[i]) * f / (N-k-1) % MOD
    #     slimes2.pop(i)
    #     r += calc(k+1,slimes2) 
    #     return r % MOD
    f = factorial(N-1) % MOD
    def calc(k,slimes):
        r = 0

        for k in range(N-1):
            r += (slimes[-1]-slimes[-2-k]) * f * pow((N-k-1),MOD-2,MOD)
            r %= MOD
        return r
    print(calc(0,X))




if __name__ == '__main__':
    main()

Measured memory_bytes: 15020
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int MaxN = 1e5;
int N, a[MaxN + 5];
bool cmp (int x,int y)
{
	return x > y;
}
int main()
{	int s,h;
	scanf("%d",&N);
	for(int i = 0;i <= sqrt(N);i++)
	{	s = i * i;
		if(s <= N)
		{
			a[++h] = s;
		}
	}
	sort(a+1,a+1+MaxN,cmp);
	printf("%d",a[1]);
}

Measured memory_bytes: 512
calc :: [Int]->Int
calc [n,x] = length [1|a<-[1..n],b<-[a+1..(min n $ x-a-1)],c<-[b+1..(min n $ x-a-b)],a+b+c==x]

main = getContents >>= mapM_ print.map calc.takeWhile (/= [0,0]).map (map (read :: String->Int).words).lines

Measured memory_bytes: 4144
fun main(args: Array<String>) {
    val a = readLine()!!.split(" ").map { it.toInt() }
    val n = a[0]
    val x = a[1]
    val y = a[2]

    for (k in 1..n - 1) {//ｋは最短距離
        var ans = 0
        for (i in 1..n - k) {//iは一つ決める点
            var simple = 1//最初にcount++してたヤーツ
            var big = 0//目的地bigのほうのヤーツ
            var small = 0

            // yからうごける回数
            val nokori = k - Math.abs(x - i) - 1

            if (nokori > 0) {

                val j_simple = i + k
                val j_big = y + nokori
                val j_small = y - nokori

                if (j_big <= n) {
                    if (j_simple <= y) {
                        big = 1
                        if (j_simple < j_small) {
                            small = 1
                        } else if (j_simple > j_small) {
                            simple = 0
                        }
                    } else if (j_simple < j_big) {
                            simple = 0
                            big = 1
                    }
                } else {
                    if (j_simple <= y){
                        if (j_simple < j_small) {
                            small = 1
                        } else if (j_simple > j_small) {
                            simple = 0
                        }
                    } else {
                        simple = 0
                    }
                }
            } else if (nokori == 0){
                if (i < (x + y) / 2){
                    big = 1
                }
            }
            ans += simple + big + small

        }
        println(ans)
    }
}

Measured memory_bytes: 37992
def warshal_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
  return d

n, m = map(int, input().split())
INF = 10**18
d = [[INF for i in range(n)] for j in range(n)]
e = [[0, 0, 0] for _ in range(m)]
for i in range(m):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    d[a][b] = c
    d[b][a] = c

    e[i][0] = a
    e[i][1] = b
    e[i][2] = c

for i in range(n):
    d[i][i] = 0

d = warshal_floyd(d)
ans = 0
for i in range(m):
    a = e[i][0]
    b = e[i][1]
    c = e[i][2]
    for k in range(n):
        if d[a][k] == c + d[b][k]:
            break
    else:
        ans += 1
print(ans)


Measured memory_bytes: 40944
if __name__ == '__main__':
    n = int(input())
    S = list(map(int, input().split()))
    q = int(input())
    T = list(map(int, input().split()))

    count = 0

    for x in T:
        left = 0
        right = len(S)
        while left < right:
            mid = (left + right) // 2
            if x == S[mid]:
                count += 1
                break
            elif x < S[mid]:
                right = mid
            else:
                left = mid + 1

    print(count)



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



int main(){
    int S;
    int tmp=0;
    cin >> S;
    if(S/100 > 0 && S/100 < 13){
        tmp+=1;
    }

    if(S%100 > 0 && S%100 < 13){
        tmp+=2;
    }

    switch (tmp){
    case 0:cout << "NA" << endl;
            break;
    case 1:cout << "MMYY" << endl;
            break;
    case 2:cout << "YYMM" << endl;
            break;
    case 3:cout << "AMBIGUOUS" << endl;
            break;
    default:break;

    }
}





Measured memory_bytes: 256
#include "iostream"

using namespace std;

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

	long long ans = 0;
    bool f;
	while(true){
        f = false;
        for(int i = 0; i < N; i++){
            if(h[i] > 0){
                f = true;
            }
        }
        if(f == false){
            break;
        }

        int i = 0;
		while(i < N){
			if(h[i] == 0){
				i++;
			}else{
				ans++;
                while(i < N && h[i] > 0){
                    h[i]--;
                    i++;
                }
			}
		}
	}

	cout << ans << endl;


    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int l,r,d;
  cin>>l>>r>>d;
  int ans=0;
  for(int i=l; i<=r; i++){
    if(i%d==0)ans++;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3584
#include <stdio.h>

int main(void)
{
	int i,n;
	int no[40];
	for(i=0;i<30;i++){
		no[i]=0;
	}
	for(i=0;i<28;i++){
		scanf("%d",&n);
		no[n-1]++;
	}
	for(i=0;i<30;i++){
		if(no[i]==0){
			printf("%d\n",i+1);
		}
	}
	return 0;
}

Measured memory_bytes: 1848
#include <cstdio>
#include <algorithm>

using namespace std;

const int MOD = 1000000007;

int main() {
    int n;

    int hw[100000];
    int he[100000];

    scanf("%d",&n);

    long long sum=1;

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

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

    for(int i=0;i<n;i++) {
        if((i==0||hw[i]!=hw[i-1])&&(i==n-1||he[i]!=he[i+1])&&(hw[i]!=he[i])) sum*=0;
        if((i==0||hw[i]!=hw[i-1])&&(hw[i]>he[i])) sum*=0;
        if((i==n-1||he[i]!=he[i+1])&&(he[i]>hw[i])) sum*=0;
        if(i==0||hw[i]!=hw[i-1]) sum*=1;
        else if(i==n-1||he[i]!=he[i+1]) sum*=1;
        else sum*=min(hw[i],he[i]);
        sum%=MOD;
    }

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

    return 0;
}

Measured memory_bytes: 896
#include<iostream>
using namespace std;
#define rep(i, n) for ( int i = 0; i < n; i++)

main(){
    char P[8][8], T[8][8];
    rep(i, 8) rep(j, 8) cin >> P[i][j];
    for ( int d = 90; d < 360; d += 90 ){
	cout << d << endl;
	rep(i, 8) rep(j, 8) T[i][j] = P[i][j];
	rep(i, 8) rep(j, 8) P[j][8-i-1] = T[i][j];
	rep(i, 8){
	    rep(j, 8) cout << P[i][j];
	    cout << endl;
	} 
    }
}

Measured memory_bytes: 0
#include <stdio.h>
int main(){
	int h1,m1,h2,m2,k,a,b,ans;
	scanf("%d%d%d%d%d",&h1,&m1,&h2,&m2,&k);
	a=h1*60+m1,b=h2*60+m2;
	ans=b-a-k;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1732
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



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

    int N,M;
    cin>>N>>M;
    int A[N];
    priority_queue<int> q;
    rep(i,N) {
        cin>>A[i];
        q.push(-A[i]);
    }
    vector<pair<int,int>> p(M);
    rep(i,M){
        int a,b;
        cin>>a>>b;
        p[i]=(make_pair(-b,a));
    }
    sort(p.begin(),p.end());
    int ans=0;
    rep(i,M){
        if(p[i].first<q.top()){
            rep(j,p[i].second){
                q.push(p[i].first);
                q.pop();
            }
        }else break;
    }
    rep(i,N){
        int x=q.top();
        q.pop();
        ans-=x;
    }
    cout << ans << endl;
    



}


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

int main() {
  string s;cin>>s;
  int n=s.size();
  ll ans=0;
  rep(bit,1<<(n-1)){
    ll a=s[0]-'0';
    rep(i,n-1){
      if(bit&(1<<i)){
      ans+=a;
      a=0;
    }
    a=a*10+s[i+1]-'0';
    }
    ans+=a;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3580
#include <stdio.h>
#include <math.h> //円周率M_PIを取得

int main(void){
	int R; //半径R用の変数
	scanf("%d", &R); //入力Rの取得
	printf("%f\n", R*2*M_PI); //R*2*piをfloatで出力

}

Measured memory_bytes: 1744
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<list>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>

using namespace std;

#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef pair<ll, ll> pll;

ll n = 0, m = 0, k = 0, ans = 0, sum = 0, cnt = 0, temp = 0;
string s;
bool flag;

//----------------------------------------------------------------------

#define MAX 1000

#define INF 1<<30
#define NOT 0
#define VIS 1
#define COMP 2

ll stt[MAX];
ll w[MAX][MAX];
ll mini[MAX];

void dijkstra(ll st) {
  FOR(i, 0, n) {
	stt[i] = NOT;
	mini[i] = INF;
  }
  mini[st] = 0;

  while (1) {
	m = INF;
	FOR(i, 0, n) {
	  if (stt[i] != COMP && mini[i] < m) {
		m = mini[i];
		temp = i;
	  }
	}

	if (m == INF) {
	  break;
	}

	stt[temp] = COMP;

	FOR(i, 0, n) {
	  if (stt[i] != COMP && w[temp][i] != INF) {
		if (w[temp][i] + mini[temp] < mini[i]) {
		  mini[i] = w[temp][i] + mini[temp];
		  stt[i] = VIS;
		}
	  }
	}
  }

}

int main(void) {
  ll x, y, a[20];
  cin >> x >> y;
  n = 10;

  FOR(i, 0, 10) {
	FOR(j, 0, 10) {
	  cin >> temp;
	  w[i][j] = temp;
	}
  }

  FOR(i, 0, 10) {
	dijkstra(i);
	a[i] = mini[1];
  }

  FOR(i, 0, x) {
	FOR(j, 0, y) {
	  cin >> temp;
	  if (temp == -1)continue;
	  if (temp == 1)continue;
	  ans += a[temp];
	}
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef  long long int ll;
typedef  long double ld;
#define sync ios_base::sync_with_stdio(false); cin.tie(NULL) 
#define input(arr,n) for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
#define mod 1000000007
#define F first
#define S second 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
//recursions\
#pragma comment(linker, "/stack:200000000")
//loops\
#pragma GCC optimize("unroll-loops")
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>//s.order_of_key(val) *s.find_by_order(ind)
using namespace std;

const int N = 1e6 + 5;

ll modexp(ll a, ll b)
{
	a %= mod; // a should not be divisible by mod 
	if(a <= 1)
		return a;
	if(b == 0)
		return 1;
	if(b % 2 == 0)
	{
		ll res = modexp(a, b / 2);
		return (res * res) % mod;
	}
	return (a * modexp(a, b - 1)) % mod;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// factorial
//problem if N is big so declare globally

ll fact[N], invf[N];
void factinv()
{
	fact[0] = invf[0] = 1;
	for(ll i = 1; i < N; i++)
		fact[i] = (i * fact[i - 1]) % mod;
	invf[N-1] = modexp(fact[N - 1], mod - 2);
	for(ll i = N - 2; i > 0; i--)
		invf[i] = (invf[i + 1] * (i + 1)) % mod;
}

ll ncr(ll n, ll r)
{
	if(n < r)
		return 0;
	ll ans = fact[n] * invf[n - r] % mod;
	ans =  ans * invf[r] % mod;
	return ans;
}
	

int main()
{
	sync;
	factinv();
	ll s, ans = 0;
	cin >> s;
	for(ll i = 1; s - 3 * i >= 0; i++)
		ans = (ans + ncr(s - 2 * i - 1, i - 1)) % mod;
	cout << ans;
}

Measured memory_bytes: 19248
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define OK puts("OK");
#define sz(s) (int)s.size()
#define pii pair<int,int>
#define all(s) s.begin(), s.end()
#define allr(s) s.rbegin(), s.rend()
#define rep(i,n) for (i=0;i<(n);++i)
#define rep1(i,n) for (i=1;i<=(n);++i)
#define ret return
#define int long long
#define scan1(a) scanf("%lld",&(a));
#define scan2(a,b) scanf("%lld %lld",&(a),&(b));
#define scan3(a,b,c) scanf("%lld %lld %lld",&(a),&(b),&(c));
#define nemeshay ios::sync_with_stdio(0),cin.tie(0);
const int INF=1e9+7,N=2e5+12;
int dp[N],q[N];
main(){
    int n,i,j,k;
    scan2(n,k)

    rep1(i,n){
        scan1(q[i])
        dp[i]=INF;
    }
    dp[0]=0;
    dp[1]=0;
    for (i=2;i<=n;++i){
        for (j=i-1;j>=max(1ll,i-k);--j){
            dp[i] = min(dp[i],dp[j] + abs(q[i]-q[j]));
        }
    }
    cout <<dp[n];
}









Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;

int h, m, s, t;

int main(){
	while (cin >> h >> m >> s){
		if (h == -1 && m == -1 && s == -1)break;
		int sum = 3600 * h + 60 * m + s,
			t1 = 7200 - sum,
			t2 = t1 * 3;
		printf("%02d:%02d:%02d\n", t1 / 3600, t1 % 3600 / 60, t1 % 60);
		printf("%02d:%02d:%02d\n", t2 / 3600, t2 % 3600 / 60, t2 % 60);

	}
}

Measured memory_bytes: 1160
#include <stdio.h>
int main()
{
    int n;  scanf("%d", &n);
    int arr[55];
    for(int i=1; i<=n; i++)
        scanf("%d", &arr[i]);
    int count = 0;
    for(int i=1; i<=n; i++)
    {
        if(arr[i]!=i)
            count++;
    }
    if(count<=2)
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  int N,K;
  cin >> N >> K;
  vp ab(N);
  rep(i,N) {
    cin >> ab[i].first >> ab[i].second;
  }
  int b = 0;
  int tmp = K;
  while(tmp>0) {
    tmp = tmp>>1;
    b++;
  }
  ll ans = 0;
  srep(d,-1,b) {
    int tar = 0;
    rep(i,d) {
      tar += (1<<i);
    }
    srep(i,d+1,b) {
      if((K>>i)&1) {
        tar += (1<<i);
      }
    }
    if(tar>K) continue;
    ll cnt = 0;
    rep(i,N) {
      if((ab[i].first|tar)==tar) {
        cnt += ab[i].second;
      }
    }
    ans = max(ans,cnt);
  }
  cout << ans << endl;
  return 0;
}

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

int main() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;

    int cnt = 0;
    while (b <= a) b *= 2, cnt++;
    while (c <= b) c *= 2, cnt++;

    if (cnt <= k)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3612
import Control.Applicative ((<$>), (<*>))
import Control.Monad
import Data.List

main :: IO ()
main = do
  xs <- getc $ split toInt
  mapM_ (putStrLn . unwords. map show) $ solve xs

solve :: [[Int]] -> [[Int]]
solve = map flyngjenny

flyngjenny :: [Int] -> [Int]
flyngjenny xs = head . sort . map snd $ takeWhile (\t -> fst t == (fst . head) zs) zs
  where
    zs = sort $ map f cs
    f ys = ((sum $ zipWith (\a b -> if a - b < 0 then 0 else a - b) xs ys), ys)

cs = [[1,4,1,4,1,2,1,2],[4,1,4,1,2,1,2,1],[1,4,1,2,1,2,1,4],[4,1,2,1,2,1,4,1],
     [1,2,1,2,1,4,1,4],[2,1,2,1,4,1,4,1],[1,2,1,4,1,4,1,2],[2,1,4,1,4,1,2,1]]

toInt :: String -> Int
toInt s = read s

split :: (String -> a) -> String -> [a]
split f = map f . words

getc :: (String -> a) -> IO [a]
getc f = map f . lines <$> getContents

Measured memory_bytes: 4192
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
int main() {
 ll n,h;
 cin >> n >> h;
 vector<ll>a(n),b(n);
 for(ll i=0;i<n;i++){
  cin >> a[i] >> b[i];
 }
 sort(a.begin(),a.end());
 sort(b.begin(),b.end());
 ll cnt=0;
 ll sum=0;
 for(ll i=n-1;i>=0;i--){
  if(a[n-1]>b[i]) break;
  sum+=b[i];
  cnt++;
  if(sum>=h) break;
 }
 h-=sum;
 if(h<=0){
  cout << cnt << endl;
  return 0;
 }
 if(h%a[n-1]!=0){
  cnt++;
 }
 cnt+=h/a[n-1];
 cout << cnt << endl;
}

Measured memory_bytes: 4860
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;

#define REP(i, n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i, n) for(ll i=(ll)(n-1);i>=0;i--)
#define FOR(i, a, b) for(ll i=(ll)(a); i<=(ll)(b); i++)
#define RFOR(i, a, b) for(ll i=(ll)(a);i>=(ll)(b); i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

ll dp[111111];

signed main()
{
	int N;
	cin >> N;
	vector<ll> h(N);
	REP(i, N){
		cin >> h[i];
	}
	dp[0] = 0;
	dp[1] = abs(h[1]-h[0]);
	FOR(i, 2, N-1){
		dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
	}
	cout << dp[N-1] << endl;
}


Measured memory_bytes: 4844
#include <iostream>
#include <vector>
#include <numeric>

#define MP 1000

using namespace std;

vector<int> p;
void set_prime()
{
    vector<bool> bp(MP + 1, true);
    for (int i = 2; i <= MP; i++)
    {
        if (bp[i])
        {
            p.emplace_back(i);
            for (int j = i + i; j <= MP; j += i)
            {
                bp[j] = false;
            }
        }
    }
}

int main()
{
    // set_prime();

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

    // check pairwise coprime
    bool is_pairwise = true;
    vector<bool> pused(1e6 + 1, false);
    for (int i = 0; i < n; i++)
    {
        if (!is_pairwise)
            break;
        if (a[i] == 1)
            continue;
        if (pused[a[i]])
        {
            is_pairwise = false;
        }
        else
        {
            pused[a[i]] = true;
        }
        for (int j = 2; j * j <= a[i]; j++)
        {
            if (a[i] % j == 0)
            {
                if (pused[j])
                {
                    is_pairwise = false;
                    break;
                }
                else
                {
                    pused[j] = true;
                }

                if (a[i] / j != 1 && j * j != a[i])
                {
                    if (pused[a[i] / j])
                    {
                        is_pairwise = false;
                        break;
                    }
                    else
                    {
                        pused[a[i] / j] = true;
                    }
                }
            }

            // if (a[i] % p[j] == 0)
            // {
            //     if (pused[j] == true)
            //     {
            //         is_pairwise = false;
            //         break;
            //     }
            //     else
            //     {
            //         pused[j] = true;
            //     }
            // }
        }
    }

    if (is_pairwise)
    {
        cout << "pairwise coprime" << endl;
        return 0;
    }

    bool is_setwise = false;
    int gcd_all = a[0];
    for (int i = 1; i < n; i++)
    {
        gcd_all = gcd(gcd_all, a[i]);
    }
    if (gcd_all == 1)
        is_setwise = true;

    if (is_setwise)
    {
        cout << "setwise coprime" << endl;
        return 0;
    }

    cout << "not coprime" << endl;
    return 0;
}

Measured memory_bytes: 7152
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long LL;
typedef long double ld;
typedef vector<ll>VI;
typedef pair<ll,ll>P;
#define VV(T) vector<vector<T>>
#define sz(x) int(x.size())
#define PI 3.1415926535897932384626433832795
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define reprev(i,n) for (ll i=(ll)n-1;i>=0;i--)
#define ALL(a)  (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define c_max(a, b) (((ll)a)>((ll)b)?(a):(b))
#define c_min(a,b) (((ll)a)<((ll)b)?(a):(b))
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 vmax(v) *max_element(ALL(v))
#define vmin(v) *min_element(ALL(v))
#define $(x) {cout<<#x<<" = " <<(x)<<endl;}
#define fi first
#define se second
#define MAX 100100//5
#define MAX2 200100
#define MAX6 1001001//6
#define MAX7 10010010//7
#define SENTINEL 2000000000//9
#define INF 1<<30
#define INFTY 1LL<<61
#define MAX_INT INT_MAX
#define Endl '\n'
#define CLR(mat) memset(mat, 0, sizeof(mat))
inline ll GCD(ll a,ll b){return b?GCD(b,a%b):a;}//最大公約数
inline ll lcm(ll a,ll b){return a*b/GCD(a,b);}//最小公倍数
template<class T> bool contain(const std::string& s, const T& v) {
   return s.find(v) != std::string::npos;
}
const int MOD = 1000000007;
//const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
// vector型から重複を削除 list.erase(unique(ALL(list)),list.end());
// g++ -o a a.cpp -Wall -lm -std=c++17
//push_back -> emplace_back
int main(){
   ll a,b,c,d;cin>>a>>b>>c>>d;
   cout<<max(a*c,max(b*d,max(a*d,b*c)))<<endl;
}

Measured memory_bytes: 3672
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define fi first
#define se second
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define rep11(i, n) for (int i = 1; i < (int)(n); ++i)
#define repo(i, o, n) for (int i = o; i < (int)(n); ++i)
#define repm(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1002000007
#define INF LONG_LONG_MAX

typedef pair<int, int> P;
int main(){
    long long n,m;
    cin>>n>>m;
    vector<long long> ans;
    vector<int>oks(n+1,true);
    rep(i,m){
        int a;
        cin>>a;
        oks[a]=false;
    }
    ans.push_back(1);
    if(oks[1]){
        ans.push_back(1);
    }
    else{
        ans.push_back(0);
    }
    long long p=0;
    for(int i=2; i<=n; i++){
        if(oks[i]){
            long long c1=ans[i-1];
            long long c2=ans[i-2];
            long long c=(c1+c2)%1000000007;
            ans.push_back(c);
            }
        else{
            ans.push_back(0);
        }
    }
    cout<<ans[ans.size()-1]<<endl;
}


Measured memory_bytes: 1784
#include <iostream>

using namespace std;

int main(){
	
	cin.tie(0); ios_base::sync_with_stdio(0);
	int k,n;
	cin>>k>>n;
	int a[n];
	int ma = 0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(i&&a[i]-a[i-1]>ma)ma = a[i]-a[i-1];
	}
	if(a[0]+k-a[n-1]>ma)ma = a[0]+k-a[n-1];
	cout<<k-ma<<endl;
	
	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define rep2(i,j,n) for(int j=i;j<n;j++)
#define rep3(i,j,n) for(int j=i;j<=n;j++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define sp(n) cout << fixed << setprecision(n)
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; }
typedef long long ll;
using namespace std;
int main(void){
    int a,b;cin>>a>>b;
    int res=(a+b+1)/2;
    cout<<res<<endl;
}

Measured memory_bytes: 256
// 基本テンプレート
 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
 
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

// Union-Find 木 (Verified: AtCoder Typical Contest 001 B)
struct UnionFind {
private:
    const int n;
    int __size;
    vector<int> uf;
public:
    // 初期化 UnionFind uni(n) のように宣言すれば良い
    UnionFind(int _n) : n(_n), __size(_n), uf(_n, -1) {}
    // find (木の根を求める)
    int find(int x) {return (uf[x] < 0) ? x : uf[x] = find(uf[x]);}
    // x と y が同じ集合に属するかどうか
    bool same(int x, int y) {return find(x) == find(y);}
    // x が属する集合の要素数
    int size(int x) {return -uf[find(x)];}
    // 集合はいくつあるか
    int size()      {return __size;}
    // x と y の属する集合を併合
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if(x == y) return;
        __size--;
        if(uf[y] < uf[x]) swap(x, y);
        uf[x] += uf[y]; uf[y] = x;
    }
};

vector<int> es[100010];
int A[100010];
signed main() {
    int N, M; cin >> N >> M;
    UnionFind uf(N);
    rep(i,0,N) cin >> A[i];
    rep(i,0,M) {
        int a, b; cin >> a >> b;
        uf.unite(a, b);
    }
    
    rep(i,0,N) {
        int f = uf.find(i);
        es[f].push_back(A[i]);
    }

    if(uf.size() == 1) {
        cout << 0 << endl;
        return 0;
    }

    int lim = ((int)uf.size() - 1);
    int ans = 0, rest = (int)uf.size() - 2;
    rep(i,0,100010) {
        sort(es[i].begin(), es[i].end());
        if(es[i].size()) {
            // printf("i = %lld, size = %zu\n", i, es[i].size());
            ans += es[i][0];
        }
    }

    priority_queue< pii, vector<pii>, greater<pii> > que;
    vector<int> ptr(N, 1);
    rep(i,0,100010) if(es[i].size() > 0 && ptr[i] < es[i].size() && ptr[i] < lim) que.push(make_pair(es[i][ptr[i]], i));

    while(rest > 0) {
        // printf("size = %zu\n", que.size());
        if(que.size() < 1) {
            cout << "Impossible" << endl;
            return 0;
        }
        rest--;
        pii cur1 = que.top(); que.pop();
        // printf("add: %lld\n", cur1.first + cur2.first);
        ans += cur1.first;
        int i1 = cur1.second;
        ptr[i1]++;
        if(ptr[i1] < es[i1].size() && ptr[i1] < lim) que.push(make_pair(es[i1][ptr[i1]], i1));
    }

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

Measured memory_bytes: 8064
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class data
{
	int floor;
	int number;
	int times;
	data(){return;}
	data(int floor,int number,int times)
	{
		this.floor=floor;
		this.number=number;
		this.times=times;
	}
}

public class Main {

	/**
	 * @param args
	 */
	/**
	 * @param building
	 * @param n
	 * @return
	 */
	int solve(int[][] building,int n)
	{
		Queue<data> que=new LinkedList<data>();
		que.add(new data(0,0,0));
		que.add(new data(0,1,0));
		
		Boolean[][] visited=new Boolean[n+2][2];
		for(int i=0;i<n+2;++i){for(int j=0;j<2;++j){visited[i][j]=false;}}
		
		while(!que.isEmpty())
		{
			data present=que.poll();
			
			if(visited[present.floor][present.number])continue;
			visited[present.floor][present.number]=true;

			int floor=present.floor;
			int num=present.number==1?0:1;
			switch(building[present.floor][present.number])
			{
			case 1:
				int i;
				for(i=present.floor;i<n&&building[i][present.number]==1;++i);
				--i;
				floor=i;
				break;
			case 2:
				for(i=present.floor;i>=0&&building[i][present.number]==2;--i);
				floor=i;
				break;
			}
			if(floor>=n-1)return  present.times;
			for(int i=0;i<3&&floor<n;++i)
			{
				que.add(new data(floor,num,present.times+1));
				++floor;
			}
		}
		return -1;
	}
	
	void io()
	{
		Scanner s=new Scanner(System.in);
		int n;
		int building[][];
		while((n=s.nextInt())>0)
		{
			building=new int[n][2];
			for(int i=0;i<n;++i)
			{
				building[i][0]=s.nextInt();
			}
			for(int i=0;i<n;++i)
			{
				building[i][1]=s.nextInt();
			}
			int ans=solve(building,n);
			if(ans==-1){System.out.println("NA");}
			else{System.out.println(ans);}
		}
		s.close();
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main().io();
	}

}

Measured memory_bytes: 12000
using System;

namespace atcoder191019
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int A = Int32.Parse(input[0]);
            int B = Int32.Parse(input[1]);
            int uncovered = A - 2 * B;
            if (uncovered < 0)
                Console.WriteLine(0);
            else
                Console.WriteLine(uncovered);

        }
    }
}


Measured memory_bytes: 11092
n = int(input())
a = list(map(int,input().split()))
dp = [0]*(n)
dp[0] = 1000

for i in range(1,n):
    tmp = dp[i-1]
    for j in range(i):
        k = dp[j]//a[j]
        m = dp[j]-a[j]*k
        tmp = max(tmp,m + a[i] * k)
    dp[i] = tmp

print(dp[n-1])

Measured memory_bytes: 64140
#include<bits/stdc++.h>
#define reg register
#define ll long long
#define inf 0x3f3f3f3f
#define iinf 0x3f3f3f3f3f3f3f3fll
using namespace std;
class edge
{
	public:
		ll to,next,v;
		inline bool operator<(const edge &b)const
		{
			return v>b.v;
		}
}w[1000005];
int n,num;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(reg int i=1;i<=n;i++)
	if(i&1)num++;
	cout<<(double)num/(double)n;
	return 0;
}

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



for i in range(n):
	v=a[i]
	j=i-1
	while j>=0 and a[j] > v:
		a[j+1]=a[j]
		j-=1
	a[j+1]=v
	print(' '.join(map(str,a)))




Measured memory_bytes: 5596
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>

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 FORR(i, m, n) for(int i = n;i >= m;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define ALL(n) n.begin(),n.end()
#define MP make_pair
ll dp[110][30];

int main() {
	ll N, s[110],ans;
	cin >> N;
	REP(i, N - 1) cin >> s[i];
	cin >> ans;
	dp[1][s[0]] = 1;
	REPO(i, N - 2) {
		REP(j, 21) {
			if (dp[i][j] > 0) {
				if (j + s[i] < 21) dp[i + 1][j + s[i]] += dp[i][j];
				if(j - s[i] >= 0)  dp[i + 1][j - s[i]] += dp[i][j];
			}
		}
	}
	cout << dp[N - 1][ans] << endl;
}



Measured memory_bytes: 3080
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 998244353
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n2 = [1 for _ in range(3010)]
for i in range(1, 3010):
    n2[i] = n2[i - 1] * 2 % mod

n, s = MAP()
a = LIST()
dp = [[0 for _ in range(s + 1)] for _ in range(n)]
if s >= a[0]:
    dp[0][a[0]] = 1
for i in range(1, n):
    for j in range(1, min(s + 1, a[i])):
        dp[i][j] = dp[i - 1][j] * 2
        dp[i][j] %= mod
    if a[i] <= s:
        dp[i][a[i]] = dp[i - 1][a[i]] * 2 + n2[i]
        dp[i][a[i]] %= mod
    for j in range(a[i] + 1, s + 1):
        dp[i][j] = dp[i - 1][j] * 2 + dp[i - 1][j - a[i]]
        dp[i][j] %= mod
print(dp[n - 1][s])


Measured memory_bytes: 149304
#include<bits/stdc++.h>
using namespace std;
const int N=1<<20,thr=20;
const long long mod=998244353,p=8293049;
long long dp[21][N],f[p];
string str[p];

long long dfs(string s)
{
	if(s.size()<=thr)
	{
		int sum=0;
		for(int i=0;i<s.size();i++)
		{
			sum=sum*2+s[i]-'0';
		}
		return dp[s.size()][sum];
	}
	int sum=0;
	for(int i=0;i<s.size();i++)
	{
		sum=(sum*2+s[i]-'0')%p;
	}
	for(;str[sum].size() && str[sum]!=s;sum=(sum+1)%p);
	if(str[sum].size())return f[sum];
	long long ans=0;
	ans=dp[1][s[0]-'0']*dfs(s.substr(1))%mod;
	for(int i=1;i*2<=s.size();i++)
	{
		string t=s.substr(0,i);
		for(int j=1;i*j+i<=s.size();j++)
		{
			for(int k=0;k<i;k++)if(s[j*i+k]=='0')
			{
				t[k]='0';
			}
			ans=(ans+dfs(t)*dfs(s.substr(i*j+i)))%mod;
		}
	}
	f[sum]=ans;
	str[sum]=s;
	return ans;
}

int main()
{
	dp[0][0]=dp[1][0]=1;
	dp[1][1]=2;
	for(int n=2;n<=thr;n++)
	{
		//printf("n=%d\n",n);
		for(int i=0;i<(1<<n);i++)
		{
			dp[n][i]=dp[1][i&1]*dp[n-1][i>>1];
			for(int j=1;j*2<=n;j++)
			{
				int t=i&((1<<j)-1);
				for(int k=1;j*k+j<=n;k++)
				{
					t=t&(i>>(j*k));
					(dp[n][i]+=dp[j][t]*dp[n-j*k-j][i>>(j*k+j)]);
				}
			}
			dp[n][i]%=mod;
		}
	}
	//cout<<dp[20][(1<<20)-1]<<endl;
	string s;
	cin>>s;
	printf("%lld\n",dfs(s));
	return 0;
}


Measured memory_bytes: 185856
#include<stdio.h>
int main()
{
  char ch;
  scanf ("%c", &ch);
    if(ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u' ||
       ch=='A' || ch=='E' || ch=='I' || ch=='O' || ch=='U')
    {
        printf("vowel", ch);
    }
    else {
        printf("consonant", ch);
    }

  return 0;
}

Measured memory_bytes: 2056
n, k = map(int,input().split())
a = list(map(int,input().split()))
l = [0]*n
i=0
cnt=0
while l[i]==0:
    l[i] = a[i]
    i = a[i]-1 
    cnt += 1
start = i+1
i = 0
pre = 0
while i+1!=start:
    i = a[i]-1
    pre += 1
loop = cnt-pre
if pre+loop<k:
    k=(k-pre)%loop+pre
i = 0
for _ in range(k):
    i = a[i]-1
print(i+1)

Measured memory_bytes: 32336
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a-1);i>=(b);i--)
#define all(x) (x).begin(), (x).end()
const int INF = 1e18;
const int MOD = 1e9+7;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef string str;
typedef vector<str> vstr;
void print() {cout<<endl;}template<class Head,class...Tail>void print(Head&&head,Tail&&...tail){cout<<head;if(sizeof...(tail)!=0)cout<<" ";print(forward<Tail>(tail)...);}template<class T>void print(vector<T>&vec){for(auto&a:vec){cout<<a;if(&a!=&vec.back())cout<<" ";}cout<<endl;}template<class T>void print(vector<vector<T>>&df){for(auto&vec:df){print(vec);}}
template<class T=int>T in() {T x;cin>>x;return(x);}
template<class T=int>vector<T> input_to_vector(int n) {vector<T>x;rep(i,n){T a;cin>>a;x.push_back(a);}return(x);}

signed main(){
    int t = in(), x = in();
    print((double)t / (double)x);
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(2000000)

n = int(input())
m = [list(map(int, input().split()))[2:] for _ in range(n)]

def dfs(x, time):
    first[x] = time
    time += 1
    for v in m[x]:
        if first[v-1] == 0:
            time = dfs(v-1, time)
    finish[x] = time
    time += 1
    return time

first = [0] * n
finish = [0] * n

time = 1
for i in range(n):
    if first[i] == 0:
        time = dfs(i, time)

for i, xy in enumerate(zip(first, finish)):
    print(i+1, *xy)


Measured memory_bytes: 5668
#include <bits/stdc++.h>
#define INF 2e9
#define MOD 1000000007
using namespace std;
typedef long long llong;
typedef long double ldouble;

using Graph = vector<vector<int>>;

// int ctoi(const char c){
//   if('0' <= c && c <= '9') return (c-'0');
//   return -1;
// }

// int gcd(int a, int b){
//   int ma = max(a,b);
//   int mi = min(a,b);
//   if(mi == 0) return ma;

//   return gcd(mi, ma%mi);
// }

int main(){
  int X, Y;
  cin >> X >> Y;
  cout << X + Y / 2 << endl;
  return 0;
}

Measured memory_bytes: 256
import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = iss()
    print(S.replace('2017', '2018', 1))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



int N,num_query;
vector<int> V;

int main(){

	scanf("%d",&N);

	int tmp;
	for(int i = 0; i < N; i++){

		scanf("%d",&tmp);
		V.push_back(tmp);
	}

	scanf("%d",&num_query);

	int b,e,t;

	for(int loop = 0; loop < num_query; loop++){

		scanf("%d %d %d",&b,&e,&t);

		swap_ranges(V.begin()+b,V.begin()+e,V.begin()+t);
	}

	printf("%d",V[0]);

	for(int i = 1; i < V.size(); i++){

		printf(" %d",V[i]);
	}
	printf("\n");

	return 0;
}




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

int main(){

  int A,B,K;
  int n;

  cin>>A>>B>>K;

  if(K>=B-A+1){
    K=B-A+1;
  }

  for(n=A;n<=A+K-1;n=n+1){
    cout<<n<<endl;
  }

  if(B-A+1>=2*K){

  for(n=B-K+1;n<=B;n=n+1){
    cout<<n<<endl;
  }

  }
  else{
    for(n=K+A;n<=B;n=n+1){
      cout<<n<<endl;
    }
  }

}

Measured memory_bytes: 256