akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(int64)(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    s.pb('T');
    int32 x,y;
    cin >> x >> y;
    vector<vector<int32>> fCnt(2);
    vector<vector<vector<bool>>> reachable(2, vector<vector<bool>>(8000, vector<bool>(20000,false)));
    reachable[0][0][10000] = true;
    reachable[1][0][10000] = true;
    int32 cnt = 0;
    int32 direction = 0;
    REP(i, s.size()){
        if(s[i] == 'F'){
            cnt++;
        }else{
            if(fCnt[0].size() == 0 && fCnt[1].size() == 0 && direction == 0){
                fCnt[0].pb(0);
                reachable[0][0][10000] = false;
                reachable[0][0][10000+cnt] = true;
            }else{
                fCnt[direction].pb(cnt);
            }
            direction = 1 - direction;
            cnt = 0;
        }
    }
    REP(k,2){
        REP(i,fCnt[k].size()){
            FOR(j,0,20000-fCnt[k][i]){
                if(reachable[k][i][j]){
                    reachable[k][i+1][j+fCnt[k][i]] = true;
                }
            }
            FOR(j,fCnt[k][i], 20000){
                if(reachable[k][i][j]){
                    reachable[k][i+1][j - fCnt[k][i]] = true;
                }
            }
        }
    }
    Yes(reachable[0][fCnt[0].size()][10000+x] && reachable[1][fCnt[1].size()][10000+y]);
    return 0;
}

Measured memory_bytes: 61764
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif
#define int long long
const int MOD = 1e9 + 7;

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...));
}
template<class T, class V>
typename enable_if<is_class<T>::value == 0>::type fill(T &t, const V &v) {
    t = v;
}
template<class T, class V>
typename enable_if<is_class<T>::value != 0>::type fill(T &t, const V &v){
    for (auto &e : t) fill(e, v);
}
// auto v = make_vec<int>(h, w);
// fill(v, 0);

