akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int n=cin.nextInt();
		long[][] dp=new long[n+1][21];
		int[]a = new int[n];
		for(int i=0;i<n;i++){
			a[i]=cin.nextInt();
		}
		dp[0][a[0]]=1;
		for(int i=1;i<n-1;i++){
			for(int j=0;j<21;j++){
				if(j+a[i]<21&&dp[i-1][j+a[i]]!=-1){
					dp[i][j]+=dp[i-1][j+a[i]];
				}
				if(j-a[i]>=0&&dp[i-1][j-a[i]]!=-1){
					dp[i][j]+=dp[i-1][j-a[i]];
				}
			}
		}
		for(int j=0;j<21;j++){
//			System.out.printf("%5d",j);
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<21;j++){
//				System.out.printf("%5d",dp[i][j]);
			}
//			System.out.println();
		}
		System.out.println(dp[n-2][a[n-1]]);
	}

}

Measured memory_bytes: 18140
/*#include <iostream>
#include <string>
using namespace std;

int main(){
	 ios::sync_with_stdio(false);
	string a, b;
	int x, i = 0;
	cin >> a >> b;
	for(int i = 0;a[i];i++){
		i = a.find(b, i);
		if(i == -1)break;
		cout << i << endl;
	}
	while((x = a.find(b, i)) != -1){
		cout << x << endl;
		i = x + 1;
	}
	return 0;
}*/

#include <iostream>
#include <string>
using namespace std;
string t,p;
int main(){
	ios::sync_with_stdio(false);
	cin>>t>>p;
	for(int i=0;t[i];i++){
		i=t.find(p, i);
		if(i==string::npos)break;
		cout<<i<<'\n';
	}
	return 0;
}

Measured memory_bytes: 4664
import java.util.*;

public class Main
{
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
		int a=sc.nextInt();
		
		if(a==999)
			a=111;
		else if(a==991)
			a=119;
		else if(a==911)
			a=199;
		else if(a==919)
			a=191;
		else if(a==191)
			a=919;
		else if(a==111)
			a=999;
		else if(a==199)
			a=911;
		else if(a==119)
			a=991;
		else if(a==191)
			a=919;
		
		System.out.println(a);
	}
}	

Measured memory_bytes: 21716
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>

using namespace std;

int main(){
	long long sx, sy, gx, gy;
	static double dist[1002][1002];
	while(cin >> sx >> sy >> gx >> gy){
		int N; cin >> N;
		vector<long long> x(N+2), y(N+2), r(N+2);
		x[0] = sx, y[0] = sy, r[0] = 0;
		x[N+1] = gx, y[N+1] = gy, r[N+1] = 0;
		for(int i=1;i<=N;i++) cin >> x[i] >> y[i] >> r[i];
		for(int i=0;i<N+2;i++){
			dist[i][i] = 0.0;
			for(int j=i+1;j<N+2;j++){
				double dx = x[i] - x[j];
				double dy = y[i] - y[j];
				double d = sqrt(dx*dx + dy*dy);
				dist[i][j] = dist[j][i] = max(0.0, d - r[i] - r[j]);
			}
		}
		vector<int> visit(N+2, 0);
		vector<double> res(N+2, 1e18);
		res[0] = 0.0;
		for(int i=0;i<N+2;i++){
			int minIdx = -1;
			for(int j=0;j<N+2;j++){
				if(visit[j]) continue;
				if(minIdx == -1 || res[minIdx] > res[j]) minIdx = j;
			}
			visit[minIdx] = 1;
			for(int j=0;j<N+2;j++){
				res[j] = min(res[j], res[minIdx] + dist[minIdx][j]);
			}
		}
		printf("%.9lf\n", res.back());
	}
}


Measured memory_bytes: 8192
#include <stdio.h>

int main () {
	int sLength, sLetter;
	char text[55];
	
	scanf("%d%d", &sLength, &sLetter);
	getchar();
	scanf("%s", &text);
	text [sLetter-1] += 32;
	printf("%s\n", text);
	
	return 0;
}

Measured memory_bytes: 1608
from sys import stdin
from collections import deque
S = (stdin.readline().rstrip())
Q = int(stdin.readline().rstrip())
cnt = 0
ccnt = 0
s = deque(["@"])
for i in range(Q):
    data = [(x) for x in stdin.readline().rstrip().split()]
    if data[0] == "2":
        if data[1] == "1":
            if cnt % 2 == 0:
                s.appendleft(data[2])
            else:
                s.append(data[2])
        else:
            if cnt % 2 == 0:
                s.append(data[2])
            else:
                s.appendleft(data[2])
    else:
        cnt += 1
s = "".join(s)
if cnt % 2 != 0:
    s = s[::-1]
if cnt % 2 != 0:
    S = S[::-1]
ans = s.replace("@",S)
print(ans)

Measured memory_bytes: 6900
# -*- coding: utf-8 -*-
import numpy as np
import itertools
import math
N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
  x[i], y[i] = map(int, input().split())
  
city = range(N)
ret = 0

def cal(ind):
  dist = 0
  n1 = ind[0]
  for n2 in ind:
    if n1 == n2:
      continue
    dist += dis(n1, n2)
    n1 = n2
  return dist

def dis(n1, n2):
  return np.sqrt((x[n1] - x[n2]) ** 2 + (y[n1] - y[n2]) ** 2)
  

for ind in itertools.permutations(city):
  ret += cal(ind)
print(ret / math.factorial(N))



Measured memory_bytes: 12512
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7;
const int mod = 1e9 + 7;
typedef long long ll;
int n, m, k;

