akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#pragma GCC optimize "Ofast,omit-frame-pointer,inline"
using namespace std;
typedef long long ll;

#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VP vector<pair<int,int>>
#define VPP vector<pair<int,pair<int,int>>>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)
typedef pair <int, int> P;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
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; }

const int  INF = 1 << 29;
const ll INFL = 1LL << 60;
const ll mod = 998244353;



int main() {

	int n, k;
	cin >> n >> k;

	VI v(n);
	REP(i, n)cin >> v[i];

	REP(i, k) {
		VI cs(n + 1, 0);
		REP(i, n) {
			cs[max(0, i - v[i])]++;
			cs[min(n, i + v[i] + 1)]--;
		}
		VI s(n);
		bool flag = false;
		s[0] = cs[0];
		if (s[0] != n)flag = true;
		
		FOR(i, 1, n) {
			s[i] = s[i - 1] + cs[i];
			if (s[i] != n)flag = true;
		}
		if (!flag) {
			REP(i, n)cout << s[i] << ' ';
			return 0;
		}
		v = s;

	}

	REP(i, n)cout << v[i] << ' ';
}


Measured memory_bytes: 5624
//Badwaper gg
#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define mp make_pair
#define pb push_back
#define re register ll
#define fr first
#define sd second
#define FOR(i,a,b) for(re i=a;i<=b;i++)
#define REP(i,a,b) for(re i=a;i>=b;i--)
#define lowbit(x) (x&(-x))
#define Z(x) (x>=mod?x-mod:x)
#define N 105
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
int C[N][N],P[N][N];
int n,m,k,mod;
int f[2][N][N];
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(),m=read(),k=read(),mod=read();
	FOR(i,0,max(n,m)){C[i][0]=1;FOR(j,1,i)C[i][j]=Z(C[i-1][j-1]+C[i-1][j]);}
	FOR(i,0,k){P[i][0]=1;FOR(j,1,max(n,m))P[i][j]=1LL*P[i][j-1]*i%mod;}
	int cur=1;
	f[0][0][0]=1;
	FOR(t,1,k)
	{
		memset(f[cur],0,sizeof(f[cur]));
		FOR(i,0,n)FOR(j,0,m)if(f[cur^1][i][j])
		{
			int x=f[cur^1][i][j],y=1LL*P[k-t+1][j]*P[t][m-j]%mod;
			for(re a=0;i+a<=n;a++,x=1LL*x*y%mod)f[cur][i+a][j]=Z(f[cur][i+a][j]+1LL*C[n-i][a]*x%mod);
		}
		cur^=1;
		memset(f[cur],0,sizeof(f[cur]));
		FOR(i,0,n)FOR(j,0,m)if(f[cur^1][i][j])
		{
			int x=f[cur^1][i][j],y=1LL*P[k-t+1][i]*P[t][n-i]%mod;
			for(re b=0;j+b<=m;b++,x=1LL*x*y%mod)f[cur][i][j+b]=Z(f[cur][i][j+b]+1LL*C[m-j][b]*x%mod);
		}
		cur^=1;
		memset(f[cur],0,sizeof(f[cur]));
		FOR(i,0,n)FOR(j,0,m)if(f[cur^1][i][j])
		{
			int x=f[cur^1][i][j],y=1LL*(mod-P[k-t][j])*P[t][m-j]%mod;
			for(re c=0;i+c<=n;c++,x=1LL*x*y%mod)f[cur][i+c][j]=Z(f[cur][i+c][j]+1LL*C[n-i][c]*x%mod);
		}
		cur^=1;
		memset(f[cur],0,sizeof(f[cur]));
		FOR(i,0,n)FOR(j,0,m)if(f[cur^1][i][j])
		{
			int x=f[cur^1][i][j],y=1LL*(mod-P[k-t][i])*P[t][n-i]%mod;
			for(re d=0;j+d<=m;d++,x=1LL*x*y%mod)f[cur][i][j+d]=Z(f[cur][i][j+d]+1LL*C[m-j][d]*x%mod);
		}
		cur^=1;
	}
	printf("%d\n",f[cur^1][n][m]);
	return 0;
}


Measured memory_bytes: 3924
#include <iostream>
#include<algorithm>
using namespace std;
int main()
{
	unsigned long long a, b, c, d;
	cin >> a >> b >> c;
	if (a%c==0)
	{
		d = b / c - a / c + 1;
	}
	else
	{
		d = b / c - a / c;
	}
	cout << d << endl;
}


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

public class Main {
    
    public static void main(String[] args) {
	// write your code here
        Scanner sc= new Scanner(System.in);
      String s= sc.next();

      if(Character.isUpperCase(s.charAt(0))){
          System.out.println('A');
      }
      else
          System.out.println('a');

    }
}


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