signed main(){

  int n, x; cin >> n >> x;
  vector<int> s(n);
  for(int i = 0; i < n; i++) cin >> s[i];
  sort(s.rbegin(),s.rend());

  auto dp = make_vec<int>(n+1, x+1);
  dp[0][x] = 1;
  for(int i = 0; i < n; i++){
    for(int j = 0; j <= x; j++){
      dp[i+1][j % s[i]] += dp[i][j]; dp[i+1][j] %= MOD;
      dp[i+1][j] += dp[i][j] * (n - i - 1); dp[i+1][j] %= MOD;
    }
  }

  int ans = 0;
  for(int i = 0; i <= x; i++){
    ans += i * dp[n][i]; ans %= MOD;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 158592
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef long  l;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
const double PI=3.141592653589;
const int INF=1000000007;
const ll LMAX=1000000000000001;
ll gcd(ll a,ll b){if(a<b)swap(a,b);while((a%b)!=0){a=b;b=a%b;}return b;}
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};


int main(){
  int n; cin>>n;
  string s; cin>>s;
  int ma=0;
  int now=0;
  rep(i,n){
    if(s[i]=='I')
    now++;
    else
    now--;
    ma=max(ma,now);
  }
  cout<<ma<<endl;
  return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
N, W = list(map(int, input().split()))
WV = []
for _ in range(N):
    WV.append(list(map(int, input().split())))

DP = [[0] * (W+1)]
for n in range(N):
    DP.append([0]*(W+1))


for n in range(N):
    for w in range(W+1):
        if w < WV[n][0]:
            DP[n+1][w] = DP[n][w]
        else:
            DP[n+1][w] = max(DP[n][w-WV[n][0]]+WV[n][1], DP[n][w])

print(DP[N][W])


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

int main() {
    int h, w;
    while (1) {
        cin >> h >> w;
        if (h == 0 && w == 0) break;

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cout << "#";
            }
            cout << endl;
        }
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 3076
#include<bits/stdc++.h>
#define loop(i, a, b) for(lli i = a;i <= b; ++i)
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define lli long long int 
using namespace std;


signed main(){
    fast;
    int n,k;
    cin>>n>>k;
    int x[n];
    loop(i,0,n-1)
        cin>>x[i];
    bool a[k+1];
    loop(i,0,k){
        bool ans = false;
        loop(j,0,n-1){
            
            if(i - x[j] >= 0){
                ans = ans || (a[i - x[j]] == 0);
            }
        }
        a[i] = ans;
    }
    cout<<(a[k] ? "First":"Second")<<endl;
    return 0;
        
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
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; }
#define pb push_back
#define mp make_pair
#define F .first
#define S .second 
using ll=long long;
using ld=long double;
const ll INF = 1LL<<60;
const ll mod=1e9+7;
using namespace std;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }


vector<ll> l;

int main(){
    ll n,q,t=0;
    cin>>n;
    rep(i,0,2*n){cin>>q;l.pb(q);}
    sort(l.begin(),l.end());
    rep(i,1,n+1)t+=l[2*i-2];
    cout<<t;
}
    

Measured memory_bytes: 256
'use strict';
(function(stdin) {
  //declare function

  //declare variable
  function search(array) {
    return allCards.filter(function(card) {
      return array.indexOf(card) === -1;
    });
  }
  var inputs = stdin.toString().trim().split('\n');
  var line = [].concat(inputs);
  var allCards = ['S', 'H', 'C', 'D'].map(function(v) {
    var newArray = [];
    for (var i = 0; i < 13; i++) {
      newArray.push([v, i + 1].join(' '));
    }
    return newArray;
  }).reduce(function(a, b) {
    return a.concat(b);
  });
  //main

  //display
  if (inputs[0] < 52) {
    console.log(search(line).join('\n'));
  }
})(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 15596
package main

import "fmt"

func main() {
	var N, T int
	fmt.Scan(&N, &T)

	ts := make([]int, N)
	for i := range ts {
		fmt.Scan(&ts[i])
	}

	var ans int
	for i := 0; i < N-1; i++ {
		diff := ts[i+1] - ts[i]

		if diff >= T {
			ans += T
		} else {
			ans += diff
		}
	}
	fmt.Println(ans + T)
}

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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) ((a+b-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/2

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;

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> void YesNo(T a) {cout<<(a?"Yes":"No")<<endl;}
template<class T> void YESNO(T a) {cout<<(a?"YES":"NO")<<endl;}
void vin(Vi &v){REP(i,0,(v).size()) cin>>v[i];}
void vin(Vi &v,Vi &v2){REP(i,0,(v).size()) cin>>v[i]>>v2[i];}
void vout(Vi &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());}
int ctoi(char c){if(c>='0'&&c<='9'){return c-'0';}return 0;}
void accum(Vi &v){REP(i,1,(v).size()) v[i]+=v[i-1];}
bool comp(Pii a,Pii b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    Vi a(m),b(m);
    VPii c(m);
    REP(i,0,m){
        cin>>a[i]>>b[i];
        c[i]=mp(a[i],b[i]);
    }

    sort(ALL(c),comp);
//    REP(i,0,m) cout<<c[i].first<<" "<<c[i].second<<endl;
    int ans=0,now=-1;
    REP(i,0,m){
        if(now<=c[i].first){
            ans++;
            now=c[i].second;
        }
    }
    cout<<ans<<endl;


    return 0;
}


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

using namespace std;

#define all(x) x.begin(), x.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define reps(i, m, n) for (int i = m; i <= n; ++i)

using i64 = long long;
using pii = pair<i64, i64>;

template<class A, class B>inline bool chmax(A &a, const B &b){return b > a ? a = b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b < a ? a = b,1 : 0;}

constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;

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

  int n;
  cin >> n;

  int sum = 0;
  rep(i, n) {
    int a;
    cin >> a;
    --a;
    sum += a;
  }

  cout << sum << "\n";

  return 0;
}

Measured memory_bytes: 256
import itertools
import math
import fractions
import functools
import copy
from collections import deque
from functools import reduce
from decimal import Decimal

n = int(input())
prime = {}

num = n
i = 2
while True:
    if i * i > n:
        if(num > 1):
            prime[num] = 1
        break
    while num%i == 0:
        prime[i] = prime.get(i, 0) + 1
        num = num//i
    i += 1

count = 0
for val in prime.values():
    use = 1
    while True:
        if(val < use):
            break
        val -= use
        use += 1
        count+=1
print(count)


Measured memory_bytes: 77512
import java.util.Scanner;

class Main {

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

    void compute() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long[] a = new long[N];
        for (int i = 0; i < N; i++) {
            a[i] = sc.nextLong();
        }
        long sum = 0;
        for (long ai : a) {
            sum += ai;
        }
        long cs = a[0];
        long minDifference = 2 * (long) Math.pow(10, 14);
        if (N == 2) {
            minDifference = Math.abs(a[0] - a[1]);
        }
        for (int i = 1; i < N - 1; i++) {
            long ai = a[i];
            cs += ai;
            long cd = Math.abs(sum - 2 * cs);
            minDifference = minDifference < cd ? minDifference : cd;
        }
        System.out.println(minDifference);
    }
}