int ar[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
int main()
{
    scanf("%d", &n);
    printf("%d\n", ar[n - 1]);

    return 0;
}


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

int main(){
    int n; cin >> n;
    queue<int> q;
    rep(i,n) {
        int a; cin >> a;
        q.push(a);
    }
    int counter = 1;
    int ans = 0;
    while(!q.empty()){
        if(q.front()==counter){
            counter++;
            ans++;
        }
        q.pop();
    }
    ans = n - ans;
    if(counter != 1) cout << ans << endl;
    else cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 1024
n = input()

zorome_count = 0
max_zorome_count = 0

for i in range(int(n)):
  a,b = input().split(" ")
  if a == b:
    zorome_count += 1
  else:
    if zorome_count > max_zorome_count:
      max_zorome_count = zorome_count
    zorome_count = 0

if zorome_count > max_zorome_count:
  max_zorome_count = zorome_count

if max_zorome_count >= 3:
  print("Yes")
else:
  print("No")


Measured memory_bytes: 9172
mod = 10**9+7 #出力の制限
def pow_r(x, n):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r((x ** 2)%1000000007 , n // 2) % mod
    else:  # standard case ② n is odd
        return x * pow_r((x ** 2)%1000000007, (n - 1) // 2) % mod

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    g1=1
    r = min(r, n-r)
    for i in range(n-r+1,n+1):
        g1*=i
        g1%=mod



    return g1 * g2[r] % mod


g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
def getgen(N):
    for i in range( 2, N + 1 ):

        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )




def resolve():
    n,a,b=map(int,input().split())
    sm=pow_r(2,n)-1
    getgen(max(a,b))
    aa=cmb(n,a,mod)
    bb=cmb(n,b,mod)

    sm-=aa

    if sm<0:
        sm+=mod
    sm-=bb
    if sm<0:
        sm+=mod
    
    print(sm)
    







if __name__ == "__main__":
    resolve()


Measured memory_bytes: 66800
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define pp pair<int,int>
#define ll long long
#define ld long double
int inf=100000000;
ll INF=4000000000000000000;
ll MOD=1000000007;



int main() {
  int n,m;
  cin >> n >> m;
  vector<ll> x(n),y(m);
  rep(i,n) cin >> x.at(i);
  rep(i,m) cin >> y.at(i);
  sort(x.begin(),x.end());
  sort(y.begin(),y.end());
  vector<ll> a(n-1),b(m-1);
  rep(i,n-1){
    a.at(i)=x.at(i+1)-x.at(i);
  }
  rep(i,m-1){
    b.at(i)=y.at(i+1)-y.at(i);
  }
  ll xx=0,yy=0;
  rep(i,n-1){
    xx=(xx+a.at(i)*(i+1)*(n-1-i))%MOD;
  }
  rep(i,m-1){
    yy=(yy+b.at(i)*(i+1)*(m-1-i))%MOD;
  }
  //cout << xx << " " << yy << endl;
  cout << xx*yy%MOD << endl;
  }

Measured memory_bytes: 3328
//ヘッダー
#include<bits/stdc++.h>
using namespace std;

//型定義
typedef long long ll;

//定数
const int INF=1e+9;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

int main(){
    string S;
    cin>>S;
    int N=S.size();
    vector<vector<ll>> dp(N+1,vector<ll>(4,0));
    dp[0][0]=1;
    REP(i,N){
        if(S[i]=='?'){
            REP(j,4){
                dp[i+1][j]=3*dp[i][j]%MOD;
            }
        }else{
            REP(j,4){
                dp[i+1][j]=dp[i][j]%MOD;
            }
        }
        
        if(S[i]=='A'||S[i]=='?'){
            dp[i+1][1]+=dp[i][0];
        }
        if(S[i]=='B'||S[i]=='?'){
            dp[i+1][2]+=dp[i][1];
        }
        if(S[i]=='C'||S[i]=='?'){
            dp[i+1][3]+=dp[i][2];
        }

        REP(j,4){
            dp[i+1][j]%=MOD;
        }
        
    }
    cout<<dp[N][3]<<endl;
}

Measured memory_bytes: 10392
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <ccomplex>
#include <unordered_map>
#include <cstring>
#include <iostream>
#include <numeric>
#include <sstream>
#include <set>
#include <map>
#include <tuple>
#include <iomanip>

using namespace std;
#define MAX 1LL << 60
#define MOD 1000000007
#define BOX 200000

typedef long long ll;

#define rep(i, s, e) for(unsigned int i = s; i < e; i++)
#define repR(i, s, e) for(ll i = s; i > e; i--)
#define reft0(i, j) setfill('0') << setw(i) << j
#define fix(i) fixed << setprecision(i)
#define so(a) sort(begin(a), end(a))
#define soR(a) sort(begin(a), end(a), greater<ll>())
#define sum(a) accumulate(begin(a), end(a), 0)


template<class T> inline bool chMax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chMin(T& a, T b) { if (a > b) { a = b; return true; } return false; }



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

    double X = 1;
    while(1){
        ll tempN = floor(X * 1.08);
        if (tempN == N) {
            cout << X << endl;
            return 0;
        }
        if (tempN > N) {
            cout << ":(" << endl;
            return 0;
        }
        X++;
    }

    return 0;

}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);

		int i,l=0;
			int sum[] = new int [2000];
			int ave[] = new int [2000];

		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			int score[] = new int [n];
			int j=0,k=0;

			for(i=0;i<n;i++){
				score[i] = sc.nextInt();
				sum[l]+=score[i];
			}
			for(i=0;i<n;i++){
				if(score[i]>=score[j]){
					j=i;
				}
				if(score[i]<=score[k]){
					k=i;
				}
			}
			sum[l]-=score[j];
			sum[l]-=score[k];
			ave[l] = sum[l]/(n-2);
			l++;
		}
		for(i=0;i<l;i++){
			System.out.printf("%d\n",ave[i]);
		}
	}
}