using namespace std;
#define ll long long
const int N=2e5+5;
int a[N];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,ans=0;
    multiset<int>st;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=n-1;i>=0;i--)
    {
        auto it=st.upper_bound(a[i]);
        if(it==st.end())
            ans++;
        else st.erase(it);
        st.insert(a[i]);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 5376
for i in range(int(input())):
	a=b=c=0
	for j in map(int,input().split()):
		if j > b:
			b=j
		elif j > c: 
			c=j
		else: 
			a=1
	if a==0:
		print('YES')
	else:
		print('NO')


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

typedef long long int lli;
#define pb push_back
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen("aaa.in","r",stdin);freopen("aaa.out","w",stdout);

using namespace std;

const long long int N = (lli)(1e5 + 5);
const long long int llinf = (1e18 + 5);

lli n;

int main ()
{
	fast;
	//fast2;
	cin >> n;
	cout << (lli)(n * n) << "\n";
}


Measured memory_bytes: 256
from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Measured memory_bytes: 94448
import math
a,b,h,m = map(int,input().split())

long_bar = math.radians(((h*60+m)/720)*360)
short_bar = math.radians((m/60)*360)

shita = long_bar-short_bar

x = (a**2) + (b**2) - (2*a*b*math.cos(shita))
print(math.sqrt(x))

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

#define PI 3.14159265358979323846264338327950L
#define ll long long
#define lli long long int

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> first(n);
    vector<ll> second(m);
    ll total = 0;
    ll references = -1;
    bool found = true;
    for (int i = 0; i < n; i++) {
        ll temp;
        cin >> temp;
        total += temp;
        first[i] = total;
        if (total > k && found) {
            references = i - 1;
            found = false;
        }
    }
    total = 0;
    for (int i = 0; i < m; i++) {
        ll temp;
        cin >> temp;
        total += temp;
        second[i] = total;
    }
    ll answer = 0;
    if (references == -1 && found) {
        references = n - 1;
    }
    if (references == -1 && !found) {

        answer = upper_bound(second.begin(), second.end(), k) - second.begin();


    } else {
        ll temp;
        for (int i = references; i >= 0; i--) {
            temp = upper_bound(second.begin(), second.end(), k - first[i]) - second.begin() + i + 1;
            if (answer < temp) {
                answer = temp;
            }
        }
        temp = upper_bound(second.begin(), second.end(), k) - second.begin();
        if (answer < temp) {
                answer = temp;
            }
    }
    cout << answer << "\n";

    return 0;
}


Measured memory_bytes: 6348
def process(n, p):
    foo = 1
    k = 2
    while k * k <= p:
        c = 0
        while p % k == 0:
            p /= k
            c += 1
        if c >= n:
            foo *= k ** (c / n)
        k += 1
    if n == 1:
        foo *= p
    return foo

def main():
    n, p = [int(i) for i in raw_input().strip().split()]
    print process(n, p)

if __name__ == '__main__':
    main()

Measured memory_bytes: 28908
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

const int N = 250;

int m, n;
int val[N+2];
bool vis[N+2];
bool G[N+2][N+2];

void makeG(){
  fill(G[0], G[n+2], false);
  for(int i=0;i<n+2;i++){
    for(int j=1;j<=m;j++){
      int next = i + j;
      if(next > n + 1) next = n + 1;
      next += val[next];
      if(next > n + 1) next = n + 1;
      if(next < 0) next = 0;
      if(next == i) continue;
      G[i][next] = true;
    }
  }
  for(int k=0;k<n+2;k++){
    for(int i=0;i<n+2;i++){
      for(int j=0;j<n+2;j++){
        if(G[i][k] && G[k][j]) G[i][j] = true;
      }
    }
  }
}

bool solve(){
  makeG();
  bool f = false;
  for(int i=0;i<n+2;i++) if(G[0][i]) f = true;
  if(!f) return false;
  for(int i=1;i<n+1;i++){
    if(G[0][i] && !G[i][n+1]) return false;
  }
  return true;
}

main(){
  while(cin >> m && m){
    cin >> n;
    val[0] = val[n+1] = 0;
    for(int i=1;i<=n;i++) cin >> val[i];
    cout << (solve() ? "OK" : "NG") << endl;
  }
}

Measured memory_bytes: 1216
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/22
Solved on 2019/3/
@author: shinjisu
"""


# ABC 077 C Festival
import collections
#import numpy as np

def getInt(): return int(input())

def getIntList(): return [int(x) for x in input().split()]
# def getIntList(): return np.array(input().split(), dtype=np.longlong)

def zeros(n): return [0]*n
# def zeros(n): return np.zeros(n, dtype=np.longlong)

def getIntLines(n): return [int(input()) for i in range(n)]
"""
def getIntLines(n):
    data = zeros(n)
    for i in range(n):
        data[i] = getInt()
    return data