Measured memory_bytes: 75076
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int k,s,cnt=0;
    cin>>k>>s;
    for(int i=0;i<=k;i++)
    {
        for(int j=0;j<=k;j++)
        {
            int p=i+j;
            if((s-p)>=0 && (s-p)<=k)
                cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 384
#include<stdio.h>
int main(){
    int a,b,d,r;
    double f;
    scanf("%d %d",&a,&b);
    d=a/b;
    r=a%b;
    f=(double)a/b;

    printf("%d %d %f\n",d,r,f);
    return 0;
}

Measured memory_bytes: 636
#include<bits/stdc++.h>
using namespace std;
double X[200200];
int main()
{
  int N,K;
  cin>>N>>K;
  for(int i=0;i<N;i++)
  {
    cin>>X[i];
    X[i]+=1;
    X[i]/=2;
  }
  double Sum=0,Ans=0;
  for(int i=0;i<K;i++)
    Sum+=X[i];
  Ans=Sum;
  for(int i=K;i<N;i++)
  {
    Sum+=X[i];
    Sum-=X[i-K];
    Ans=max(Ans,Sum);
  }
  printf("%.6lf",Ans);
  return 0;
}

Measured memory_bytes: 1792
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    h,w = LI()
    s = SR(h)
    ans = 1
    for y in range(h):
        for x in range(w):
            if s[y][x] == "B":
                for y_ in range(h):
                    for x_ in range(w):
                        if s[y_][x_] == "B":
                            ans = max(ans, abs(y-y_)+abs(x-x_))
    print(ans)
    return

#B
def B():
    n = I()

    return

#C
def C():
    n = I()

    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#G
def G():
    n = I()

    return

#H
def H():
    n = I()

    return

#I
def I_():
    n = I()

    return

#J
def J():
    n = I()

    return

#Solve
if __name__ == "__main__":
    A()



Measured memory_bytes: 8244
use proconio::input;

fn main() {
    input! {
        x: [i32; 5]
    }

    solve(&x);
}

fn solve(x: &[i32]) {
    for i in 0..x.len() {
        if x[i] == 0 {
            println!("{}", i + 1);
            return;
        }
    }
}


Measured memory_bytes: 2092
#include<stdio.h>
int main(void)
{
	long long int n = 0,ans = 0,count = 1;
	scanf("%lld", &n);
	
	if (n % 2 != 0) {
		printf("0\n");
	}
	else {
		int under = 10;
		while (1) {
			if (under * count > n) {
				break;
			}
			ans += n / (under * count);
			count *= 5;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Measured memory_bytes: 128
#include <string.h>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

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

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

    sort(d.begin(), d.end());
    sort(t.begin(), t.end());

    int j = 0;
    int i;
    for (i = 0; i < m && j < n; i++) {
        if (t[i] == d[j]) {
            j++;
        } else if (t[i] > d[j]) {
            while (t[i] != d[j] && j < n) {
                if (t[i] < d[j]) {
                    cout << "NO";
                    return 0;
                }
                j++;
            }
            j++;
        } else if (t[i] < d[j]) {
            cout << "NO" << endl;
            return 0;
        }
    }

    if (i == m && j <= n) {
        cout << "YES" << endl;
    }
}

Measured memory_bytes: 1792
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
int N;

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

  cin >> N;
  
  cout << (N-1)/2 << "\n";
  return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;

#define REP(i, n) for(ll i=0;i<ll(n); i++)

int main(){
    string N;
    cin >> N;
    int i;
    for(i=0;i<N.length();i++){if(N[i] == '7'){cout << "Yes" << endl;return 0;}}

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


Measured memory_bytes: 3100
import os
import sys

import numpy as np
from numpy.linalg import matrix_power

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

sys.setrecursionlimit(2147483647)
INF = float("inf")

L, A, B, M = list(map(int, sys.stdin.readline().split()))
MOD = M


class ModInt:
    def __init__(self, value):
        self.value = value % MOD

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.value + other.value)
        else:
            return ModInt(self.value + other)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.value * other.value)
        else:
            return ModInt(self.value * other)

    def __repr__(self):
        return str(self.value)


size = 0
# 全部つなげたのを X とすると、
# [今の X, 次に加算する数, 公差]
vec = [ModInt(0), ModInt(A), ModInt(B)]
# 加算する数の桁数
digits = 1
while size < L:
    # 桁数が digits である要素の数
    # digits 以下の要素の数の合計から今までに加算した数を引く
    cnt = max(0, (10 ** digits - 1 - A) // B - size + 1)
    cnt = min(cnt, L - size)

    mat = np.array([
        [ModInt(pow(10, digits, MOD)), ModInt(0), ModInt(0)],
        [ModInt(1), ModInt(1), ModInt(0)],
        [ModInt(0), ModInt(1), ModInt(1)],
    ])
    if cnt > 0:
        vec = np.dot(vec, matrix_power(mat, cnt))
    digits += 1
    size += cnt
print(vec[0])


Measured memory_bytes: 12472
#include<stdio.h>
int main(void){
  char a[3];
  scanf("%s",a);
    if((a[0]=='A'&&a[1]=='A'&&a[2]=='A')||(a[0]=='B'&&a[1]=='B'&&a[2]=='B')){
      printf("No");
      return 0;
    }
       printf("Yes");
       return 0;
       }
       

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

int main(void){
    int A, B, K;
    cin >> A >> B >> K;
    int L[2*K];
    int cnt = 1;
    for (int num = A; num<=B+K; num++)
    {
        if (cnt <= K)
        {
            L[cnt-1] = num;
            cnt++;
        }
        else
        {
            break;
        }
    }
    int up_cnt = 1;
    if (B - A <= K)
    {
        for(int num = A; num <= B; num++)
        {
            cout << num << endl;
        }
    }
    
    else
    {
        for (int num = B; num>=B-K; num--)
        {
            if (up_cnt <= K && num > 0)
            {
                L[cnt+up_cnt-2] = num;
                cnt++;
            }
            else
            {
                break;
            }
        }
        sort(L, L+2*K);
        int del_cnt = 0;
        for (int i = 0; i < 2*K-1; i++)
        {
            if (L[i] == L[i+1])
            {
                L[i+1] = 900000000;
                del_cnt++;
            }
        }
        sort(L, L+2*K);
        for(int i = 0; i<2*K - del_cnt; i++)
        {
            cout << L[i] << endl;
        }
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
int main(void){
  double n;
  scanf("%lf",&n);
  int i;
  for(i=1;;i++){
    if(i*i>n){
      printf("%d",(i-1)*(i-1));
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cassert>
#include <exception>
#include <numeric>
using namespace std;
typedef long long ll;
typedef string str;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef vector<str> vs;
typedef vector<Pll> vp;
typedef vector<bool> vb;
#define rep(i, a, n) for (ll i = (a); i < (n); ++i)
#define rrep(i, a, n) for (ll i = (a); i > (n); --i)
#define erep(i, a, n) for (ll i = (a); i <= (n); ++i)
#define rerep(i, a, n) for (ll i = (a); i >= (n); --i)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define mp make_pair
#define sz(x) ((int)x.size())
#define vec_max(V) *max_element(all(V))
#define vec_min(V) *min_element(all(V))
#define vec_sum(V) accumulate(all(V), 0LL)
#define print(X) cout << (X) << "\n"
#define _ << " " <<
#define Yes print("Yes")
#define No print("No")
static const int INF = 1e+9+7;

int main(){
  ll N,M,C;
  cin >> N >> M >> C;
  ll B[M];
  rep(i,0,M) cin >> B[i];
  ll ans = 0;
  rep(i,0,N){
    ll tmp = 0;
    rep(j,0,M){
      ll a;
      cin >> a;
      tmp += a*B[j];
    }
    if(tmp+C > 0) ans++;
  }

  print(ans);

 return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
    long long N,count;count =0;
    cin >> N;
    long long M = 100;
    while(1){
        if(M >= N)break;
        M = M / 100 + M;
        count++;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 3636
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::io::{BufWriter, Write};

// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn solve() {
    input!(
        n: usize,
        k: usize,
    );

    let mo = 1000000007;

    let mut comb = Vec::new();
    comb.resize(2*n+1, Vec::new());
    for i in 0..2*n+1 {
        comb[i].resize(2*n+1, 0);
    }


    comb[0][0] = 1;

    for i in 1..2*n+1 {
        comb[i][0] = 1;
        comb[i][i] = 1;
        for j in 1..i {
            comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
            comb[i][j] = comb[i][j] % mo;
        }
    }

    let a = k;
    let b = n-k;

    for i in 1..k+1 {

        if b+1 < i {
            println!("{}", 0);
            continue;
        }

        let t1 = comb[a-1][i-1] as i64;
        let t2 = comb[b+1][i] as i64;

        println!("{}", t1 * t2 % mo);
    }
}

fn main() {
    let stack_size = 1 << 28;
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


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

memo = []
flag = 1
for i in range(n):
    w = input()
    start = w[0]
    if i==0: end = w[len(w)-1]; memo.append(w); continue
    if start == end and not w in memo: end = w[len(w)-1]; memo.append(w)
    else: flag = 0; break

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

Measured memory_bytes: 3060
#include <bits/stdc++.h>
//---------------------------
using namespace std;
//---------------------------
#define REP(i,n) for(int i = 0; i < (n); i++)
#define P(x) cout << (x) << "\n"

#define MOD 1e9+7
#define PI acos(-1.0)
#define ll long long
#define INF 1000000001

int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
//---------------------------

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

  // ifstream in("input.txt");
  // cin.rdbuf(in.rdbuf());

  int N,Z,W;cin>>N>>Z>>W;
  int a[2001];
  for(int i=1;i<=N;i++){
    cin>>a[i];
  }
  // n=3を考えると、
  // max(|a3-a2|, min(|a3-a2|, |a3-a1|))
  // になるので、n一般で、xはすべて取るか一個残すかしかない。
  if(N==1){
    P(abs(a[1]-W));
    return 0;
  }
  P(max(abs(a[N]-W), abs(a[N]-a[N-1])));
  return 0;
}


Measured memory_bytes: 256
# include <cstdio>
# include <iostream>
 
using namespace std;
 
int h,w,f=1,j,x,lasx,lasy;
int g[502][502];
int H,a[250005],b[250005],c[250005],d[250005];
 
int main()
{
	scanf("%d%d",&h,&w);
	for (int i=1;i<=h;++i)
		for (int j=1;j<=w;++j)
			scanf("%d",&g[i][j]),g[i][j]%=2;
	for (int i=1;i<=h;++i)
	{
		if(i%2) j=1; else j=w;
		while (1<=j&&j<=w)
		{
			if(x)
			{
				a[++H]=lasx,b[H]=lasy,c[H]=i,d[H]=j;
				if(g[i][j]) x=0;
			}
			else if(g[i][j]) x=1; 
			lasx=i;
			lasy=j;
			j+=f;
		}
		f=-f;
	}
	printf("%d\n",H);
	for (int i=1;i<=H;++i)
		printf("%d %d %d %d\n",a[i],b[i],c[i],d[i]);
	return 0;
}

Measured memory_bytes: 6016
from collections import defaultdict

n,m = map(int,input().split())

al = list(map(int,input().split()))

modd = defaultdict(int)

s = 0
for a in al:
    s += a
    s %= m 
    modd[s] += 1
    
ans = 0
for i in modd.values():
    ans += i * (i-1) // 2

ans += modd[0]

print(ans)

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

//隣接行列
int d[101][101];

int main(){
  
  int u,k,v,n;
  cin >> n;
  //入力
  for(int i = 0; i < n; i++){
    cin >> u >> k;
    for(int j = 0; j < k; j++){
      cin >> v;
      d[u][v] = 1;//隣接しているところを1にする
    }
  }
  //出力
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      //最後に空白が入らないようにする
      if(j == n){
	cout << d[i][j];
      }else{
	cout << d[i][j] << " ";
      }
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 1200
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        AFiftyFifty solver = new AFiftyFifty();
        solver.solve(1, in, out);
        out.close();
    }

    static class AFiftyFifty {
        PrintWriter out;
        InputReader in;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            this.out = out;
            this.in = in;
            String st = n();
            int[] freq = new int[26];
            int i = 0;
            for (i = 0; i < st.length(); i++)
                freq[st.charAt(i) - 'A']++;
            int lol = 1;
            for (i = 0; i < 26; i++) {
                lol *= Math.max(1, freq[i]);
                if (freq[i] == 4)
                    lol = 0;
            }
            pn(lol == 4 ? "Yes" : "No");
        }

        String n() {
            return in.next();
        }

        void pn(String zx) {
            out.println(zx);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new UnknownError();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new UnknownError();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public String next() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuffer res = new StringBuffer();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));

            return res.toString();
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

    }
}



Measured memory_bytes: 23380
#include <algorithm>
#include <vector>
#include <cmath>
#include <tuple>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <queue>
#include <numeric>
#include <iostream>

using namespace std;


int main() {

    int N;
    cin >> N;

    int m = 0;
    int sum = 0;
    for (int i = 0; i < N; i++) {
        int l;
        cin >> l;
        m = max(m, l);
        sum += l;
    }

    sum -= m;

    if (sum > m) {
        cout << "Yes" << "\n";
    } else {
        cout << "No" << "\n";
    }


    return 0;
}

Measured memory_bytes: 256
N = int(input())
D = list(map(int,input().split()))
from collections import Counter
 
mod = 998244353
c = Counter(D)
max_D = max(D)
if c[0]!=1:
  print(0)
  
elif D[0]!=0:
  print(0)
  
elif max_D<=1:
  print(1)
  
else:
  answer=1
  for i in range(2,max_D+1):
    c_i2 = c[i]
    c_i1=c[i-1]
    answer = ((answer % mod) * ((c_i1**c_i2) % mod)) % mod
    
  print(answer%998244353)

Measured memory_bytes: 19808
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<tuple>
#include<list>
#include<unordered_map>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define INF (1 << 30) - 1
#define LLINF (1LL << 61) - 1
// #define int ll
using namespace std;
const int MOD = 1000000007;
const int MAX = 510000;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,a[100010],cnt=0;
    bool flag=false;
    cin>>n;
    rep(i,n){
        cin>>a[i];
        if(a[i]%2==1){
            flag=true;
        }
    }
    if(flag){
        cout<<"first"<<endl;
    } else{
        cout<<"second"<<endl;
    }
    return 0;
}

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

int main()
{
	int i;
	long long A[5];

   #ifndef ONLINE_JUDGE
   freopen("input.txt","r",stdin);
   freopen("output.txt","w",stdout);
   #endif 

   for(i=0;i<5;i++)
   	cin>>A[i];

   for(i=0;i<5;i++)
   { if(A[i]==0)
      {  cout<<i+1;
        break;
      }  
    } 
 }      

Measured memory_bytes: 3632
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();

    Set<String> set = new HashSet<>();

    for(int i = 0; i < n; i++) {
      String s = sc.next();

      set.add(s);
    }
    sc.close();

    System.out.println(set.size());
  }
}


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

long long int ans;
long long int w, h;

int dx[4] = { -1,  0,  1,  0 };
int dy[4] = {  0, -1,  0,  1 };

void kansu( long long int m[30][30], long long int x, long long int y, long long int k ) {

  if ( k == 10 ) return;
  k++;

  for ( long long int i = 0; i < 4; i++ ) {

    long long int mx = x + dx[i];
    long long int my = y + dy[i];

    if ( mx < 0 || mx >= w || my < 0 || my >= h || m[mx][my] == 1 ) continue;

    while( true ) {

      if ( mx < 0 || mx >= w || my < 0 || my >= h ) break;
      if ( m[mx][my] == 3 ) {
	ans = min( ans, k );
	break;
      }else if ( m[mx][my] == 1 ) {
	m[mx][my] = 0;
	kansu( m, mx - dx[i], my - dy[i], k );
	m[mx][my] = 1;
	break;
      }

      mx += dx[i];
      my += dy[i];

    }

  }

  return;

}

int main() {

  while( true ) {

    cin >> w >> h;
    if ( w == 0 ) break;

    long long int x, y;
    long long int m[30][30];

    for ( long long int i = 0; i < h; i++ ) {
      for ( long long int j = 0; j < w; j++ ) {
	cin >> m[j][i];
	if ( m[j][i] == 2 ) {
	  m[j][i] = 0;
	  x = j;
	  y = i;
	}
      }
    }

    ans = 20;
    kansu( m, x, y, 0 );

    if ( ans <= 10 ) {
      cout << ans << endl;
    }else {
      cout << -1 << endl;
    }

  }

  return 0;

}

Measured memory_bytes: 1164
N = int(input())
p_list = list(map(int, input().split()))
slist = sorted(p_list)
if p_list == sorted(p_list):
    print('YES')
else:
    list1 = [1 if p_list[i] == slist[i] else 0 for i in range(N)]
    if list1.count(0) == 2:
        print('YES')
    else:
        print('NO')

Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
using namespace std;
int main(){
long long int A, B, C, D ,E ,F, N,M;
long long V[10000000] = {};
long long G[10000000] = {};
string S,Sa,Sb,Sc;
bool ans = true;
  C = 0;
cin >> A >> B;
if((A + 1) / 2 >= B)cout << "YES" << endl;
else cout << "NO" << endl;

return 0; 
}


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

int main()
{
  long long N, W;
  cin >> N >> W;
  vector<long long> v1, v2, v3, v4;
  long long w, v;
  cin >> w >> v;
  long long w1 = w;
  v1.push_back(v);
  for(long long i = 1; i < N; i++){
    cin >> w >> v;
    if(w == w1){
      v1.push_back(v);
    }else if(w == w1+1){
      v2.push_back(v);
    }else if(w == w1+2){
      v3.push_back(v);
    }else{
      v4.push_back(v);
    }
  }
  sort(begin(v1),end(v1),greater<long long>());
  sort(begin(v2),end(v2),greater<long long>());
  sort(begin(v3),end(v3),greater<long long>());
  sort(begin(v4),end(v4),greater<long long>());
  long long ans = 0;
  for(long long i = 0; i <= (long long)v1.size(); i++){
    for(long long j = 0; j <= (long long)v2.size(); j++){
      for(long long k = 0; k <= (long long)v3.size(); k++){
        for(long long l = 0; l <= (long long)v4.size(); l++){
          if(i*w1+j*(w1+1)+k*(w1+2)+l*(w1+3) > W) continue;
          long long x = accumulate(begin(v1),begin(v1)+i,0LL)+accumulate(begin(v2),begin(v2)+j,0LL)+accumulate(begin(v3),begin(v3)+k,0LL)+accumulate(begin(v4),begin(v4)+l,0LL);
          ans = max(ans,x);
        }
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
use std::io::prelude::BufRead;
use std::io::StdinLock;

pub fn read_line(locked_stdin: &mut StdinLock) -> std::io::Result<String> {
    let mut buf = String::new();
    locked_stdin.read_line(&mut buf).map(|_| buf)
}

pub fn read_to_vec<T: std::str::FromStr>(locked_stdin: &mut StdinLock) -> Vec<T> {
    read_line(locked_stdin).unwrap()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn main() {
    let (n, x): (usize, usize);
    let a_vec: Vec<usize>;

    {
        let stdin = std::io::stdin();
        let mut lkin = stdin.lock();
        let mut input = read_to_vec(&mut lkin).into_iter();
        n = input.next().unwrap();
        x = input.next().unwrap();
        a_vec = read_to_vec(&mut lkin);
    }

    let mut ans = Vec::new();
    let mut diff = a_vec[0].saturating_sub(x);

    ans.push(diff);

    for i in 1..n {
        diff = (a_vec[i-1] - diff + a_vec[i]).saturating_sub(x);
        let &last = ans.last().unwrap();
        ans.push(last + diff);
    }

    println!("{}", ans.last().unwrap());
}


Measured memory_bytes: 8444
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]

for i in range(N):
    if A[i][i] != 0:
        print(-1)
        exit()
import copy
ca = copy.deepcopy(A)

for k in range(N):
    for i in range(N):
        for j in range(N):
            ca[i][j] = min(ca[i][j],ca[i][k] + ca[k][j])


## 各頂点間に最短距離通りの辺を引いた時に最短距離が更新されていたらそれはどうやったって構築できない
for i in range(N):
    for j in range(N):
        if A[i][j] != ca[i][j]:
            print(-1)
            exit()

ans = 0
for i in range(N):
    for j in range(N):
        need = True
        for k in range(N):
            if i != k and j != k and ca[i][k] + ca[k][j] == ca[i][j]: # ijのパスが無くても制約を満たせるならijのパスは消して良い
                need = False
        if need:
            ans += ca[i][j]
ans = ans//2 # 各パスを2回ずつ数えている
print(ans)

Measured memory_bytes: 56924
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>

#define STARTUP {(cin.tie(0));\
 (ios::sync_with_stdio(false));}

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).size()
#define MAX(list) std::max(list)
#define MIN(list) std::min(list)
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())
#define CINVEC(vec) const int size = (vec).size(); REP(i,size) cin>>(vec)[i];

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

template <typename T1, typename T2>
std::istream& operator>>(std::istream& is, std::pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

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

using ll = long long;
using namespace std;
ll mod = 1'000'000'007;

const int INF = 1'050'000'000;

int main() {
    STARTUP;

    string a, b;
    cin >> a >> b;
    if (a.length() == b.length()) {
        if (a > b)cout << "GREATER" << endl;
        else if (a < b)cout << "LESS" << endl;
        else cout << "EQUAL" << endl;
    }
    else {
        if(a.length()>b.length())cout << "GREATER" << endl;
        else cout << "LESS" << endl;
    }
    return 0;
}

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

long long m = 1e9 + 7;

long long modPow(long long a, long long n, long long p) {
  if (n == 1) return a % p;
  if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
  long long t = modPow(a, n / 2, p);
  return (t * t) % p;
}

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

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

    long long n, a, b;
    cin >> n >> a >> b;

    long long ans = modPow(2, n, m) % m;
    
    // a
    long long hoge = 0;
    long long tmpUp = 1;
    for(long long i = n; i > max(1LL, n - a); i--){
        tmpUp = ((tmpUp % m) * (i % m)) % m;
    }
    long long tmpDo = 1;
    for(long long i = 1; i <= a; i++){
        tmpDo = ((tmpDo % m) * (i % m)) % m;
    }

    hoge = ((hoge % m) + (((tmpUp % m) * modinv(tmpDo, m)) % m)) % m;


    // b
    tmpUp = 1;
    for(long long i = n; i > max(1LL, n - b); i--){
        tmpUp = ((tmpUp % m) * (i % m)) % m;
    }
    tmpDo = 1;
    for(long long i = 1; i <= b; i++){
        tmpDo = ((tmpDo % m) * (i % m)) % m;
    }

    hoge = ((hoge % m) + (((tmpUp % m) * modinv(tmpDo, m)) % m)) % m;

    ans = ((ans % m ) - (hoge % m)) % m;
    ans = (ans % m - 1) % m;
    if (ans < 0) ans += m;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n, a, b; cin >> n >> a >> b;
  cout << min(a, b) << ' ' << max(0, a + b - n) << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

lli dp[100100];
map<lli,vector<lli>> x;

lli dfs(lli p){
	if(dp[p]>0)return dp[p];

	REP(i,0,x[p].size()){
		lli next = x[p][i];
		dp[p] = max(dp[p],dfs(next)+1);
	}
	return dp[p];
}

signed main(){

	lli n,m;
	cin>>n>>m;
	REP(i,0,100100)dp[i]=0;

	REP(i,0,m){
		lli a,b;
		cin>>a>>b;
		a--,b--;
		x[a].push_back(b);
	}

	lli ans=0;
	REP(i,0,n){
		ans = max(ans,dfs(i));
	}

	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 15360
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <cstdio>
using namespace std;

int main() {
  int n;
  cin >> n;
  priority_queue<double> q;
  vector<double> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i];
    q.push(-v[i]);
  }
  for (int i = 0; i < n - 1; i++) {
    double a = -q.top();
    q.pop();
    double b = -q.top();
    q.pop();
    q.push(-(a + b)/2);
  }
  double ans = -q.top();
  printf("%.16lf\n", ans);
  return 0;
}

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

#define N 80

int n; 
long a[N+1];

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

    long money = 1000;
    long stock = 0;
    for (int i = 1; i < n; i++){
        long diff = a[i+1] - a[i];
        if ( diff > 0 ){
            long stockTmp = money / a[i];
            money -= stockTmp*a[i]; 
            stock += stockTmp;
        }
        else if ( diff < 0 ){
            money += stock*a[i];
            stock = 0;
        }
    }
    money += stock*a[n];

    cout << money << endl;

    return 0;
}


Measured memory_bytes: 3620
from fractions import gcd
import sys
sys.setrecursionlimit(4100000)

def os(): return input()
def oi(): return int(input())
def oli(): return map(int, input().split())
def olai(): return list(map(int, input().split()))
def olas(): return list(input().split())
def mlai(L): return [int(input()) for _ in range(L)]
def mlas(L): return [input() for _ in range(L)]

def ar(a, b, c=-1, d=-1, INIT=0):
    if(c==-1): return [[INIT]*b for _ in range(a)]
    if(d==-1): return [[[INIT]*c for _ in range(b)] for __ in range(a)]
    return [[[[INIT]*d for _ in range(c)] for __ in range(b)] for ___ in range(a)]

def lcm(a, b): return (a*b)//gcd(a, b)

#MOD
P = 10**9 + 7
N = 200001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2, N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b):
    if a<b or b < 0: return 0 # error
    return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P




class T:
    num = 1
    child = 0

    def __init__(self, a, b):
        self.num = a
        self.child = b

def step(x):
    return T(x.num, x.child+1)
def merge(x, y):
    if(x.num==-1): return y
    if(y.num==-1): return x
    return T((x.num*y.num*comb(x.child+y.child, x.child))%P, x.child+y.child)

G = [[] for _ in range(200001)]
down_data = [T(-1, -1) for _ in range(200001)]
dat = [T(-1, -1) for _ in range(200001)]

def dfs(now, parent):
    cnt = 0
    for to in G[now]:
        if(to==parent): continue
        cnt += 1
        dfs(to, now)
        down_data[now] = merge(down_data[now], step(down_data[to]))
    if(cnt==0): down_data[now] = T(1, 0)

def dfs_rev(now, parent, rev):
    left = []
    right = []
    cnt = 0
    for to in G[now]:
        if(to==parent): continue
        if(len(left)==0): left.append(step(down_data[to]))
        else: left.append(merge(left[cnt-1], step(down_data[to])))
        cnt += 1
    cnt = 0
    for to in reversed(G[now]):
        if(to==parent): continue
        if(len(right)==0): right.append(step(down_data[to]))
        else: right.append(merge(right[cnt-1], step(down_data[to])))
        cnt += 1
    cnt = 0
    dat[now] = merge(rev, down_data[now])
    for to in G[now]:
        if(to==parent): continue
        x = T(-1, -1) if cnt==0 else left[cnt-1]
        y = T(-1, -1) if cnt==len(right)-1 else right[len(right)-2-cnt]
        dfs_rev(to, now, step(merge(rev, merge(x, y))))
        cnt += 1

def main():
    n = oi()
    for i in range(n-1):
        a, b = oli()
        G[a].append(b)
        G[b].append(a)
    root = -1
    for i in range(1, n+1):
        if(len(G[i]) == 1):
            root = i
            break
    dfs(root, -1)
    dfs_rev(root, -1, T(1, 0))
    for i in range(1, n+1):
        print(dat[i].num)

if __name__ == "__main__": main()


Measured memory_bytes: 175956
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

void digit(long long& x,int& digit_num){
  for (int i = 0; i <= 15; ++i) {
    long long a = (long long)(26 * (pow(26, i)) / 25);
    long long b = (long long)(26 * (pow(26, i + 1)) / 25);
    if (a <= x && x < b) {
      x = x-a;
      digit_num = i+1;
    }
  }
}

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

  vector<char> rlt;

  int digit_num;
  digit(N,digit_num);
  //cout << N << " " << digit_num << endl;
  int i = 1;
  while(true){
    if(digit_num>=2){
      char c = 'a';
      long long mod = pow(26,digit_num-1);
      c += N/mod;
      rlt.push_back(c);
      //cout << c << " " << N/mod << endl;
      N -= N/mod*mod;
      i++;
    }

    if(digit_num==1) break;
    digit_num -= 1;
  }
  rlt.push_back('a'+N%26);

  for (int i = 0; i < rlt.size(); ++i) {
    cout << rlt[i];
  }
  cout << "\n";



  return 0;
}

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

typedef long long ll;
typedef pair<int,int> pii;

long long MOD = 10000000000 + 7;
// modint
const ll mod = 1e9+7;
template< int mod >
struct ModInt {
  int x;
  ModInt() : x(0) {}
  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
  ModInt &operator+=(const ModInt &p) {
    if((x += p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator-=(const ModInt &p) {
    if((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator*=(const ModInt &p) {
    x = (int) (1LL * x * p.x % mod);
      return *this;
  }
  ModInt &operator/=(const ModInt &p) {
    *this *= p.inv();
    return *this;
  }
  ModInt operator-() const { return ModInt(-x); }
  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
  bool operator==(const ModInt &p) const { return x == p.x; }
  bool operator!=(const ModInt &p) const { return x != p.x; }
    
  ModInt inv() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }
  
  ModInt pow(int64_t n) const {
    ModInt ret(1), mul(x);
    while(n > 0) {
      if(n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
  
  friend ostream &operator<<(ostream &os, const ModInt &p) {
    return os << p.x;
  }
  
  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt< mod >(t);
    return (is);
  }
  
  static int get_mod() { return mod; }
};
 
using mint = ModInt<mod>;

int main(){
  cout << setprecision(10);
  int N,K; cin >> N >> K;

  // gcdが kになる場合の個数
  vector<mint> v(K+1,0);

  mint ans = 0;
  for(int i = K; i >= 1; i--){
    mint tmp = K / i; // 上限
    tmp = tmp.pow(N);  // 組み合わせ数

    for(int j = 2; i * j <= K; j++){
      // cerr << "i*j: " << i * j << endl;
      tmp -= v[i*j];
    }
    v[i] = tmp;
    ans += tmp * (mint)i;
  }

  cout << ans << endl;
}


Measured memory_bytes: 3700