Measured memory_bytes: 21004
import sys
import math
def i():return int(sys.stdin.readline().replace("\n",""))
def i2():return map(int,sys.stdin.readline().replace("\n","").split())
def s():return str(sys.stdin.readline().replace("\n",""))
def l():return list(sys.stdin.readline().replace("\n",""))
def intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def lx():return list(map(lambda x:int(x)*-1,sys.stdin.readline().replace("\n","").split()))
def t():return tuple(map(int,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":pass
n = i()
s = s()
l = list("ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ")
for i in range(len(s)):
    print(l[l.index(s[i])+n],end="")

Measured memory_bytes: 4468
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <iterator>  // std::back_inserter()
#include <algorithm>  // std::copy()
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <cmath>
#include <climits>  // INT_MIN
#include <cctype>  // std::isdigit()
#include <ios>     // std::left, std::right
#include <iomanip> // std::setw(int), std::setfill(char)
using namespace std;

// typedef
typedef long long ll;
typedef unsigned long ul;
// #define int long long

// macro
#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for (int i=0; i < (int)(n); i++)  // 0 ~ n-1
#define REPN(i, n) for (int i=1; i <= (int)(n); i++)  // 1 ~ n
#define DESCEND greater<int>()  // sort 降順 大きい順
#define UNIQUE(vec) (vec).erase(unique(ALL((vec))), (vec).end());  // 必ずsortを行なってから
#define MIN(vec) min_element(ALL((vec)))  // 値を取り出すときは * を先頭につける
#define MAX(vec) max_element(ALL((vec)))
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define SUM(vec) accumulate(ALL((vec)), 0)  // 0 は初期値
#define COPY(vec1, vec2) copy(ALL(vec1), back_inserter(vec2))  // vec1をvec2にコピーする vec2は空にしておく必要あり
#define zero_pad(num) setfill('0') << std::right << setw(num)  // 直後の要素をパディング
#define space_pad(num) setfill(' ') << std::right << setw(num)  // 直後の要素をパディング

// func declaration
template <class T> void print2DVec(vector< vector<T> >&);
template <class T> void calcVec(vector<T>&, int, char);
int char_to_int(const char);

// const
const int INF = 10000000;

/*MEMO
・辞書順
abc < abcd, atcoder < atlas
・イテレータ
std::vector<int>::iterator とタイプするのは面倒なので、
 通常は型推論の auto を使用する。
 auto iter = max_element(ALL(vec));
・2次元配列
vector<vector<int>> vec = {{1, 2, 3}, {4, 5, 6}}
・20×10の配列
vector<vector<int>> vec(20, vector<int>(10, 0));
・(n, m)の多次元配列
vector< vector<int> > vec(n, vector<int>(m, 0))  // 0で初期化
*/

int main() {
    cin.tie();
    ios::sync_with_stdio(false);
    
    // input
    int X, Y, Z;
    cin >> X >> Y >> Z;
    
    if (X == Y) {
        cout << Z << "\n";
    } else if (X == Z) {
        cout << Y << "\n";
    } else {
        cout << X << "\n";
    }
    
    return 0;
}


// function
template <class T> void print2DVec(vector< vector<T> >& vec) {
    REP(i, vec.size()) {
        REP(j, vec.front().size()) {
            cout << vec.at(i).at(j);
        }
        cout << endl;
    }
}

template <class T> void calcVec(vector<T> &vec, int num, char ch) {
    // vec全体への演算
    switch (ch) {
        case '+':
            REP(i, vec.size()) vec.at(i) += num; break;
        case '-':
            REP(i, vec.size()) vec.at(i) -= num; break;
        case '*':
            REP(i, vec.size()) vec.at(i) *= num; break;
        case '/':
            REP(i, vec.size()) vec.at(i) /= num; break;
        case '%':
            REP(i, vec.size()) vec.at(i) %= num; break;
        default:
            cout << "Incorrect Operator" << endl;
    }
}

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


Measured memory_bytes: 256
import math

N=int(input())
number_of_withdrawal=[100000]

# def floor(float_number):
#     integer = 0
#     while integer < float_number:
#         integer+=1
#     if integer == float_number:
#         return integer
#     else:
#         integer-=1
#         return integer

for money_6 in range(0, N+1):
    money_9 = N-money_6

    i=0
    count_6_pow_number=0
    while pow(6,i)<=money_6:
        count_6_pow_number += (math.floor(money_6/pow(6,i)))%6
        i+=1
    j=0
    count_9_pow_number=0
    while pow(9,j)<=money_9:
        count_9_pow_number += (math.floor(money_9/pow(9,j)))%9
        j+=1

    # print(money_6, money_9, sum(count_6_pow_number), sum(count_9_pow_number))
    number_of_withdrawal.append(count_6_pow_number+count_9_pow_number)

print(min(number_of_withdrawal))

Measured memory_bytes: 3860
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

int h,w;
char fie[11][21];
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,1,-1};
bool used[11][21];
vector<string> index2;
string str;

void dfs(int y,int x,int k){
	if(used[y][x])return;
	used[y][x]=true;
	str+=fie[y][x];
	index2.push_back(str);
	dfs((y+dy[k]+h)%h,(x+dx[k]+w)%w,k);
}

int main(void){
	while(1){
		scanf("%d %d%*c",&h,&w);
		if(h+w==0)break;
		index2.clear();
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				scanf("%c",&fie[i][j]);
			}
			scanf("%*c");
		}
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				for(int k=0;k<8;k++){
					memset(used,false,sizeof(used));
					str="";
					dfs(i,j,k);
				}
			}
		}
		sort(index2.begin(),index2.end());
		int res=index2.size();
		index2.push_back("0");
		for(int i=0;i<index2.size();i++){
			if(index2[i].size()>=2){
				if(index2[i]==index2[i-1] && index2[res].size()<index2[i].size())res=i;
			}
		}
		cout << index2[res] << endl;
	}
	return 0;
}

Measured memory_bytes: 28712
#pragma GCC optimize ("Ofast","unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define F first
#define S second
#define setpre(a) cout.precision(a),cout<<fixed;
#define ALL(a) a.begin(),a.end()
#define MEM(a,b) memset(a,b,sizeof a)
#define Tie ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

ll n;

int main() {Tie
    cin >> n;
    cout << (1000 - (n % 1000)) % 1000 << '\n';
}


Measured memory_bytes: 3652
class Battle:
    def __init__(self, A, B, C, D):
        self.A = A
        self.B = B
        self.C = C
        self.D = D

    def result(self):
        while self.A > 0 or self.C > 0:
            self.C -= self.B
            if self.C <= 0:
                return "Yes"
            self.A -= self.D
            if self.A <= 0:
                return "No"