"""

def zeros2(n, m): return [zeros(m) for i in range(n)] # obsoleted zeros((n, m))で代替

def getIntMat(n, m):  # n行に渡って、1行にm個の整数
    #mat = zeros((n, m))
    mat = zeros2(n, m)
    for i in range(n):
        mat[i] = getIntList()
    return mat

ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**18

class Debug():
    def __init__(self):
        self.debug = True
 
    def off(self):
        self.debug = False
 
    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                print(cmt, ':  ', end='')
            print(x)
        return x


def prob():
    d = Debug()
    d.off()
    N = getInt()
    d.dmp((N), 'N')
    aParts = getIntList()
    bParts = getIntList()
    cParts = getIntList()
    aParts.sort()
    bParts.sort()
    cParts .sort()
    d.dmp((aParts), 'A')
    d.dmp((bParts), 'B')
    d.dmp((cParts), 'C')
    combAB = zeros(N)  # Aのi番めのパーツが組み合わせられる数
    combBC = zeros(N)
    j = 0
    for i in range(N):
        while j < N and bParts[j] <= aParts[i]:
            j += 1
            #d.dmp((i,j),'in while')
        combAB[i] = N-j
        #d.dmp((i,j),'in for')
    d.dmp((combAB), 'combAB')
    j = 0
    for i in range(N):
        while j < N and cParts[j] <= bParts[i]:
            j += 1
        combBC[i] = N-j
    d.dmp((combBC), 'combBC')
    sm = zeros(N+1)
    for i in range(N):
        sm[-2-i] = combBC[-1-i]+sm[-1-i]
    d.dmp((sm), 'sm')
    count = 0
    for i in range(N):
#        count += sum(combBC[N-combAB[i]:])
        count += sm[N-combAB[i]]
    return count


ans = prob()
if ans is None:
    pass
elif type(ans) == tuple and ans[0] == 1:  # 1,ans
    for elm in ans[1]:
        print(elm)
else:
    print(ans)


Measured memory_bytes: 28560
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <functional>
#include <complex>
#include <numeric>
using namespace std;

typedef long long LL; typedef pair<LL, LL> PLL; typedef vector<LL> VLL;
#define REP(i,n) for(int (i)=0; (i)<(n) ;++(i))
#define REPN(i,a,n) FOR((i),(a),(a)+(n))
#define FOR(i,a,b) for(int (i)=(a); (i)<(b) ;++(i))
#define PB push_back
#define MP make_pair
#define OUT(a) cout<<(a)<<endl;

vector<int> d;

bool chk(int a){
    while(a>0){
        int tmp=a%10;
        a/=10;
        if(find(d.begin(),d.end(),tmp)!=d.end()){
            return false;
        }
    }
    return true;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,k,ans;
    cin >> n >> k;
    REP(i,k){
        int t;
        cin >> t;
        d.push_back(t);
    }

    while(1){
        if(chk(n)==true){
            ans=n;
            break;
        }
        n++;
    }

    cout << ans <<endl;

    return 0;
}


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


int main() {
  string s, t;
  cin >> s >> t;
  int cnt = 0;
  rep(i, s.size()){
    if(s[i] != t[i]){
      cnt++;
    }
  }
  cout << cnt << endl;
}

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

M0, m0 = -float('inf'), float('inf')
M1, m1 = -float('inf'), float('inf')
for i in range(N):
    x, y = map(int, input().split())
    M0 = max(M0, x + y)
    m0 = min(m0, x + y)
    M1 = max(M1, x - y)
    m1 = min(m1, x - y)

print(max(M0 - m0, M1 - m1))


Measured memory_bytes: 9200
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
const double PI = acos(-1);
const double EPS = 1e-15;
long long INF=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;
bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}
 
class UnionFind {
    public:
    //各頂点の親の番号を格納する。その頂点自身が親だった場合は-(その集合のサイズ)を入れる。
    vector<int> Parent;
    
    //クラスを作るときは、Parentの値を全て-1にする。
    //以下のようにすると全てバラバラの頂点として解釈できる。
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }
    
    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
    
    //自分のいるグループの頂点数を調べる
    int size(int A) {
        return -Parent[root(A)];//先祖をrootで取っておきたい。
    }
    
    //AとBをくっ付ける
    bool connect(int A, int B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }
        
        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらAとBをひっくり返す。
        if (size(A) < size(B)) swap(A, B);
        
        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;
        
        return true;
    }
};

int main(){
  
  int consume[]={-1,2,5,5,4,5,6,3,7,6};
  int n,m;
  cin>>n>>m;
  vector<int> a(m);
  REP(i,m){
    cin>>a[i];
  }
  sort(a.begin(),a.end(),greater<int>());
  
  vector<int> dp(n+1,-1);//マッチをi本使って作れる最大の桁数を格納する。
  vector<int> to(n+1,-1);
  REP(i,m){
    if(consume[a[i]]>n)continue;
    if(dp[consume[a[i]]]>0)continue;
    dp[consume[a[i]]] = 1;
    to[consume[a[i]]] = i;
  }
  REP(i,n){
    REP(j,m){
      if(i+1-consume[a[j]]<0)continue;
      if(dp[i+1-consume[a[j]]]<0)continue;
      if(dp[i+1]<(dp[i+1-consume[a[j]]]+1)){
        dp[i+1] = dp[i+1-consume[a[j]]]+1;
        to[i+1] = j;
      }
    }
  }
  
  int matches = n;//残りのマッチの数
  
  string ans="";
  int index;
  char next_;
  while(to[matches]>=0){
    index = to[matches];
    next_ = '0' + a[index];
    ans += next_;
    matches -= consume[a[index]];
  }
    
  
  cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>

#define FOR(i, a, b) for (int i = a; i < b; i++)
#define FORN(i, a, b) for (int i = a; i <= b; i++)
#define P(s) cout << s << endl
#define PC(condition, _true, _false) if (condition) _true; else _false;

using namespace std;
//
// Created by karayuu on 2019-3-28.
//


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

        if (n == 0) break;

        int a[1001];
        FOR(i, 0, n) {
            cin >> a[i];
        }

        double sum = 0.0;
        FOR(i, 0, n) {
            sum += a[i];
        }
        double ave = sum / n;

        double si = 0.0;
        FOR(i, 0, n) {
            si += pow(a[i] - ave, 2);
        }

        double x = si / (double) n;
        printf("%.5f\n", sqrt(x));
    }
}


Measured memory_bytes: 3156
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>
#include <cassert>

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

int main(){
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    ll now = (a[0]==0) ? 1LL : a[0];
    ll tmp_ans1 = (a[0]==0) ? abs(a[0])+1LL : 0;
    for (int i = 1; i < n; ++i) {
        if (now >= 0 && now+a[i] >= 0) {
            tmp_ans1 += abs(now+a[i])+1LL;
            now = -1LL;
        }
        else if (now < 0 && now+a[i] <= 0) {
            tmp_ans1 += abs(now+a[i])+1LL;
            now = 1LL;
        }
        else {
            now += a[i];
        }
        //cout << "1: " << " " << i << " " << now << " " << tmp_ans1 << endl;
    }
    now = (a[0] < 0) ? 1LL : -1LL;
    ll tmp_ans2 = abs(a[0]) + 1LL;
    for (int i = 1; i < n; ++i) {
        if (now >= 0 && now+a[i] >= 0) {
            tmp_ans2 += abs(now+a[i])+1LL;
            now = -1LL;
        }
        else if (now < 0 && now+a[i] <= 0) {
            tmp_ans2 += abs(now+a[i])+1LL;
            now = 1LL;
        }
        else {
            now += a[i];
        }
        //cout << "2: " << i << " " << now << " " << tmp_ans2 << endl;
    }
    //cout << tmp_ans1 << " " << tmp_ans2 << endl;
    cout << min(tmp_ans1, tmp_ans2) << endl;
    return 0;
}


Measured memory_bytes: 1024
void main()
{
    long n = rdElem;
    long[][] a = n.rdMat;

    bool[][] ok = new bool[][](n, n);
    foreach (i; 0 .. n)
    {
        ok[i][] = true;
    }

    foreach (i; 0 .. n)
    {
        foreach (j; 0 .. n)
        {
            foreach (k; 0 .. n)
            {
                if (i == j || j == k || k == i) continue;
                if (a[j][k] > a[j][i] + a[i][k])
                {
                    writeln(-1);
                    return;
                }
                if (a[j][k] == a[j][i] + a[i][k] && ok[j][i] && ok[i][k])
                {
                    ok[j][k] = false;
                }
            }
        }
    }

    long total;
    foreach (i; 0 .. n-1)
    {
        foreach (j; i+1 .. n)
        {
            if (ok[i][j]) total += a[i][j];
        }
    }

    total.writeln;
}

enum long mod = 10^^9 + 7;
enum long inf = 1L << 60;

T rdElem(T = long)()
if (!is(T == struct))
{
    return readln.chomp.to!T;
}

alias rdStr = rdElem!string;
alias rdDchar = rdElem!(dchar[]);

T rdElem(T)()
if (is(T == struct))
{
    T result;
    string[] input = rdRow!string;
    assert(T.tupleof.length == input.length);
    foreach (i, ref x; result.tupleof)
    {
        x = input[i].to!(typeof(x));
    }
    return result;
}

T[] rdRow(T = long)()
{
    return readln.split.to!(T[]);
}

T[] rdCol(T = long)(long col)
{
    return iota(col).map!(x => rdElem!T).array;
}

T[][] rdMat(T = long)(long col)
{
    return iota(col).map!(x => rdRow!T).array;
}

void rdVals(T...)(ref T data)
{
    string[] input = rdRow!string;
    assert(data.length == input.length);
    foreach (i, ref x; data)
    {
        x = input[i].to!(typeof(x));
    }
}

void wrMat(T = long)(T[][] mat)
{
    foreach (row; mat)
    {
        foreach (j, compo; row)
        {
            compo.write;
            if (j == row.length - 1) writeln;
            else " ".write;
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.traits;
import std.container;
import std.functional;
import std.typecons;
import std.ascii;
import std.uni;

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

int main(){
  int h, n;
  cin >> h >> n;
  int sum = 0;
  for(int i = 0; i < n; i++){
    int a;
    cin >> a;
    sum += a;
  }
  puts(sum >= h ? "Yes" : "No");
}


Measured memory_bytes: 256
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long LL;

template<typename T>
istream& operator >> (istream& is, vector<T>& vs){
  for(T& v: vs) is >> v;
  return is;
}
template<typename T>
ostream& operator << (ostream& os, vector<T>& vs){
  for (const T& v : vs) os << v << " ";
  return os;
}

int main() {
  int N, M; cin >> N >> M;
  int sum = 0;
  for (int i = 0; i < M; ++i) {
    int a; cin >> a;
    sum += a;
  }
  if (N >= sum)
    cout << N - sum << endl;
  else
    cout << -1 << endl;
}


Measured memory_bytes: 3620
#include <iostream>

int main(){
	//紙 3 はさみ 2 石 1
	bool eflag = false;
	while(!eflag){
		int hands[5] = {0}, things[4] = {0};
		for(int i=0;i<5&&!eflag;i++){
			int n;
			std::cin >> n;
			hands[i] = n, things[n]++;
			if(!n)eflag = true;
		}
		if(!eflag){
			int winner = 0;
			//あいこのとき
			if(things[1] && things[2] && things[3])
				winner = -1;
			else if(things[1] && things[2])
				winner = 1;
			else if(things[2] && things[3])
				winner = 2;
			else if(things[1] && things[3])
				winner = 3;
			else
				winner = -1;
			for(int i=0;i<5;i++){
				if(winner < 0)
					std::cout << "3\n";
				else if(hands[i] == winner)
					std::cout << "1\n";
				else
					std::cout << "2\n";
			}
		}
	}
}

Measured memory_bytes: 0
#include <stdio.h>

int main()
{
	int a, b, c;
	scanf("%d %d", &a, &b);
	
	if (a==1 && b==2)
{
	printf("3");
}
	else if(a==2 && b==1)
{
	printf("3");
}
	else if(a==2 && b==3)
{
	printf("1");
}
	else if(a==3 && b==2)
{
	printf("1");
}
	else if (a==1 && b==3)
{
	printf("2");
}
	else if(a==3 && b==1)
{
	printf("2");
}
	return 0;
}

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

using i64 = int64_t;

template<typename T> class QueueAggregation{
private:
    struct Node {
        T val, sum;
    };

    std::stack<Node> front_stack, back_stack;
    const std::function<T(T, T)> op;

public:
    QueueAggregation(std::function<T(T, T)> op) : op(op), front_stack(), back_stack() {}

    bool empty() const { return front_stack.empty() && back_stack.empty(); }

    std::size_t size() const { return front_stack.size() + back_stack.size(); }

    T fold_all() const {
        assert(!empty());
        if (front_stack.empty()) {
            return back_stack.top().sum;
        } else if (back_stack.empty()) {
            return front_stack.top().sum;
        } else {
            return op(front_stack.top().sum, back_stack.top().sum);
        }
    }

    void push(const T &x) {
        if (back_stack.empty()){
            back_stack.push({x, x});
        } else {
            T s = op(back_stack.top().sum, x);
            back_stack.push({x, s});
        }
    }

    void pop() {
        assert(!empty());
        if (front_stack.empty()) {
            front_stack.push({back_stack.top().val, back_stack.top().val});
            back_stack.pop();
            while (!back_stack.empty()) {
                T s = op(back_stack.top().val, front_stack.top().sum);
                front_stack.push({back_stack.top().val, s});
                back_stack.pop();
            }
        }
        front_stack.pop();
    }

    T front() const { return front_stack.top().val; }
};

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> v;
    for(int i=0;i<n;++i){
        int p;
        cin >> p;
        v.push_back(p);
    }

    QueueAggregation<int> min_que([](int a, int b){return min(a, b);});
    QueueAggregation<int> max_que([](int a, int b){return max(a, b);});

    int ans = n - k + 1;
    for(int i=0;i<k;++i){
        min_que.push(v[i]);
        max_que.push(v[i]);
    }
    for(int i=0;i+k<n;++i){
        min_que.pop(); max_que.pop();
        int mini = min_que.fold_all();
        int maxi = max_que.fold_all();
        //cerr << mini << " " << maxi << endl;
        if(v[i] < mini && v[i+k] > maxi)ans--;
        min_que.push(v[i+k]);
        max_que.push(v[i+k]);
    }

    int len = 0, cnt = 0, maxi = -1;
    for(int i=0;i<n;++i){
        if(v[i] > maxi){
            maxi = v[i];
            len++;
        }else{
            if(len >= k)cnt++;
            maxi = v[i];
            len = 1;
        }
    }

    if(len >= k)cnt++;

    if(cnt > 1)ans -= (cnt - 1);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4340
using System;

public class Program
{
    public void Solve()
    {
        var sc = new Scanner();
        int N = sc.NextInt();
        long[] A = sc.LongArray();

        long sum = 0;
        foreach (long i in A)
        {
            sum += i;
        }

        long ans = long.MaxValue;
        long s = 0;
        for (int i = 0; i < N - 1; i++)
        {
            s += A[i];
            long t = sum - s;
            ans = Math.Min(ans, Math.Abs(s - t));
        }

        Console.WriteLine(ans);
    }

    public static void Main(string[] args)
    {
        new Program().Solve();
    }
}

class Scanner
{
    public Scanner()
    {
        _pos = 0;
        _line = new string[0];
    }

    const char Separator = ' ';
    private int _pos;
    private string[] _line;

    #region スペース区切りで取得

    public string Next()
    {
        if (_pos >= _line.Length)
        {
            _line = Console.ReadLine().Split(Separator);
            _pos = 0;
        }

        return _line[_pos++];
    }

    public int NextInt()
    {
        return int.Parse(Next());
    }

    public long NextLong()
    {
        return long.Parse(Next());
    }

    public double NextDouble()
    {
        return double.Parse(Next());
    }

    #endregion

    #region 型変換

    private int[] ToIntArray(string[] array)
    {
        var result = new int[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = int.Parse(array[i]);
        }

        return result;
    }

    private long[] ToLongArray(string[] array)
    {
        var result = new long[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = long.Parse(array[i]);
        }

        return result;
    }

    private double[] ToDoubleArray(string[] array)
    {
        var result = new double[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = double.Parse(array[i]);
        }

        return result;
    }

    #endregion

    #region 配列取得

    public string[] Array()
    {
        if (_pos >= _line.Length)
            _line = Console.ReadLine().Split(Separator);

        _pos = _line.Length;
        return _line;
    }

    public int[] IntArray()
    {
        return ToIntArray(Array());
    }

    public long[] LongArray()
    {
        return ToLongArray(Array());
    }

    public double[] DoubleArray()
    {
        return ToDoubleArray(Array());
    }

    #endregion
}

Measured memory_bytes: 35408
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String[] disp = 
			{
				"0111111",
				"0000110",
				"1011011",
				"1001111",
				"1100110",
				"1101101",
				"1111101",
				"0100111",
				"1111111",
				"1101111",
				"0000000"
			};
		
		int[] disp_b = new int[11];
		
		for(int i = 0; i < 11; i++){
			disp_b[i] = Integer.parseInt(disp[i] , 2);
		}
		
		while (true) {
			final int n = sc.nextInt();
			
			if(n == -1){
				break;
			}
			
			int cur = 10;
			
			for(int i = 0; i < n; i++){
				int next = sc.nextInt();
				String str = Integer.toString(disp_b[cur] ^ disp_b[next], 2);
				if(str.length() != 7){
					StringBuilder b = new StringBuilder();
					for(int j = 0; j < 7 - str.length(); j++){
						b.append("0");
					}
					b.append(str);
					str = b.toString();
				}
				System.out.println(str);
				cur = next;
			}
			
		}
	}

}

Measured memory_bytes: 12000
a, b, m = map(int, input().split())
fridge = list(map(int, input().split()))
micro = list(map(int, input().split()))
c = []
for i in range(m):
    c.append(list(map(int, input().split())))
costs = []
for i in c:
    temp = fridge[i[0]-1]+micro[i[1]-1]-i[2]
    costs.append(temp)
fridge.sort()
micro.sort()
costs.append(fridge[0]+micro[0])
costs.sort()
print(costs[0])


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

using namespace std;

#define DUMP(x) std::cout << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()
#define YES puts("YES")
#define Yes puts("Yes")
#define NO puts("NO")
#define No puts("No")
#define IMP puts("IMPOSSIBLE")
#define Imp puts("Impossible")
#define imp puts("impossible")
#define pb push_back

template <typename T>
T dup(T x, T y)
{
    return (x + y - 1) / y;
};
template <typename A, size_t N, typename T>
inline void arrayFill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }

using ll = int64_t;
using vint = vector<int32_t>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pint = pair<int32_t, int32_t>;
using pll = pair<ll, ll>;
using setint = unordered_set<int32_t>;
using setstr = unordered_set<string>;
using qint = queue<int32_t>;

constexpr std::int32_t INF = 1001001001;
constexpr std::int64_t LINF = 1001001001001001001;

void Main()
{
    string s;
    cin >> s;

    int n = s.length() - 1;

    ll sum = 0;
    rep(bit, (1 << n))
    {
        vint S;
        ll tmp = 0;
        rep(i, n)
        {
            tmp += (s[i] - '0');
            if (bit & (1 << i))
            {
                sum += tmp;
                tmp = 0;
            }
            else
            {
                tmp = tmp * 10;
            }
        }
        sum += tmp + (s.back() - '0');
    }
    cout << sum << endl;
}

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


Measured memory_bytes: 256
def get_total(set_num, set_amount):
    total_num = 0
    total_amount = 0
    while True:
        total_num += set_num
        total_amount += set_amount
        if total_num >= num:
            break
    return total_num, total_amount


num, x_num, x_price, y_num, y_price = [int(i) for i in input().split()]

# セットX
x_num, x_amount = get_total(x_num, x_price)

# セットY
y_num, y_amount = get_total(y_num, y_price)

print(x_amount if x_amount < y_amount else y_amount)



Measured memory_bytes: 5604
s = input()
t = input()
s_l = {}
t_l = {}
for i in range(len(s)):
    if s[i] in s_l:
        s_l[s[i]]+=1
    else:
        s_l[s[i]]=1
    if t[i] in t_l:
        t_l[t[i]]+=1
    else:
        t_l[t[i]]=1

s_arr = []
t_arr = []
for i in s_l.values():
    s_arr.append(i)
for i in t_l.values():
    t_arr.append(i)
s_arr = sorted(s_arr)
t_arr = sorted(t_arr)
flag = False
for i in range(len(s_arr)):
    if s_arr[i] != t_arr[i]:
        flag = True
        break
if flag:
    print('No')
else:
    print('Yes')

Measured memory_bytes: 3632
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	win := false
	for i := 0; i < n; i++ {
		var a int
		fmt.Scan(&a)
		if a%2 == 1 {
			win = true
		}
	}
	if win {
		fmt.Println("first")
	} else {
		fmt.Println("second")
	}
}


Measured memory_bytes: 5504
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, a, b) for(int i = (a), i_len = (b); i < b; ++i)

int main()
{
    int N;
    cin >> N;
    char S[N+3];
    cin >> S;
    int res = 0, x = 0;
    REP(i, 0, N) {
        if(S[i] == 'I') ++x;
        if(S[i] == 'D') --x;
        res = max(res, x);
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

void Solve(std::vector<int64_t> a,int start_right, const int n){
  //start_right==n -> すべて右から左へ処理
  std::vector<std::pair<int,int>> result;
  for(int edit=start_right+1;edit<n;edit++){
    if(a[edit-1]<=a[edit]) continue;
    while(a[edit-1]>a[edit]){
      if(result.size()>=2*n)
        return;
      result.push_back(std::make_pair(edit-1,edit));
      a[edit]+=a[edit-1];
    }
  }
  for(int edit=start_right-2;edit>=0;edit--){
    if(a[edit]<=a[edit+1]) continue;
    while(a[edit]>a[edit+1]){
      if(result.size()>=2*n)return;
      result.push_back(std::make_pair(edit+1,edit));
      a[edit]+=a[edit+1];
    }
  }
  if(result.size()<=2*n){
    cout<<result.size()<<endl;
    for(auto p:result){
      cout<<p.first+1<<" "<<p.second+1<<endl;
    }
    exit(0);
  }
}

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

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

  if(a[0]>=0){
    Solve(a,0,n);
  }
  for(int left=0;left<n-1;left++){
    if(a[left]<=0&&a[left+1]>=0){
      Solve(a,left+1,n);
    }
  }
  if(a[n-1]<=0){
    Solve(a,n,n);
  }

  cout<<"ＷＡ！ｗ"<<endl;






  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

int main(){
    int a,b,ans,n=1;
    cin>>a>>b;
    if(a<b){
        for(int i=0;i<b;i++){
            ans=ans+a*n;
            n=n*10;
        }
    }
    else{
        for(int i=0;i<a;i++){
            ans=ans+b*n;
            n=n*10;
        }
    }
    cout<<ans<<endl;
   return 0;
}

Measured memory_bytes: 256
/*
    Problem 2
    https://atcoder.jp/contests/abc106/tasks/abc106_b
*/
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
int cntDivisor(int x) {
    int ret = 0;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            ret++;
            if (i * i != x) ret++;
        }
    }
    return ret;
}
/* main */
int main(){
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 105; i <= n; i+=2) ans += (cntDivisor(i) == 8);
    cout << ans << '\n';
}


Measured memory_bytes: 3496
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))


# dp[i + 1][smaller][j] = 上からi桁目までで0でない桁がj個ある数字の数
N = input()
K = I()
l = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(l + 1)]
dp[0][False][0] = 1
for i in range(1, l + 1):
    N_i = int(N[i - 1])
    for smaller in [True, False]:  # smaller := Nより小さいことが確定している
        for j in range(K + 1):
            for d in range((9 if smaller else N_i) + 1):
                if j - (0 if d == 0 else 1) >= 0:
                    dp[i][smaller or d < N_i][j] += dp[i - 1][smaller][j - (0 if d == 0 else 1)]

print(dp[l][True][K] + dp[l][False][K])


Measured memory_bytes: 40816
#include <iostream>

using namespace std;

int main(void){
  int n;
  cin>>n;
  long long int l[n];
  l[0]=2;
  l[1]=1;
  for(int i=2;i<=n;i++){
    l[i]=l[i-1]+l[i-2];
  }
  cout<<l[n]<<endl;
  return 0;
}

Measured memory_bytes: 256
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
red = []
blue = []

for _ in range(n):
    red.append(list(li()))
    
for _ in range(n):
    blue.append(list(li()))
    
# 二部グラフの作成
graph = [{} for _ in range(2*n+2)]

for i,r in enumerate(red):
    for j,b in enumerate(blue):
        if r[0]<b[0] and r[1]<b[1]:
            graph[i+1].update({n+j+1: [1, 1]})
            graph[n+j+1].update({i+1: [0, 0]})
            
for i in range(1,n+1):
    graph[0].update({i: [1, 1]})
    graph[i].update({0: [0, 0]})
    
    graph[n+i].update({2*n+1: [1, 1]})
    graph[2*n+1].update({n+i: [0, 0]})
    

# 最大フロー
def dfs(start:int, goal:int, flow:int, visited:list):
    if start == goal:
        return flow
    
    visited[start] = True
    
    for key,value in graph[start].items():
        to = key
        cap, isFwd = value
        
        if not visited[to] and cap > 0:
            d = dfs(to, goal, min(flow, cap),visited)
            
            if d > 0:
                graph[start][to][0] -= d
                graph[to][start][0] += d
                
                return d
            
    return 0

def max_flow(start: int, goal: int):
    INF = float("inf")
    flow = 0
    while True:
        visited = [False]*(2*n+2)
        f = dfs(start,goal,INF,visited)
        
        if f == 0:
            return flow
        flow += f
        
ans = max_flow(0,2*n+1)
print(ans)

Measured memory_bytes: 3956
#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define com bool operator<(const node &b)
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn = (ll) 2e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
int T = 1;

void solve() {
    int x;
    cin >> x;
    int gcd = __gcd(x, 360ll);
    cout << 360 / gcd;
}

signed main() {
    start;
    while (T--)
        solve();
    return 0;
}

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

int main () {
  int a,b,c,k;
  cin >> a >> b >> c >> k;
  for(int i=0;i<k;i++){
    if(a>=b) b*=2;
    else c*=2;
  }
  if(a<b && b<c) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3632
#include <stdio.h>

int main(void) {
	// your code goes here
	int x,h,m,s;
	scanf("%d",&x);
	s = x % 60;
	m = (x / 60) % 60;
	h = x / 3600;
	printf("%d:%d:%d\n",h,m,s);
	return 0;
}



Measured memory_bytes: 2140
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define int ll
#define double long double
#define YES cout<<"YES"<<'\n'
#define NO cout<<"NO"<<'\n'
#define Yes cout<<"Yes"<<'\n'
#define No cout<<"No"<<'\n'
#define yes cout<<"yes"<<'\n'
#define no cout<<"no"<<'\n'
void YN(bool flg) {cout<<(flg?"YES":"NO")<<'\n';}
void Yn(bool flg) {cout<<(flg?"Yes":"No")<<'\n';}
void yn(bool flg) {cout<<(flg?"yes":"no")<<'\n';}
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
#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 out(n) cout << n << '\n'
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<VI> VVI;
const int MOD = 1000000007;
const long long INF = 10e10;
const double PI = acos(-1.0);
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; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
int POW(int a, int n) { int r = 1; while (n > 0) { if (n & 1)r *= a; a *= a; n >>= 1; }return r; }
int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*素因数分解*/map< int, int >prime_factor(int n){map< int, int > ret;for(int i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}
/*約数列挙*/vector<int> divisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------ライブラリとか----------------

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(15);

    int n; cin >> n;
    VI l(n+1); l[0]=2; l[1]=1;
    FOR(i,2,n+1) l[i]=l[i-2]+l[i-1];
    cout << l[n] << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	Scanner sc = new Scanner(System.in);
	final static long LNF = 1L << 60;
	final static double EPS = 1e-9;

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

	void run() {

		int n = ni();
		long[] h = new long[100010];
		long[] dp = new long[100010];

		for (int i = 0; i < n; i++) {
			h[i] = ni();
		}
		for (int i = 0; i < dp.length; i++) {
			dp[i] = LNF;
		}

		dp[0] = 0;
		for (int i = 1; i < n; i++) {
			dp[i] = Util.min(dp[i], dp[i - 1] + Math.abs(h[i] - h[i - 1]));
			if (i > 1) {
				dp[i] = Util.min(dp[i], dp[i - 2] + Math.abs(h[i] - h[i - 2]));
			}
		}
		System.out.println(dp[n-1]);
	}

	int ni() {
		return Integer.parseInt(sc.next());
	}

	long nl() {
		return sc.nextLong();
	}

	double nd() {
		return Double.parseDouble(sc.next());
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}

	static class Util {
		static <T extends Comparable<T>> T max(T a, T b) {
			if (a.compareTo(b) > 0) {
				return a;
			} else {
				return b;
			}
		}

		static <T extends Comparable<T>> T min(T a, T b) {
			if (a.compareTo(b) < 0) {
				return a;
			} else {
				return b;
			}
		}
	}

}


Measured memory_bytes: 48912
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
  ll N,K,ans=0;
  cin>>N>>K;
  vector<ll> vec(N);
  for(ll i=0;i<K;i++){
    ll d;
    cin>>d;
    for(ll i=0;i<d;i++){
      ll a;
      cin>>a;
      vec.at(a-1)++;
    }
  }
  for(ll i=0;i<N;i++){
    if(vec.at(i)==0){ans++;}
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3632
#include <stdio.h>

int main(void){
  int i,j,n,taro_p=0,hana_p=0;
  char taro[101], hana[101];

  scanf("%d", &n);

  for(i=0;i<n;i++){
    scanf("%s %s", taro, hana);

    for(j=0;;j++){
      if(taro[j] > hana[j]){
        taro_p += 3;
        break;
      }else if(taro[j] < hana[j]){
        hana_p += 3;
        break;
      }else if(taro[j] + hana[j] == 0){
        hana_p++;
        taro_p++;
        break;
      }
    }
  }

  printf("%d %d\n", taro_p , hana_p);
  return 0;
}



Measured memory_bytes: 2080
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static long Mod = (long)1e9 + 7;
        static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            var NK = Sarray();
            var N = NK[0];
            var K = NK[1];
            var S = ReadLine();
            var runlen = new List<Tuple<char, long>>();
            for (var i = 0; i < N; ++i)
            {
                var t = S[i];
                var cnt = 1L;
                while (i < N - 1 && t == S[i + 1])
                {
                    ++cnt;
                    ++i;
                }
                runlen.Add(Tuple.Create(t, cnt));
            }
            //最初の塊が直立の場合
            var rui = new long[runlen.Count + 1];
            for (var i = 1; i < rui.Length; ++i)
                rui[i] = rui[i - 1] + runlen[i - 1].Item2;
            var ans = 0L;
            var strt = 0L;
            if (runlen[0].Item1 == '0')
            {
                var l = Min(runlen.Count, K * 2);
                ans = rui[l];
                strt = 1;
            }
            for (var i = strt; i < runlen.Count; i += 2)
            {
                var l = Min(runlen.Count, i + K * 2 + 1);
                ans = Max(ans, rui[l] - rui[i]);
            }
            WriteLine(ans);
            //Out.Flush();
        }
    }
}

Measured memory_bytes: 16224
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#define pb push_back
#define mp make_pair
using namespace std;
const int N=105;

long long n,m;
long long prob=1;

long long ans;

int main()
{
    int i;

    cin>>n>>m;

    for(i=1;i<=m;i++)
        prob*=2;

    ans=(n-m)*100 + m*1900;
    ans*=prob;

    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 256
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入
  var input = Number(input)
	console.log(Math.pow(input, 3));
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 22080
#include <bits/stdc++.h>
 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define li long long
#define itn int
 
using namespace std;
 
inline int nxt(){
	int n;
	scanf("%d", &n);
	return n;
}

ostream& operator <<(ostream& ostr, const vector<int>& a) {
	ostr << "(";
	for (size_t i = 0; i < a.size(); ++i) {
		if (i) {
			ostr << ", ";
		}
		ostr << a[i];
	}
	ostr << ")";
	return ostr;
}

int main(){

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

	vector<int> dp(n);
	dp[0] = a[0];
	for (int i = 1; i < n; ++i) {
		if (a[i] == a[i - 1] + 1) {
			if (dp[i - 1] == a[i - 1] - 2 * (i - 1)) {
				dp[i] = dp[i - 1] - 1;
			} else {
				dp[i] = dp[i - 1];
			}
		} else {
			dp[i] = dp[i - 1];
		}
	}

	vector<int> place(n);
	for (int i = 1; i < n; ++i) {
		if (dp[i - 1] > 0) {
			place[i] = 0;
		} else {
			place[i] = 1 + (-dp[i - 1]) / 2;
		}
	}

	// cerr << dp << "\n";

	const int mod = 1000000007;
	long long ans = 1;
	vector<int> cnt(1, 0);
	for (int i = 0; i < n; ++i) {
		while (place[i] >= cnt.size()) {
			cnt.push_back(cnt.back());
		}
		cnt.back() += 1;
	}
	while (cnt.size() < n) {
		cnt.push_back(cnt.back());
	}
	for (int i = 0; i < n; ++i) {
		ans = ans * (cnt[i] - i) % mod;
	}

	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 2044