def atc_164b(ABCD: str) -> str:
    A, B, C, D = map(int, ABCD.split(" "))
    battle = Battle(A, B, C, D)
    return battle.result()


ABCD_input = input()
print(atc_164b(ABCD_input))

Measured memory_bytes: 9144
L, R = map(int, input().split())
if L//2019 != R//2019:
    print(0)
elif L % 2019 <= 673 and R % 2019 >= 673 and R - L >= 2:
    print(0)
else:
    ans = 2019
    for i in range(L, R):
        for j in range(i+1,R+1):
            ans = min(ans, (i*j)%2019)
    print(ans)


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

#define REP(i,n) for(int i = 0;i < n;i++)
#define REPR(i,n) for(int i = n-1;i >= 0;i--)
#define FOR(i,m,n) for(int i = m;i < n;i++)
#define INF 2e9
#define ALL(v) v.begin(),v.end()
#define ll long long
#define GREATER greater<int>()

using namespace std;

string pop_back(string s){
    string t = s.substr(0,s.size()-1);
    return t;
}

int gcd(int max,int min){
    
    if(max<min){
        int tmp=max;
        max=min;
        min=tmp;
    }

    if(max%min==0)return min;
    else return gcd(min,max%min);

}

int main(void){

    int n,T;
    cin>>n>>T;
    int minc=INF;
    for(int i=0;i<n;i++){
        int c,t;
        cin>>c>>t;
        if(t<=T){
            minc=min(minc,c);
        }
    }
    if(minc==INF)cout<<"TLE"<<endl;
    else cout<<minc<<endl;

    return 0;
}




Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#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 REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define D()
#define INF 1000000000000
#define MOD 10000007
#define MAXR 100000
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define INITA(a,i,j,v) for(ll k=i;k<=j;k++){a[k]=v;}

int main() {
    int n;
    cin >> n;
    int res = -1;
    int tmp = 0;
    int prev = 0;
    int inp;
    REP(i, n) {
        cin >> inp;
        if (i == 0) {
            tmp = 0;
        } else if (inp <= prev) {
            tmp++;
        } else {
            res = max(res, tmp);
            tmp = 0;
        }
        prev = inp;
    }
    res = max(res, tmp);
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
/**
 * @Author:      K C-L
 * @DateTime:    2018-06-16 20:40:28
 * @Description: 
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef stringstream strstm;
#define fi first
#define se second
#define INF 0X3f3f3f3f
#define SZ(x) ((int)(x).size())
#define pb push_back
#define PI acos(-1.0)
#define E 2.718281829459
#define lowbit(x) (x & (-x))
#define DBG(x) cout << (x) <<  << endl;
#define MST(a,b) memset(a,b,sizeof(a));
#define _for(i,a,b) for(int i = (a); i < (b); ++i)
#define _rep(i,a,b) for(int i = (a); i <= (b); ++i)


int main(int argc, char const *argv[]) {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	int a,b;
	while(cin >> a >> b){
		if(abs(a-b) <= 1) cout << "Yay!" << endl;
		else cout << ":(" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
 
int A[1000000], n;
 
int main() {
  cin >> n;
  for ( int i = 0; i < n; i++ ) {
    scanf("%d", &A[i]);
  }
 
  int q, k, sum = 0;
  cin >> q;
  for ( int i = 0; i < q; i++ ) {
    scanf("%d", &k);
    if ( *lower_bound(A, A + n, k) == k ) sum++;
  }
 
  cout << sum << endl;
 
  return 0;
}


Measured memory_bytes: 3540
using System;


class Program
    {
        static void Main(string[] args)
        {
            
            string[] s = (Console.ReadLine()).Split(' ');
            int p = int.Parse(s[0]);
            int q = int.Parse(s[1]);
            int r = int.Parse(s[2]);

            int max = Math.Max(p, Math.Max(q, r));
            Console.WriteLine(p + r + q - max);

        }
    }

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

int n,d;

int main()
{
    scanf("%d %d",&n,&d);
    int t = 2*d+1;
    double t1 = n*1.0/t;
    int t2 = (int)t1;
    if(t1 > t2)
        printf("%d\n",(t2+1));
    else
        printf("%d\n",t2);
}


Measured memory_bytes: 256
n = int(input())
s = input()
ans = 0
init = True
m = s.count('#')
l = [0] * m
idx = 0
for i in range(n):
    if s[i] == '#':
        l[idx] = i
        idx += 1
ans = m
for i in range(m):
    ans = min(ans, i + (n - l[i] - 1 - (m - i - 1)))
print(ans)

Measured memory_bytes: 16868
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

int main() {
	int N, K, S;
	cin >> N >> K >> S;
	
	vector<int> ans(N);
	
	if (S == 1000000000) {
		REP(i, K) ans[i] = S;
		FOR(i, K, N) ans[i] = 1;
	}
	else {
		REP(i, K) ans[i] = S;
		FOR(i, K, N) ans[i] = 1000000000;
	}
	
	REP(i, N) printf("%d%c", ans[i], i == N - 1 ? '\n' : ' ');
	
	return 0;
}


Measured memory_bytes: 1664
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <unordered_map>
#include <cmath>
using namespace std;

typedef long long llong;
// -2.1e-9 <= int <= 2.1e9

int main()
{
    size_t N; cin >> N;
    vector<int> X(N, 0);
    double target = 0;
    for (size_t i=0; i<N; i++) {
        cin >> X[i];
        target += X[i];
    }
    target /= N;
    int P = std::round(target);

    int ans = 0;
    for (auto &y: X) {
       ans += (y - P) * (y - P);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

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

ll gcd(ll a, ll b)
{
    if (a % b == 0)
    {
        return (b);
    }
    else
    {
        return (gcd(b, a % b));
    }
}

ll lcm(ll a, ll b)
{
    return a / gcd(a, b) * b;
}

inline double nCr(const int n, int r)
{
    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

template <typename T>
T seinomi(T a)
{
    if (a > 0)
    {
        return a;
    }
    else
    {
        return 0;
    }
}

template <typename T>
map<T, T> soinsuubunkai(T n) //連想配列[素因数f.first][個数f.second]
{
    map<T, T> ret;
    for (T i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

template <typename T>
T ketasuu(T num)
{
    return std::to_string(num).length();
}

int kaizyou(int k)
{
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

template <class ForwardIt, class T>
void iota(ForwardIt first, ForwardIt last, T value)
{
    while (first != last)
    {
        *first++ = value;
        ++value;
    }
}

//nの階乗を計算
int factorial(int n)
{
    int answer = 1;
    while (n > 1)
    {
        answer *= n;
        n--;
    }
    return answer;
}
int comb(int n, int r)
{
    return factorial(n) / (factorial(r) * factorial(n - r));
}

long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}


template <typename T>
T amarinasi(T a,T b){
    if(a%b==0)
{
    return a/b;
}
else if(a%b>0)
{
    return a/b+1;
}
else
{
    return a/b-1;
}
}

//小数点以下10桁テンプレート（main関数内の最初に貼付け）
//std::cout << std::fixed << std::setprecision(10);

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

int main(){
string s;
cin>>s;
map<char,ll>rensou;
for(int i=0;i<s.size();i++){
    rensou[s[i]]++;
}
for(int i='a';i<='z';i++){
    if(rensou[i]==0){
        cout<<(char)i<<endl;
        break;
    }
    if(i=='z'){
        cout<<"None"<<endl;
    }
}

}












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

const int M = 1e9+7;
const int b = 70000;
int N, K;

int dp[2][2*b];

void madd(int& a, int b) {
    a = (a+b) % M;
}
void msub(int& a, int b) {
    a = (a-b+M) % M;
}
int mult(int a, int b) {
    return (1LL*a*b) % M;
}

int cnt[b];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> K;
    int sq = (int)(sqrt(N));
    map<int,int> mp;
    for (int i = 1; i <= sq; i++) {
        dp[0][i] = 1 + dp[0][i-1];
        cnt[i] = 1;
        //cout << i << ": " << dp[0][i] << '\n';
    }
    int mx = sq;
    int pt = sq+1;
    for (int i = N/(sq+1); i >= 1; i--) {
        cnt[pt] = (N/i) - (N/(i+1));
        dp[0][pt] = cnt[pt] + dp[0][pt-1];
        mp[i] = pt;
        mx = pt;
        //cout << i << ": " << dp[0][pt] << '\n';
        pt++;
    }
    for (int q = 1; q < K; q++) {
        int curr = q&1;
        int other = curr^1;
        for (int i = 1; i <= sq; i++) {
            int r = mp.count(i) ? mp[i] : N/i;
            dp[curr][i] = dp[other][r];
        }
        pt = sq + 1;
        for (int i = N/(sq+1); i >= 1; i--) {
            int r = i;
            dp[curr][pt] = mult(cnt[pt],dp[other][r]);
            pt++;
        }
        /*
        for (int i = 1; i <= mx; i++) {
            cout << i << ": " << dp[curr][i] << '\n';
        }
        */
        for (int i = 1; i <= mx; i++) {
            madd(dp[curr][i],dp[curr][i-1]);
        }
    }
    int ans = dp[(K-1)&1][mx];
    cout << ans << '\n';
}



Measured memory_bytes: 2432
#include<bits/stdc++.h>
#include<string>
using namespace std;
#define int long long int
const long long mod = 1000000007;
const int N = 2e5+5;
const int inf = 1e18;
int n;
int v[405];
int pre[405];
int dp[405][405];
int solve(int l,int r)
{
    if(dp[l][r]!=inf)
    {
        return dp[l][r];
    }
    if(l==r)
    {
        return dp[l][r]=0;
    }

    for(int k = l+1;k<=r;k++)
    {
        dp[l][r] = min(dp[l][r],solve(l,k-1) + solve(k,r)+ pre[r]-pre[l-1]);
    }

    return dp[l][r];

}
int32_t main()
{   
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    for(int i=0;i<405;i++)
    {
        for(int j=0;j<405;j++)
        {
            dp[i][j]= inf;
        }
    }
    
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
        pre[i] = pre[i-1]+v[i];
    }

    int ans = solve(1,n);
    

    cout<<ans<<endl;
}

Measured memory_bytes: 1536
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int top, S[1000];

void push(int x){
	S[++top] = x;
}

int pop(){
	top--;
	return S[top+1];
}


int main(void){
	
	int a,b;
	top=0;
	char s[100];
	int ans;
	
	
	while( scanf("%s", s) != EOF){
		if ( s[0] == '+' ){
			a=pop();
			b=pop();
			push(a+b);
	    } else if ( s[0] == '-' ){
	    	b=pop();
	    	a=pop();
	    	push(a-b);
	    } else if ( s[0] == '*' ){
	    	a=pop();
	    	b=pop();
	    	push(a*b);
	    } else {
	    	push(atoi(s));
	    }
    }
	
	printf("%d\n", pop());
	
	return 0;
}


Measured memory_bytes: 2036
# https://atcoder.jp/contests/abc077/tasks/arc084_a
# bisectで行けるけどめぐる式の練習

# Bを固定すると、A,Cを二分探索すれば条件を満たす個数が計算できる

from bisect import bisect_left, bisect_right
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


N = read_a_int()
A = read_ints()
B = read_ints()
C = read_ints()

A.sort()
C.sort()

ans = 0
for b in B:
    ans += bisect_left(A, b) * (N - bisect_right(C, b))
    # Cに関しては真に大きい個数を知りたいことに注意
print(ans)


Measured memory_bytes: 92516
x, k ,d = gets.chomp.split(" ").map(&:to_i)
#今いる座標
#ｋkaisuu
#d idou
x = x.abs

kyori = x - k * d
if x > 0
    if kyori > 0
        puts kyori
    elsif kyori == 0
        puts "0"
    elsif kyori < 0
        mae = x / d
        maekyori = x - d * mae
        usiro = x - d * (mae + 1)
        kaizuu = k - mae
        if maekyori != d
            if kaizuu % 2 == 0
                puts maekyori.abs
            else
                puts usiro.abs
            end
        elsif maekyori == d
            if kaizuu % 4 == 1 || kaizuu % 4 == 3
                puts "0"
            else
                puts maekyori.abs
            end
        end
    end
elsif x == 0
    if k % 4 == 1 || k % 3 == 3
        puts d.abs
    else
        puts "0"
    end
end

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

ll ans = INF;

int main()
{
ll a , b , m ;
cin >> a >> b >> m ;
vector<ll> aa(a);
rep(i, a){
  cin >> aa[i];
}
vector<ll>bb(b);
rep(i, b){
  cin >> bb[i];
}
rep(i,m){
  ll x , y , c ;
  cin >> x >> y >> c ;
  ans=min(ans,aa[x-1]+bb[y-1]-c);
}
sort(aa.begin(),aa.end());
sort(bb.begin(),bb.end());
ans=min(ans,aa[0]+bb[0]);
cout << ans << endl;
return 0;
}

Measured memory_bytes: 1792
import sys
from sys import stdin
n,m = [int(x) for x in stdin.readline().rstrip().split()]
data = [stdin.readline().rstrip().split() for _ in range(n)]
data = [[int(i) for i in l] for l in data]
data.sort(key=lambda x:x[0])
cost=0
for d in data:
    for i in range(d[1]):
        cost+=d[0]
        m-=1
        if m==0:
            print(cost)
            sys.exit()


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

int main() {
	int N; cin >> N;
	vector<int> r(N);
	for (int i = 0; i < N; i++)
		cin >> r[i];
	sort(r.begin(), r.end());
	double ma = 0;
	for (; N >= 3; N--, r.erase(r.begin())) {
		do {
			double ub = DBL_MAX;
			for (int i = 0; i < N; i++)
				ub = min(ub, (double)r[i] * r[(i + 1) % N]);
			double lb = -ub;
			bool ok = false;
			for (int t = 0; t < 100; t++) {
				double mid = (lb + ub) / 2, sum = 0;
				for (int i = 0; i < N; i++)
					sum += acos(mid / r[i] / r[(i + 1) % N]);
				if (sum <= M_PI*2) {
					ub = mid;
					ok = true;
				}
				else lb = mid;
			}
			if (!ok) continue;
			double S = 0;
			for (int i = 0; i < N; i++)
				S += sqrt(pow(r[i] * r[(i + 1) % N], 2) - lb * lb);
			ma = max(ma, S);
		} while (next_permutation(r.begin(), r.end()));
	}
	printf("%.15f\n", ma / 2);
}

Measured memory_bytes: 3656
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF (1e9+1)
//#define INF (1LL<<59)

//0-index ??????????????°?????????(????????´??°or?????? , ????°????or?????§???or???) verified AOJ DSL_2,DSL_3
template<class T>
class segtree{
private:
	vector<T> dat;
	vector<T> lazy;
	int _size;  //the number of leaves
	T _init;
	
public:
	segtree(int __size=0 , T init=numeric_limits<T>::max() ):_size(__size), _init(init), dat(4*__size,init), lazy(4*__size,init){
		if(__size==0)return ;
		int x=1;
		while(x<_size)x*=2;
		_size = x;
	}
	

	void update(int s,int t, T x ,int num=1,int a=0,int b=-1){
		if(b==-1)b=_size-1; //I couldn't "int b=_size".
		if(b<s||t<a)return ;
		if(s<=a&&b<=t){
			lazy[num]+=x;	//addition
//			lazy[num]=x;	//initialize

//			dat[num] = min(dat[num],x);	//minimum
//			dat[num] = max(dat[num],x);	//maximum
			dat[num]+=x*(b-a+1);		//sum
			return ;
		}
		update(s,t,x,num*2+0,a,(a+b)/2);
		update(s,t,x,num*2+1,(a+b)/2+1,b);
//		dat[num] = min(min(dat[num*2],dat[num*2+1]),lazy[num]);	//minimum
//		dat[num] = max(max(dat[num*2],dat[num*2+1]),lazy[num]);	//maximum
		dat[num] = dat[num*2]+dat[num*2+1]+lazy[num]*(b-a+1);	//sum
	}

	
	// call find(s,t)
	T find(int s,int t,int num=1,int a=0,int b=-1){
		if(b==-1)b=_size-1; //I couldn't "int b=_size".
		if(b<s||t<a)return _init;
		if(s<=a&&b<=t)return dat[num];
		ll l = find(s,t,num*2,a,(a+b)/2);
		ll r = find(s,t,num*2+1,(a+b)/2+1,b);
//		return min(min(l,r),lazy[num]);		//minimum
//		return max(max(l,r),lazy[num]);		//maximum
		return l+r+lazy[num]*(min(b,t)-max(a,s)+1);		//sum
	}

	int size(){return _size;}
};



int main(){
	int n,q;
	cin>>n>>q;
	segtree<ll> st(n,0);
	
	rep(i,q){
		int p;
		cin>>p;
		if(!p){
			int s,t,x;
			cin>>s>>t>>x;
			s--,t--;
			st.update(s,t,x);
//			rep(i,n)cout<<st.find(i,i)<<" ";cout<<endl;
		}else{
			int s,t;
			cin>>s>>t;
			s--,t--;
			cout<<st.find(s,t)<<endl;
		}
	}
}

Measured memory_bytes: 9180
#include<bits/stdc++.h> 
#define ll long long
using namespace std;
const ll p = 1e9 + 7, N = 1e5 + 5;
ll x[N], f[N], ans = 0;
int n;
ll solve (ll x) {
	ll ans = 1;
	ll b = p - 2;
	while (b) {
		if (b & 1) ans = ans * x % p;
		x = x * x % p;
		b >>= 1;
	}
	return ans;
}
int main () {
	scanf ("%d", &n);
	for (int i=1;i<=n;i++) scanf ("%lld", &x[i]);
	f[0] = 0;
	for (int i=1;i<n;i++) {
		ll i_1 = solve (1LL * i);
		f[i] = (i_1 % p * (1 + f[i - 1])
		+ (i - 1) * i_1 % p * f[i - 1]) % p;
//		cout << f[i] << endl;
	}
	for (int i=2;i<=n;i++) {	
		ans = (ans + f[i - 1] * (x[i] - x[i - 1]) % p);
	}
	for (int i=1;i<n;i++) {
		ans = (ans * i) % p;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1792
/*
(1)for binary shift operator always use 'LL' 1LL<<63

*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set_pair tree<pair<ll,ll>, null_type,less<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update> 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define ordered_multiset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define Luv(...) [&] (auto &&u, auto &&v) { return __VA_ARGS__; }
  
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n;cin>>n;
	string s;cin>>s;
	if(s.size()>n){
		string s1=s.substr(0,n);
		s1+="...";
		cout<<s1;
	}
	else cout<<s;

	return 0;
} 

Measured memory_bytes: 3644
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W, L, R;

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

	string s;
	cin >> s;
	for (auto i : s) {
		if (i == '+')N++;
		else N--;
	}
	cout << N << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define FLASH ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) // rep(i, 1, 5) --> {1,2,3,4} // rep(i, 5, 1) --> {4,3,2,1} // rep(it, end(v), begin(v)) --> *it

using namespace std;

signed main()
{
    int n;
    cin >> n;
    vector<vector<int>> adj; // Outside main
    adj.resize(n); // Inside main
    map<pair<int, int>, int> mp;
    rep(i, 0, n-1)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--; // To have graph indexed from 0
        adj[a].push_back(b);
        adj[b].push_back(a);
        mp[{a,b}] = c;
        mp[{b,a}] = c;
    }
    // vector<vector<int>> adj;  // adjacency list representation
    // int n; // number of nodes
    int s = 0; // source vertex
    
    queue<int> q;
    vector<bool> used(n);
    vector<int> d(n); //, p(n); // For parent and distance
    vector<int> res(n);
    q.push(s);
    used[s] = true;
    // p[s] = -1;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : adj[v]) {
            if (!used[u]) {
                used[u] = true;
                q.push(u);
                d[u] = d[v] + mp[{u,v}];
                if (d[u]%2 == 0)
                    res[u] = 0;
                else 
                    res[u] = 1;
                // p[u] = v;
            }
        }
    }
    rep(i, 0, n)
        cout << res[i] << endl;
    return 0;
}

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

int main(){
	string S;
	cin >> S;
	
	for(int i=0; i<100; i++){
		if(S[2*i]=='L'){
			cout << "No" << endl;
			return 0;
		} else if(S[2*i+1]=='R'){
			 cout << "No" << endl;
			 return 0;
		}
	}
	
	cout << "Yes" << endl;
	return 0;
}

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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFの値が適切か確認する --- */
// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
const ll MOD = 1000000007;

int main() {
  int n;
  cin >> n;
  ll ans = 1;
  rep(i, n) ans = ans * (i + 1) % MOD;
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
int main() {
  string N;
  cin >> N;
  int digit = N.size();
  int head = N[0] - '0';
  bool can = true;
  for (int i = 1; i < digit; i++) {
    if (N[i] != '9') {
      can = false;
    }
  }
  if (!can) head--;
  cout << ((digit - 1) * 9) + head << endl;
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#define MAXN 10005
int N,K,digit[6],ans;
bool d[15];
int main()
{
	scanf("%d %d",&N,&K);
	int x,len=0;
	for(int i=1;i<=K;i++)
	{
		scanf("%d",&x);
		d[x]=1;
	}
	for(int i=N;i<=10000005;i++)
	{
		bool f=0;
		x=i;
		while(x)
		{
			if(d[x%10])
			{
				f=1;
				break;
			}
			x/=10;
		}
		if(!f)
		{
			printf("%d\n",i);
			return 0;
		}
	}
	/*x=N;
	while(x)
	{
		len++;
		digit[len]=x%10;
		x/=10;
	}
	bool f=0;
	for(int i=1;i<=len;i++)
	{
		
	}*/
}

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

#define mem(dp,a)           memset(dp,a,sizeof dp)
#define rep(i,a,b)          for(ll i=a;i<b;i++)
#define pb(x)               push_back(x)
#define mp(x,y)             make_pair(x,y)
#define xlr8                ios_base::sync_with_stdio(false);cin.tie(NULL)
#define F                   first
#define S                   second
#define all(c)              (c).begin(),(c).end()

int main()
{
    ll a,b,c,d;cin>>a>>b>>c>>d;
    ll cans=(b/c)-((a-1)/c);
    ll dans=(b/d)-((a-1)/d);
    ll g=__gcd(c,d);
    g=(c*d)/g;
    ll both=(b/g)-((a-1)/g);
    cout<<(b-a+1)-(cans+dans-both);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){
  string s;
  cin>>s;
  for(int i=0;i<(int)s.size()-1;i++){
    if(s[i]=='A'&&s[i+1]=='C'){
      cout<<"Yes"<<endl;
      return 0;
    }
  }
  cout<<"No"<<endl;
  return 0;
}


Measured memory_bytes: 256
program pass_
  implicit none
  integer(8), parameter :: md = 998244353_8
  character(2000) :: s
  integer :: n, m, i, j, a, r(0:2000) = 0, b(0:2000) = 0, x, y
  integer(8) :: dp(0:4000,0:4000) = 0_8
  dp(0,0) = 1_8
  read(*,*) s
  n = len_trim(s)
  m = 2*n
  do i = 1, n
    a = ichar(s(i:i))-48
    r(i) = r(i-1)+2-a
    b(i) = b(i-1)+a
  end do
  do i = 1, m
    x = r(min(i,n))
    y = b(min(i,n))
    do j = 0, i
      if (x < j .or. y < i-j) cycle
      dp(i,j) = dp(i-1,j)
      if (j /= 0) dp(i,j) = mod(dp(i,j)+dp(i-1,j-1),md)
    end do
  end do
  write(*,'(i0)') dp(m,r(n))
end program pass_

Measured memory_bytes: 123392
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (ll i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;

int main()
{
    ll N, K;
    cin >> N >> K;
    vector<vector<ll>> cnt(N, vector<ll>(2, -1));
    vector<ll> G(N);

    rep(i, N) {
        int A;
        cin >> A;
        A--;
        G[i] = A;
    }


    ll to = 0, p = 0;
    while (1) {
        bool flag = false;
        rep(i, 2) {
            if (cnt[to][i] == -1) {
                cnt[to][i] = p;
                flag = true;
                break;
            }
        }
        to = G[to];
        p++;
        if (!flag) break;
    }

    int ans = 0;
    rep(i, N) {
        rep(j, 2) {
            if (cnt[i][j] == K) {
                ans = i + 1;
                break;
            }
            else if (cnt[i][1] < K) {
                ll diff = cnt[i][1] - cnt[i][0];
                if (diff == 0 || cnt[i][0] == -1 || cnt[i][1] == -1) continue;
                if (K % diff == (cnt[i][0] % diff)) ans = i + 1;
            }
        }
    }

    cout << ans << endl;


    return 0;
}

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

const ll N=1e5+5;
ll n, k, h[N], dp[N];

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

    for(ll i=1; i<=n; i++){
        cin>>h[i];
        dp[i]=1e12;
    }
    dp[1]=0;
    for(ll i=2; i<=n; i++){
        for(ll w=1; w<=k && i-w>=1; w++){
            dp[i] = min (dp[i],dp[i-w]+abs(h[i]-h[i-w]));
        }
    }

    cout<<(ll)dp[n];

}


Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>

using namespace std;

#define rep(i,a,n) for(int i = a; n > i; i++)
#define REP(i,n) rep(i,0,n)
#define MP(a,b) make_pair(a,b)
#define ALL(a) (a).begin(),(a).end()
typedef pair<int,int> pii;
typedef long long ll;

signed main(){
	int n;
	scanf("%d%*c", &n);
	int isum = 0;
	vector<char> str(n);
	REP(i,n){
		scanf("%c", &str[i]);
if(str[i] == 'I')
	isum++;
	}
	ll Oad = 0,cans[3] = {};
	int cj = 0,ci = isum;
	REP(i,n){
		if(str[i] == 'O'){
			cans[0] += (ll)(cj+1)*ci;
			cans[1] += (ll)cj*ci;
			cans[2] += (ll)cj*(ci+1);
		}
		else if(str[i] == 'I'){
			ci--;
		}
		else{
			cj++;
		}
		Oad = max(Oad, (ll)cj*ci);

	}

	cans[1] += Oad;

	printf("%lld\n", max({cans[0], cans[1], cans[2]}));


	return 0;
}

Measured memory_bytes: 3332
#include"bits/stdc++.h"
using namespace std;
int a,b;
int main()
{
    cin>>a>>b;
    if(a>0)cout<<"Positive";
    else if(a==0||(a<0&&b>0))cout<<"Zero";
    else if((abs(b)-abs(a))%2!=0)cout<<"Positive";
    else cout<<"Negative";
    return 0;
}

Measured memory_bytes: 256
T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())
A1 *= T1
A2 *= T2
B1 *= T1
B2 *= T2
if A1 > B1:
    A1, B1 = B1, A1
    A2, B2 = B2, A2
C = B1 - A1
D = A2 - B2

if A1 + A2 == B1 + B2:
    print("infinity")
    exit()
elif C > D:
    print(0)
    exit()

q, r = divmod(C, (D - C))
if r == 0:
    print(2 * q)
else:
    print(2 * q + 1)

Measured memory_bytes: 9196
//2017-12-24
//miaomiao
//
#include <bits/stdc++.h>
using namespace std;

#define For(i, a, b) for(int i = (a); i <= (int)(b); ++i)
#define N (100000+5)

char s[N];
int a[N];

int main(){ 
	scanf("%s", s);
	int n = strlen(s); s[n] = '0';

	a[0] = s[0]^'0';
	For(i, 1, n) a[i] = s[i-1]^s[i];

	int ans = n;
	For(i, 0, n) if(a[i]) ans = min(ans, max(i, n-i));
	printf("%d\n", ans);

	return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <utility>
#include <algorithm>
#include <numeric>
#include <typeinfo>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <ctime>
 
using namespace std;
 
#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define debug(n) cout<<__FILE__<<","<<__LINE__<<": #"<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)
#define iter(c) __typeof((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();i++)
#define allof(c) (c).begin(),(c).end()
#define mp make_pair
 
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;
 
//int solve(int n,int s)
//{
//  if(n<=0 || 10<n)
//      return 0;
//  
//  vi c(n),k(10);
//  rep(i,n)
//      c[i]=i+1;
//  rep(i,10)
//      k[i]=i;
//  int res=0;
//  do{
//      if(inner_product(allof(c),k.begin(),0)==s)
//          res++;
//      reverse(n+allof(k));
//  }while(next_permutation(allof(k)));
//  return res;
//}
 
int memo[1<<10][331];
 
void gen_answer()
{
    rep(i,10)
        memo[1<<i][i]=1;
    repi(i,1,1<<10){
        int use=__builtin_popcount(i);
        rep(j,10){
            if(i&(1<<j))
                continue;
            int term=(use+1)*j;
            rep(k,331-term)
                memo[i|(1<<j)][k+term]+=memo[i][k];
        }
    }
}
 
int solve(int n,int s)
{
    if(n<=0 || 10<n)
        return 0;
    if(s<0 || 330<s)
        return 0;
     
    int res=0;
    rep(i,1<<10){
        if(__builtin_popcount(i)==n)
            res+=memo[i][s];
    }
    return res;
}
 
int main()
{
    gen_answer();
    for(int n,s;cin>>n>>s;)
        //cout<<solve(n,s)<<endl;
        //printf("%d %d: %d\n",n,s,solve(n,s));
        printf("%d\n",solve(n,s));
     
    return 0;
}


Measured memory_bytes: 4392