akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,t;
    cin>>n>>t;
    vector<int> ts(n);
    for(int i=0;i<n;i++)cin>>ts[i];
    int ans=0;
    for(int i=0;i<n-1;i++){
        ans+=min(t,ts[i+1]-ts[i]);
    }
    ans+=t;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
// {{{
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <complex>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define FOR(i, a, b) for(ll i = static_cast<ll>(a); i < static_cast<ll>(b); i++)
#define FORR(i, a, b) for(ll i = static_cast<ll>(a); i >= static_cast<ll>(b); i--)
#define REP(i, n) for(ll i = 0ll; i < static_cast<ll>(n); i++)
#define REPR(i, n) for(ll i = static_cast<ll>(n); i >= 0ll; i--)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> IP;
typedef pair<ll, LP> LLP;

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

constexpr int INF = 100000000;
constexpr ll LINF = 10000000000000000ll;
constexpr int MOD = static_cast<int>(1e9 + 7);
constexpr double EPS = 1e-9;
// }}}

int N;
ll h[100001], dp[100001];

void init()
{
}

void solve()
{
    dp[1] = 0;
    dp[2] = abs(h[2] - h[1]);
    FOR(i, 3, N+1){
        dp[i] = min(dp[i-2] + abs(h[i]-h[i-2]), dp[i-1] + abs(h[i]-h[i-1]));
    }
    cout << dp[N] << endl;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    FOR(i, 1, N+1) cin >> h[i];
    solve();
    return 0;
}

// vim:set foldmethod=marker:


Measured memory_bytes: 1792
#include <stdio.h>

int main(void){
  int n;
  int frag=0;
  scanf("%d",&n);
  for(int i=1;i<=9;i++){
    for(int j=1;j<=9;j++){
      if(frag==0 && i*j==n){
        printf("Yes");
        frag=1;
      }
    }
  }
  if(frag==0){
    printf("No");
  }
  return 0;
}


Measured memory_bytes: 128
#![allow(unused_variables)]
#![allow(unused_imports)]
#![allow(dead_code)]
use std::io;
use std::str::FromStr;
use std::iter::FromIterator;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::mem::{replace, swap};


// abcde
fn read_string() -> String {
    let mut line = String::new();
    io::stdin().read_line(&mut line).unwrap();
    line
}

// -3.2
fn read_as_primitive<T: FromStr>() -> T {
    let s = read_string();
    s.trim().parse().ok().expect("failed to parse input")
}

// 1 -3 0 999
fn read_as_collection<U: FromStr, T: FromIterator<U>>() -> T {
    let s = read_string();
    s.trim().split_whitespace().map(|s| s.parse().ok().expect("failed to parse")).collect()
}

// #.#.###..
fn read_as_chars<T: FromIterator<char>>() -> T {
    let s = read_string();
    s.trim().chars().collect()
}

// 1 abc
fn read_as_pair<T: FromStr, U: FromStr>() -> (T, U) {
    let s = read_string();
    let elems: Vec<_> = s.trim().split_whitespace().collect();
    (
        elems[0].parse().ok().expect("failed to parse"),
        elems[1].parse().ok().expect("failed to parse"),
    )
}

// 1.5 -2 abc
fn read_as_triple<T: FromStr, U: FromStr, V: FromStr>() -> (T, U, V) {
    let s = read_string();
    let elems: Vec<_> = s.trim().split_whitespace().collect();
    (
        elems[0].parse().ok().expect("failed to parse"),
        elems[1].parse().ok().expect("failed to parse"),
        elems[2].parse().ok().expect("failed to parse"),
    )
}

// Usage:
// let mut v: Vec<f64> = vec![0.1, 1.0, 2.0];
// v.sort_by_key(|&x| Total(x));
// 
// src: https://qiita.com/hatoo@github/items/fa14ad36a1b568d14f3e
//      https://github.com/rust-lang/rust/pull/53938
//
#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);

impl<T: PartialEq> Eq for Total<T> {}

impl<T: PartialOrd> Ord for Total<T> {
    fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}


fn main() {
    let cs: Vec<_> = read_as_chars();
    let ans = cs
        .windows(3)
        // [NOTE] tri should not be &tri; error with size blah happens otherwise.
        .map(|tri| {
            let s = tri.iter().map(|c| c.to_string()).collect::<Vec<_>>().join("");
            // [NOTE] let s: String = tri.iter().collect();  
            // [NOTE] This fails in 1.14 (works in 1.36)
            let n = s.parse::<i64>().unwrap() - 753;
            n.abs()
        })
        .min()
        .unwrap();
    println!("{}", ans);
}

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

inf = 1
sup = max(a)

while inf < sup:
  x = (inf + sup) // 2
  cut = 0
  for a_i in a:
    cut += (a_i - 1) // x
  if cut <= k:
    sup = x
  else:
    inf = x + 1
print(sup)

Measured memory_bytes: 30624
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

constexpr int atcoder_mod = 1e9+7;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}

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

	ll N=in<ll>(),M=in<ll>();
	vector<pair<ll,ll>> P(N);
	REP(i,N){
		P[i].first=in<ll>();
		P[i].second=in<ll>();
	}
	sort(ALL(P),PAIRCOMP(first,<));
	ll sum = 0;
	for(int i=0,num=0;i<N;i++){
		if(num+P[i].second>=M){
			ll m = M-num;
			sum += P[i].first*m;
			break;
		}
		else{
			num += P[i].second;
			sum += P[i].first*P[i].second;
		}
	}
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int d[100][100];
typedef pair<int, int>pii;
typedef pair<pii, int>pi3;
int x[1000];
int main()
{
	int a, b, s, t;
	scanf("%d%d%d%d", &a, &b, &s, &t);
	for (int i = a; i < s; i++)printf("R");
	for (int i = b; i < t; i++)printf("U");
	for (int i = a; i < s; i++)printf("L");
	for (int i = b; i < t; i++)printf("D");
	printf("D");
	for (int i = a; i <= s; i++)printf("R");
	for (int i = b; i <= t; i++)printf("U");
	printf("L");
	printf("U");
	for (int i = a; i <= s; i++)printf("L");
	for (int i = b; i <= t; i++)printf("D");
	printf("R");
}

Measured memory_bytes: 128
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdint.h>
#include<stdbool.h>
#include<tgmath.h>
#include<sys/queue.h>
#include<time.h>
#define ll long long
#define min(a, b) ((a) > (b) ? (b) : (a))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define miin(a, b, c) min((a), min((b), (c)))
#define maax(a, b, c) max((a), max((b), (c)))
#define mod 1000000007
#define INF 1001001001
#define NIL -1

int n, m;
char s[111111], t[111111];

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

main(){
    scanf("%d%d", &n, &m);
    scanf("%s%s", s, t);
    bool flag = true;
    int i=0, j=0, d = gcd(n, m);
    while(i < n){
        if(s[i] != t[j])flag = false;
        i += n/d;
        j += m/d;
    }
    printf("%lld\n", flag?lcm(n, m):-1);
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>

using namespace std;

int main()
{
    int k = 1;
    string s;
    cin >> s;
    int n = s.size()/2;

    if (s.size() % 2 == 0) {

        if (s[n] != s[n-1]) {
            k = s.size()/2;
        } else {
            int a = 0;
            for (int i = 0; i < s.size()/2; i++) {
                if (s[n] == s[n+i] && s[n-1] == s[n-1-i]) a++;
                else break;
            }
            k = s.size()/2 + a;
        }
    } else {

        int a = 0;
        for (int i = 0; i <= s.size()/2; i++) {
            if (s[n] == s[n+i] && s[n] == s[n-i]) a++;
            else break;
        }
        k = s.size()/2 + a;
    }

    cout << k << endl;

    return 0;
}

Measured memory_bytes: 760
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;

int x1, sy, x2, y2;
int n;
int x[200000], y[200000];
vector<P> pos;
int lis[200001]; //lis([index])[長さ] = 最小値

signed main() {
	int i;
	
	cin >> x1 >> sy >> x2 >> y2;
	cin >> n;
	rep(i, n) cin >> x[i] >> y[i];
	
	if (x1 > x2) {
		rep(i, n) x[i] *= -1;
		x1 *= -1;
		x2 *= -1;
	}
	if (sy > y2) {
		rep(i, n) y[i] *= -1;
		sy *= -1;
		y2 *= -1;
	}
	
	rep(i, n) {
		if (x1 <= x[i] && x[i] <= x2 && sy <= y[i] && y[i] <= y2) {
			pos.push_back(P(x[i], y[i]));
		}
	}
	sort(pos.begin(), pos.end());
	
	int INF = 1145141919810;
	rep(i, n + 1) lis[i] = INF;
	lis[0] = -INF;
	rep(i, pos.size()) {
		int id = upper_bound(lis, lis + n + 1, pos[i].second) - lis;
		lis[id] = pos[i].second;
	}
	
	rep(i, pos.size() + 1) {
		if (lis[i] >= INF) break;
	}
	i--;
	
	int length = i;
	double PI = 3.14159265358979;
	double a = 5 * PI - 20;
	double b = 10 * PI - 20;
	double ans = 100 * ((x2 - x1) + (y2 - sy));
	if (length >= min(x2 - x1, y2 - sy) + 1) {
		ans += (length - 1) * a + b;
	}
	else {
		ans += length * a;
	}
	printf("%.14f\n", ans);
	return 0;
}

//x1 <= x2, sy <= y2と仮定しても、一般性を失わない。このとき、噴水は長方形[x1, x2][sy, y2]の中にあるものだけ考えればよい。
//また、x, yが増加する方向にしか進まない場合を考える（←噴水を直進する回数について考察すると、これだけ考えればよいことが分かる）
//先に「通る噴水」を決めておいてから「経路」を決めても探索される「経路」の集合が変わらないことに注意する。
//先に「通る噴水」を決めてみる。通る噴水のy座標をx座標が小さい順に並べてみる。
//すると、「同じ行,列に噴水は高々1個」という制約より、同じx座標の噴水は存在せず、かつ、それは「狭義単調増加列(IS)」になることが分かる。
//
//これより、最大「LISの長さ」回噴水を通ることができる。
//逆に、最小では？
//基本的に「0回噴水を通る」ことはできる。しかし例外がある。
//たとえば、「すべての行(sy <= y <= y2)に噴水があり、左の列から見ると噴水のy座標が単調増加になっている」場合、噴水を少なくとも1回は通らないといけない。
//また、「すべての列(x1 <= x <= x2)に噴水があり、左の列から見ると噴水のy座標が単調増加になっている」場合、噴水を少なくとも1回は通らないといけない。
//（しかも、1回は「噴水を直進」しないといけない！！！！）
//
//「直進せざるを得ないケース」は（LIS回通ると限定したときでも）あまりない。でも例外が2つある。
//・すべての行(sy <= y <= y2)に噴水があり、左の列から見ると噴水のy座標が単調増加になっている場合。
//・すべての列(x1 <= x <= x2)に噴水があり、左の列から見ると噴水のy座標が単調増加になっている場合。
//行のパターンでは、噴水の「上側」から「下側」に移動しないとゴールにたどり着けず、かつ移動するときに「噴水を直進」する必要が出てくる。
//列のパターンでは、「下」→「上」と移動しないとゴールにたどり着けず、かつ移動するときに「噴水を直進」する必要が出てくる。
//それ以外のパターンでは、
//x軸方向に移動した直後に噴水に出会わないことがあるので、そのときに「向こう側」に移動することで「噴水を直進」しなくてよくなる。
//
//すべての行に～, すべての列に～のパターンでは、噴水を直進が少なくとも1回必要。曲がるのは高々LIS - 1回できる。(伸び, 縮み) = (1, LIS-1)が答え。
//それ以外のパターンでは、LIS回噴水を曲がれるので、(0, LIS)が答え。

Measured memory_bytes: 10480
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<bitset>
#include<list>
using namespace std;

int main() {

	vector<int> A(3, 0);

	cin >> A[0] >> A[1] >> A[2];

	cout << *max_element(A.begin(), A.end()) - *min_element(A.begin(), A.end()) << endl;

	return 0;
}


Measured memory_bytes: 256
import fractions
N=int(input())
A=list(map(int,input().split()))
MOD=10**9+7
ans=1
gcd=A[0]
for i in range(1,N):
    a=A[i]
    b=fractions.gcd(a,gcd)
    temp=gcd
    gcd=temp*a//b
    ans=ans*(a//b)+temp//b
    ans%=MOD
print(ans)

Measured memory_bytes: 6116
a = list([str(i) for i in input()])
s1={a[0]}
s2={a[1]}
s3={a[2]}
s4={a[3]}

s_union=s1|s2|s3|s4
if len(s_union)==2 and a.count(a[0])==2 and a.count(a[1])==2 and a.count(a[2])==2:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    vector<int> v;
    bool check=true;
    for(int i=1;i<=n;i++)
    {
        int input;
        scanf("%d",&input);
        if(check)
            v.insert(v.begin(),input);
        else
            v.push_back(input);
        check=!check;
    }
    if(!check)
        for(int i=0;i<v.size();i++)
        printf("%d ",v[i]);
    else
        for(int i=v.size()-1;i>-1;i--)
        printf("%d ",v[i]);
}


Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <climits>
#include <queue>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

using namespace std;

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

int main() {
    // 頂点数と辺数
    int N, M; cin >> N >> M;

    // グラフ入力受取 (ここでは無向グラフを想定)
    vector<vector<int>> G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        G[a-1].push_back(b-1);
        G[b-1].push_back(a-1);
    }

    // BFS のためのデータ構造
    vector<int> dist(N, -1); // 全頂点を「未訪問」に初期化
    queue<int> que;

    // 初期条件 (頂点 0 を初期ノードとする)
    dist[0] = 0;
    que.push(0); // 0 を橙色頂点にする

	vector<int> pre(N);

    // BFS 開始 (キューが空になるまで探索を行う)
    while (!que.empty()) {
        int v = que.front(); // キューから先頭頂点を取り出す
        que.pop();

        // v から辿れる頂点をすべて調べる
        for (int nv : G[v]) {
            if (dist[nv] != -1) continue; // すでに発見済みの頂点は探索しない

			pre[nv] = v;

            // 新たな白色頂点 nv について距離情報を更新してキューに追加する
            dist[nv] = dist[v] + 1;
            que.push(nv);
        }
    }

	cout << "Yes" << endl;
    for(int i=1; i<N; i++){
		cout << pre[i]+1 << endl;
	}
}

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

int main(){
	int N; cin>>N;
	int r = 0, n = 0;
	int  A[N];
	rep(i, N){ cin>>A[i]; n = max(n, A[i]); }
	int half = n/2;
	rep(i, N) if(abs(half - r) > abs(half - A[i])) r = A[i];
	cout<< n <<" "<< r <<endl;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(s) s.begin(), s.end()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;
const int DIV = 1e9+7;

string s;

int main()
{
    cin >> s;
    int n = stoi(s);
    int digit_sum = 0;
    rep(i, s.size()){
        digit_sum += stoi(s.substr(i, 1));
    }
    if(n % digit_sum == 0) puts("Yes");
    else puts("No");

    return 0;
}

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




class Main{


	static	ArrayList<Integer> one ;
	static	ArrayList<Integer> two ;
	static	ArrayList<Integer> three ;
	static	ArrayList<Integer> four ;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);			//文字の入力
		int x =sc.nextInt();
		

		int t = 0;
		for(int i = 1;i <= x;i++){
			t += i;
			if(t >= x){
				System.out.println(i);
				return;
			}
		}



	}
	
	
	
}

class Pair implements Comparable{
	Character from;
	int end;
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return end - otherpair.end;
	}
}




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

using namespace std;

using ll = long long;
typedef pair <int, int> item;

int main()
{	
	int n, w;
	cin >> n >> w;
	vector <item> items;
	items.push_back(make_pair(0, 0));
	vector <vector <ll> > dp(n + 1, vector<ll> (w + 1, 0)) ; 
	for (int i = 0; i < n; i++) {
		item x;
		cin >> x.first >> x.second;
		items.push_back(x);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < items[i].first; j++) {
			dp[i][j] = dp[i - 1][j];
		}
 		for (int j = items[i].first; j <= w; j++) {
 			dp[i][j] = max(dp[i - 1][j - items[i].first] + items[i].second, dp[i - 1][j]);
 		} 	
	}
	cout << dp[n][w];
	
	return 0;	
}

Measured memory_bytes: 80256
#include <stdio.h> 
 #include <math.h> 
 
 
 int main(){ 
     double x1, y1, x2, y2, distance; 
     scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2); 
     distance=sqrt((pow(x2-x1, 2)+pow(y2-y1, 2))); 
     printf("%f\n", distance); 
 
 
     return 0; 
 } 



Measured memory_bytes: 2140
#ifndef LOCAL
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#endif
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
#define sim template < class c
#define int long long
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << '\n'; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
typedef tree< pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
const ll MOD = 1e9 + 7 ;
const ll N = 2e5 + 10 ;
const ll INF = 1e18 + 10 ;
signed main(){
    fastio
    int n , m , k ;
    cin >> n >> m >> k ; 
    map<int, set<int> > row , col ;
    int maxRow , maxCol ;
    maxRow = maxCol = 0 ;
    for(int i = 0; i < k; i++){
        int a , b ;
        cin >> a >> b ; 
        a--, b-- ;
        row[a].insert(b) ;
        col[b].insert(a) ;
        maxRow = max(maxRow, (int)row[a].size()) ;
        maxCol = max(maxCol, (int)col[b].size()) ;
    }
    map<int, set<int> > R , C ;
    for(auto &v : row){
        if ( (int)v.second.size() == maxRow ) {
            R[v.first] = v.second ;
        }
    }
    for(auto &v : col){
        if ( (int)v.second.size() == maxCol ) {
            C[v.first] = v.second ;
        }
    }
    int ans = maxRow + maxCol - 1 ;
    for(auto &r : R){
        for(auto &c : C){
            if ( r.second.count(c.first) == 0 ) {
                cout << ans + 1 << endl;
                return 0 ;
            }
        }
    }
    cout << ans << endl;
    return 0; 
}
// ---##-##--
// -#----#---
// --#######-
// -#-##-----
// -#--------

// ##########
// ##########
// ##########
// ##########
// ##########

Measured memory_bytes: 172300
unittest
{
	assert( [ "5", "2", "1", "4", "5", "3" ].solve == 2 );
	assert( [ "4", "0", "0", "0", "0" ].solve == 4 );
}



import std.conv;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.to!( long );
	auto as = new long[ n ];
	foreach( ref a; as )
	{
		input.popFront;
		a = input.front.to!( long );
	}
	
	// LISを求めた後の使ったバッファの長さが答え
	auto ans = 0L;
	auto cs = new long[ as.length ];
	cs[] = -1;
	auto cs_s = cs.assumeSorted!( ( x, y ) => y < x );
	foreach( a; as )
	{
		auto i = cs_s.lowerBound( a - 1 ).length;
		cs[ i ] = a;
		if( ans <= i ) ans++;
	}
	return ans;
}


Measured memory_bytes: 5288
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
typedef pair<int,int> P;
const int inf=1000000007;
const int MOD=1000000007;
signed main(){
  int x;cin>>x;
  int res=(x/500)*1000;
  res+=((x%500)/5)*5;
  cout<<res<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream> 
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <stack>
#include <cstring>

#define mp make_pair
#define s second
#define f first
#define ll long long
using namespace std;
int dp[3003][3003];

int main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
	
	string a, b, ans;
	cin >> a >> b;
	int n = a.size(), m = b.size();
	
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
			else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);	
		}
	}
	
	int i = n, j = m;
	while (i > 0 and j > 0) {
		if (a[i-1] == b[j-1]) {
			ans += a[i-1];
			i--;
			j--;
		}
		else if (dp[i-1][j] > dp[i][j-1]) i--;
		else j--;
	}
	
	reverse(ans.begin(), ans.end());
	cout << ans;
return 0;	
}




Measured memory_bytes: 35456
import sys
input = sys.stdin.readline

N, M, Q = map(int, input().split())


class CumSum2d(object):
    def __init__(self, H, W):
        self.H, self.W = H, W
        self.tiles = [[0] * W for _ in range(H)]

    def add(self, x, y, c=1):
        self.tiles[y][x] += c

    def build(self):
        for y in range(self.H):
            for x in range(1, self.W):
                self.tiles[y][x] += self.tiles[y][x - 1]
        for y in range(1, self.H):
            for x in range(self.W):
                self.tiles[y][x] += self.tiles[y - 1][x]

    def get(self, sx, sy, tx, ty):
        assert sx <= tx and sy <= ty
        cnt = self.tiles[ty][tx]
        if sx > 0:
            cnt -= self.tiles[ty][sx - 1]
        if sy > 0:
            cnt -= self.tiles[sy - 1][tx]
        if sx > 0 and sy > 0:
            cnt += self.tiles[sy - 1][sx - 1]
        return cnt


cs = CumSum2d(N, N)
for i in range(M):
    l, r = map(int, input().split())
    cs.add(l - 1, r - 1)
cs.build()

for _ in range(Q):
    p, q = map(int, input().split())
    ans = cs.get(p - 1, p - 1, q - 1, q - 1)
    print(ans)


Measured memory_bytes: 13608
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;
import std.bigint;


void main()
{
  auto x = readln.chomp.to!int;
  auto a = readln.chomp.to!int;
  auto b = readln.chomp.to!int;
  writeln((x-a)%b);
}


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

int main() {
  int h,n;
  cin >> h >> n;
  vector<int> a(n);
  
  REP(i,n) cin >> a[i];
  
  int sum = 0;
  
  REP(i,n) sum += a[i];
  
  
  if(sum >= h) cout << "Yes" << endl;
  else cout << "No" << endl;
  
}


Measured memory_bytes: 3704
#include<iostream>
#include<algorithm>
#include<iterator>
#include<vector>
#include<string>
#include<map>

using namespace std;


#define mod(cans) cans%10**9+7
#define cin_pl(x,y) for(int i=0;i<x;i++){cin>>y[i];}
#define pl_twin(x,y,z) for(int i=0;i<x;i++){cin>>y[i]>>z[i];}
#define debug(x) cout << "Debug" << x << "\n"
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define st(s) size_t size = s.length()
#define prians(Answer) cout<<Answer<<"\n"
#define com_div(x,Co) for(int i=1;i<x+1;i++){if(x%i==0){Co++;}}
#define TF(X) X==1?cout<<"Yes\n":cout<<"No\n"
#define elcon else{continue;}

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<vector<int>> matrix;
typedef pair<int,int> pr;
typedef vector<pr> vpt;
typedef greater<int> gi;

int main()
{
    int a,b;
    cin>>a>>b;
    cout<<(a+b)%24;
}

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

bool cmp(long long x, long long y){
    return x>y;
}
int main()
{
    int ca, cb, cc, k;
    cin>>ca>>cb>>cc>>k;

    //vector<long long> a, b, c; 错解，会RE，搞不明白；
    vector<long long> a(ca), b(cb), c(cc);
    for (int i=0; i<ca; i++) cin>>a[i];
    for (int i=0; i<cb; i++) cin>>b[i];
    for (int i=0; i<cc; i++) cin>>c[i];

    vector<long long> tmp;
    for (int i=0; i<ca; i++)
        for (int j=0; j<cb; j++)
            tmp.push_back(a[i]+b[j]);
    sort(tmp.begin(), tmp.end(), cmp);

    vector<long long> ans;
    for (int i=0; i<tmp.size()&&i<k; i++)
        for (int j = 0; j < cc; j++)
            ans.push_back(tmp[i] + c[j]);
    sort(ans.begin(), ans.end(), cmp);

    for (int i = 0; i < k; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 43112
#pragma GCC optimize("O3")

#include <iostream>
#include <math.h>
#include <vector>
#include <fstream>
#include <iomanip>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <queue>
#include <stack>
#include <string.h>
#include <unordered_map>
#include <random>
#include <cassert>

#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define pi acos(-1.0)
#define uniq(v) (v).erase(unique((v).begin(),(v).end()),(v).end())
#define fcin(a) ifstream cin(a);
#define fcout(a) ofstream cout(a);
#define inf (long long)(4e10)
#define MOD 1000000007

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    ll a, b, k;
    cin >> a >> b >> k;
    ll aa = a;
    a -= min(a, k);
    k -= min(aa, k);
    b -= min(b, k);
    cout << a << ' ' << b;
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int ans=1e9;
int check(vector<int> z,int x)
{
  int f=0;
  for(int i=0;i<z.size();i++)
  {
    if(z[i]<x)
    {
      f=1;
      break;
    }
  }
  if(f)
    return 0;
  return 1;
}
int a[13][13],c[13];
void dfs(int s,int sum,int x,vector<int> q,int n,int m,int a[][13])
{
  vector<int> z;
  z.assign(q.begin(),q.end());
  if(check(q,x))
    ans=min(ans,sum);
  if(s<n)
  {
    for(int i=0;i<m;i++)
      z[i]+=a[s][i];
    dfs(s+1,c[s]+sum,x,z,n,m,a);
    dfs(s+1,sum,x,q,n,m,a);
  }
  else
    return;
}
int main()
{
  int n,m,x;
  cin>>n>>m>>x;
  vector<int> w(m,0);
  ans=1e9;
  for(int i=0;i<n;i++)
  {
    cin>>c[i];
    for(int j=0;j<m;j++)
      cin>>a[i][j];
  }
  dfs(0,0,x,w,n,m,a);
  if(ans==1e9)
    ans=-1;
  cout<<ans<<endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
typedef long long ll;
const ll MOD=1e+9+7;
struct mint{
  ll x;
  mint(ll x=0):x(x%MOD){}
  mint& operator+=(const mint a){
    if((x+=a.x)>=MOD) x-=MOD;
    return *this;
  }
  mint& operator-=(const mint a){
    if((x += MOD-a.x)>=MOD) x-=MOD;
    return *this;
  }
  mint& operator*=(const mint a){
    (x*=a.x)%=MOD;
    return *this;
  }
  mint operator+(const mint a) const{
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const{
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const{
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const{
    if(!t) return 1;
    mint a = pow(t>>1);
    a*=a;
    if(t&1) a*=*this;
    return a;
  }
  
  //for prime mod
  mint inv() const{
    return pow(MOD-2);
  }
  mint& operator/=(const mint a){
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const{
    mint res(*this);
    return res/=a;
  }
};
const int NMAX=200010;
mint fact[NMAX],infac[NMAX];
void Make_Fact(){
  fact[0]=fact[1]=1;
  for(int i=2;i<=NMAX-1;++i){
    fact[i]=fact[i-1]*(mint)i;
  }
}
void Make_InvFact(){
  infac[0]=infac[1]=1;
  for(int i=2;i<=NMAX-1;++i){
    infac[i]=infac[i-1]/(mint)i;	
  }
}
mint Comb(int n,int k){
  if(n<0||k<0||n-k<0) return 0;
  return fact[n]*infac[k]*infac[n-k];
}
//return x's prime factor as map
map<int,int> primefactor(int x){
  int nn = x;
  map<int,int> res;
  for(int i=2;i*i<=nn;++i){
    while(nn%i==0){
      res[i]++;
      nn /= i;
    }
  }
  if(nn!=1) res[nn] = 1;
  return res;
}


int main()
{
  Make_Fact();
  Make_InvFact();
  int n,m;cin >> n >> m;
  map<int,int> mp = primefactor(m);
  mint res(1);
  for(auto it=mp.begin();it!=mp.end();it++){
    res *= Comb(it->second+n-1,n-1);
  }
  cout << res.x << "\n";
  return 0;
}


Measured memory_bytes: 3328
let input = readLine()!.characters.split(" ").map{Int(String($0))!}
let (R,G,B,N) = (input[0],input[1],input[2],input[3])
var ans = 0
for r in 0...N {
    for g in 0...N {
        let b = N-r*R-g*G
        if b>=0 && b%B==0 {
            ans += 1
        }
    }
}
print(ans)

Measured memory_bytes: 4208
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <string>

using namespace std;

int main(void){
	int N, M, L;
	cin >> N >> M >> L;
	long long matA[100][100]={0};
	long long matB[100][100]={0};
	long long matC[100][100]={0};
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			cin >> matA[i][j];
		}
	}
	for(int i=0; i<M; i++){
		for(int j=0; j<L; j++){
			cin >> matB[i][j];
		}
	}
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			for(int k=0; k<L; k++){
				matC[i][k] += matA[i][j]*matB[j][k];
			}
		}
	}
	for(int i=0; i<N; i++){
		for(int j=0; j<L; j++){
			if(j!=0) cout << " ";
			cout << matC[i][j];
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 1404
import java.util.*;

class Main{
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        String s[] = new String [3];
        s[0] = "Sunny";
        s[1] = "Cloudy";
        s[2] = "Rainy";
        
        String today = stdIn.next();
        System.out.println(s[0].equals(today) ? s[1] : (today.equals(s[1]) ? s[2] : s[0]));
    }
}

Measured memory_bytes: 19796
"""
keyword: ラジアン, 度

最大限傾けたとき、水と接している面は横から見ると台形ないし三角形となる
水と接している面の面積 x/a が a*b/2 より大きい場合は台形となり、それ以下の場合は三角形となる

・台形の場合
最大限傾けたとき、水と接している台形の上辺の長さをhとすると
(h+b)*a/2 = x/a
h = 2*x/(a**2) - b
求める角度をthetaとすると
tan(theta) = (b-h)/a
theta = arctan((b-h)/a)

・三角形の場合
最大限傾けたとき、水と接している三角形の底辺の長さをhとすると
h*b/2 = x/a
h = 2*x/(a*b)
求める角度をthetaとすると
tan(theta) = b/h
theta = arctan(b/h)
"""

import sys
sys.setrecursionlimit(10**6)

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

import numpy as np

if x/a > a*b/2:
    h = 2*x/(a**2) - b
    theta = np.arctan2(b-h, a) # radian表記なので戻り値の範囲は[-pi/2, pi/2]
    theta = np.rad2deg(theta)
else:
    h = 2*x/(a*b)
    theta = np.arctan2(b, h)
    theta = np.rad2deg(theta)

print(theta)

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

int main(){
    string s,t;
    cin>>s;
    t="x";
    for(int i=0;s.size()!=t.size();i++){
        t=t+"x";
    }
    cout<<t<<endl;
   return 0;
}

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

int cnt[100000];

int main(void) {
  string S;
  cin >> S;
  int size = S.size();
  for(int i = 0; i < size; i++) {
    cnt[i] = 0;
  }
  int cnt_r = 0;
  for(int i = 0; i < size; i++) {
    if(S[i] == 'R') {
      cnt_r++;
    }
    if(S[i] == 'L') {
      int amari = cnt_r % 2;
      cnt[i] += cnt_r / 2;
      cnt[i-1] += cnt_r / 2 + amari;
      cnt_r = 0;
    }
  }
  
  int cnt_l = 0;
  for(int i = size - 1; i >= 0; i--) {
    if(S[i] == 'L') {
      cnt_l++;
    }
    if(S[i] == 'R') {
      int amari = cnt_l % 2;
      cnt[i] += cnt_l / 2;
      cnt[i+1] += cnt_l / 2+amari;
      cnt_l = 0;
    }
  }
  for(int i = 0; i < size; i++) {
    cout << cnt[i] << " ";
  }
  return 0; 
}

Measured memory_bytes: 1024
-- Try AtCoder
-- author: Leonardone @ NEETSDKASU

import qualified Data.ByteString.Char8 as C
import Data.List (sort)

main = putStrLn . solve . C.lines =<< C.getContents

solve [n,ds,m,ts] = if ans then "YES" else "NO"
    where
        n' = C.readInt n
        m' = C.readInt m
        ds' = sort $ map C.readInt $ C.words ds
        ts' = sort $ map C.readInt $ C.words ts
        ans = n' >= m' && f ts' ds'
        f [] _  = True
        f _  [] = False
        f xs@(x:xxs) ys@(y:yys) | x == y = f xxs yys
                                | x >  y = f xs  yys
                                | otherwise = False

Measured memory_bytes: 159868
n, m, q = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]

acc = [[0] * (n + 1) for _ in range(n + 1)]
for l, r in lr:
    acc[l][r] += 1
for i in range(n):
    for j in range(n):
        tmp = acc[i][j + 1] + acc[i + 1][j] - acc[i][j]
        acc[i + 1][j + 1] += tmp

for p, q in pq:
    p -= 1
    ans = acc[q][q] - acc[p][q] - acc[q][p] + acc[p][p]
    print(ans)


Measured memory_bytes: 125400
#include<stdio.h>


double _pow( double a ,int b )
{
	double ret = 1 ;

	while( b-- )
	{
		ret *= a ;
	}

	return ret ;
}



int year ;

double bank_p ,bank_per ,bank_type ;



#define per bank_per / 100

#define type_1 1.0 + ( ( double )year * per )
#define type_2 _pow( 1.0 + per ,year )


int main()
{
	int n ;

	while( 1 )
	{
		scanf( "%d" ,&n ) ;

		if( n == 0 )
		{
			return 0 ;
		}


		double max[ 2 ] = { 0 } ;

		scanf( "%d" ,&year ) ;


		int i ;
		for( i = 0 ; i < n ; ++i )
		{
			scanf( "%lf %lf %lf" ,&bank_p ,&bank_per ,&bank_type ) ;

			double kale = bank_type < 2 ? type_1 : type_2 ;


			if( max[ 0 ] < kale )
			{
				max[ 0 ] = kale ;

				max[ 1 ] = bank_p ;
			}
		}


		printf( "%d\n" ,( int )max[ 1 ] ) ;
	}
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
int main()
{
    int a,b,c;
    cin >> a>>b>>c;

    string ans="win";
    if (a+b+c>21) ans="bust";
    cout << ans<< endl;

   return 0;
}

Measured memory_bytes: 256
def main():
    M, K = map(int, input().split())
    if M == 1:
        if K == 0:
            print('0 0 1 1')
            return
        if K == 1:
            print('-1')
            return
    if (2**M) - 1 < K:
        print('-1')
        return
    l = [i for i in range(K)] + [i for i in range(K+1, (2**M))] + [K] + [i for i in reversed(range(K+1, (2**M)))] + [i for i in reversed(range(K))] + [K]
    print(' '.join(str(i) for i in l))
main()


Measured memory_bytes: 31500
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios::sync_with_stdio(0); cin.tie(0);
ll k=1000000007;
int main(){
  ll a,b,c,d;
  cin>>a>>b>>c>>d;
  ll x=a*c;
  ll y=a*d;
  ll z=b*c;
  ll m=b*d;
  cout<<max(max(x,y),max(z,m));
}


Measured memory_bytes: 3640
#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>
#include <limits>
#include <map>
#include <cmath>

using namespace std;
using lli = long long int;

int main(void) {
	lli N,ans = 0;
	cin >> N;

	if (N == 1) {
		cout << "0" << endl;
		return 0;
	}

	for (lli i = 1; i <= sqrt(N); i++) {
		lli m = (N - i) / i;

		if (N % m == N / m) {
			ans += m;
		}

	}

	cout << ans << endl;

	return 0;
}
//
//int main(void) {
//
//	lli N,ans = 0;
//	cin >> N;
//
//	lli a = 0, b = 0;
//
//	for (int i = 0; i < N; i++) {
//		string str;
//		cin >> str;
//		if (str[0] == 'B') b++;
//		if (str[str.size() - 1] == 'A') a++;
//		for (int j = 0; j < str.size() - 1; j++) {
//			if (str[j] == 'A' && str[j + 1] == 'B') {
//				ans++;
//			}
//		}
//	}
//
//	cout << ans + min(a, b) << endl;
//
//	return 0;
//}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define mod 1000000007
# define INF (1 << 29)
# define MAX_N 1000010
/* ちゃんと考えてわかって実装 */

int main(void){
    int a, b, c;
    cin >> a >> b >> c;
    if(a+b+c >= 22) cout << "bust";
    else cout << "win";
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
   int main(void)
   {
           int a,b,c,i,j,x,y,k,n=0;
   
           scanf("%d%d%d",&a,&b,&k);
   
           if(b>a){
                   c=b;
                  b=a;
                  a=c;
          }
  
  
          for(i=b;i>0;i--){
                  if((b%i==0)&&(a%i==0)){
                          n=n+1;
                          if(n==k) y=i;
                  }
          }
  
          printf("%d\n",y);
  
          return 0;
  }


Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cmath>

using namespace std;

int main(void){

  int N,M,X;
  int A[100];
  int cost[100];

  for(int i=0;i<100;i++){
    cost[i]=0;
  }

  cin >> N;
  cin >> M;
  cin >> X;  

  for(int i=0;i<M;i++){
    cin >> A[i];
    cost[A[i]]=1;
  }

  

  int c1=0;
  int c2=0;  

  for(int i=0;i<X;i++){
    c1+=cost[i];
  }

  for(int i=X;i<100;i++){
    c2+=cost[i];
  }  

  cout << min(c1,c2) << endl;
  
  return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);
#endif

#define FILE_IO freopen("input.txt","r",stdin)
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(c) c.begin(),c.end()
#define debug(x) cerr << #x << " = " << x << endl;

const int MOD = 1e9 + 7;
const int INF = 1<<29;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>void print(T t){for(auto &it:t)cout<<it<<" ";}
inline int powerexp(int a,int b,int m = MOD){int res=1;while(b){if(b&1)res=res*a%m;a=a*a%m,b>>=1;}return res%m;}
inline int modinv(int a){return powerexp(a,MOD-2,MOD);}
inline int lcm(int a,int b){int g=__gcd(a,b);return a/g*b;}

//-------------------< start here >-------------------------// 
const int N = 5005;
int fact[N], invfact[N];
int n,k ;
void pre(){
   fact[0] = 1;
   invfact[0] = modinv(fact[0]);
   for(int i = 1; i < N ; i++){
	     fact[i] = i * fact[i-1];
	     fact[i] %= MOD;
	     invfact[i] = modinv(fact[i]); 
	  }	
}
int nCr(int n,int r){
  if(r > n)
     return 0;
  int ret = fact[n];
  ret *= invfact[n-r];
  ret %= MOD;
  ret *= invfact[r];
  ret %= MOD;
  return ret;  	
}
int fastnCr(int n,int r){
	if(n<r or r<0)return 0;
	int ans=1;
	for(int i=0;i<r;i++){
		ans*=(n-i);ans%=MOD;
	}
	ans*=invfact[r];
return ans%MOD;
}
void solve(){
	pre();
	cin >> n >> k;
	int blue = k, red = n - k;
	for(int i = 1; i <= k; i++){
	   int ret = nCr(red + 1, i);
	   int y = nCr(blue - 1,i - 1);
	   ret *= y;
	   ret %= MOD;
	   cout << ret << endl; 	
	}
}
//-----------------------------
//comment from here for TOPCODER 
int32_t main(){
   IOS;
   solve();
   //find();
   #ifdef LOCAL_DEFINE
   cerr<<"time elapsed "<<(double)clock()/CLOCKS_PER_SEC<<endl;
   #endif
}


Measured memory_bytes: 384
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

vector<int> topological_sort(const vector<vector<int>> &adj) {
    int n = adj.size();
    vector<int> in_degree(n, 0);
    vector<int> order;

    for (int i = 0; i < n; i++)
        for (int neighbor : adj[i])
            in_degree[neighbor]++;

    for (int i = 0; i < n; i++)
        if (in_degree[i] == 0)
            order.push_back(i);

    int current = 0;

    while (current < (int) order.size()) {
        int node = order[current++];

        for (int neighbor : adj[node])
            if (--in_degree[neighbor] == 0)
                order.push_back(neighbor);
    }

    return order;
}

int N, M;
vector<vector<int>> adj;

int main() {
    scanf("%d %d", &N, &M);
    adj.assign(N, {});

    for (int i = 0; i < M; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        x--; y--;
        adj[x].push_back(y);
    }

    vector<int> order = topological_sort(adj);
    vector<int> dp(N, 0);
    int longest = 0;

    for (int node : order) {
        longest = max(longest, dp[node]);

        for (int neighbor : adj[node])
            dp[neighbor] = max(dp[neighbor], dp[node] + 1);
    }

    printf("%d\n", longest);
}


Measured memory_bytes: 6780
#include <bits/stdc++.h>
#include "ext/pb_ds/tree_policy.hpp"
#include "ext/pb_ds/assoc_container.hpp"

using namespace __gnu_pbds;
using namespace std;

#define forn(i, n)             for(int i = 0; i < n; i ++)
#define forn1(i, n)            for(int i = 1; i <= n; i ++)
#define pb push_back
#define ll long long
#define fi first
#define se second
#define ii  pair<int, int>
#define vi  vector <int>
#define vii vector <pair <int, int > >
#define all(cont)  cont.begin(), cont.end()
#define EPS 1e-9
#define MOD 1000000007
#define range 200010
#define int long long
#define IO ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0)
#pragma GCC optimize ("Ofast")

// debug_statment ...............................................................................
template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
string to_string(string s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
 
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
void debug1(int a[], int l, int r) {
  vector<int> temp(a + l, a + r + 1);
  debug(temp);

}


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r){
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}
// end_debug_statment .......................................................................

signed main(){
    IO;
    // freopen("input.txt", "r", stdin);
    int x, y, a, b, c;
    cin >> x >> y >> a >> b >> c;
    int p[a], q[b];

    vi r;

    for( int i =0 ; i < a; i ++ )cin>>p[i];
    for( int i =0 ; i < b; i ++ )cin>>q[i];
    for( int i =0 ; i < c; i ++ ){
      int xx;
      cin>>xx;
      r.pb(xx);
    }


    sort(p,p + a, greater<int>());
    sort(q,q + b, greater<int>());

    sort(r.begin(), r.end());

    multiset<int> mult;

    for(int i = 0 ; i < x ; i ++ )mult.insert(p[i]);
    for(int i = 0 ; i < y ; i ++ )mult.insert(q[i]);

    while(r.empty() != 1 && r.back() > *(mult.begin())){
      mult.erase(mult.begin());
      mult.insert(r.back());
      r.pop_back();
    }
    ll output = 0 ; 
    for(auto it = mult.begin() ; it != mult.end(); it ++ ){
      output += (ll)(*it);
    }
    cout<<output;
    cout << setprecision(10) << fixed;
    return 0;
}




Measured memory_bytes: 10996
#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 x, y, ans = 0;
    cin >> x >> y;
    if(x == 1) ans += 300000;
    else if(x == 2) ans += 200000;
    else if(x == 3) ans += 100000;
    if(y == 1)  ans += 300000;
    else if(y == 2) ans += 200000;
    else if(y == 3) ans += 100000;
    if(x == 1 && y == 1) ans += 400000;
    cout << ans << endl;
    return 0;
}


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

typedef long long int ll;

#define endl '\n'


int main()
{

    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string s;
    cin>>s;

    if(s[0]==s[1]){
        cout<<"Bad"<<endl;return 0;
    }
    else{
        if(s[1]==s[2]){
                cout<<"Bad"<<endl;return 0;
        }
        else{
            if(s[2]==s[3]){
                    cout<<"Bad"<<endl;return 0;
            }
            else{
                cout<<"Good"<<endl;
            }
        }
    }

}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define enld endl //* missspell check
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

struct TopologicalSort{
    vector<vll> G; //* DAG
    TopologicalSort(ll N){ G.resize(N); }
    void add_edge(ll a, ll b) { G[a].push_back(b); }
    bool visit_by_dfs(vll &order, vll &color, ll v) {
        //* color[v] meaning: 0: unvisited, 1: pre-visit, 2: post-visit
        //! return false if this graph has a cycle
        color[v] = 1; //* pre-visit this vertex
        for(auto u: G[v]) {
            if(color[u] == 2) continue; //* this vertex is done (already put in order)
            if(color[u] == 1) return false; //* re-visit this vertex means a cycle
            if(!visit_by_dfs( order, color, u)) return false; //* a cycle detected further
        }
        order.push_back(v);
        color[v] = 2;
        return true;
    }
    bool sort(vll &order) {
        //! return false if this graph has a cycle
        ll n = G.size();
        vll color(n, 0);
        REP(u, n) if( !color[u] && !visit_by_dfs(order, color, u)) return false;   
        reverse(order.begin(), order.end()); 
        return true;
    }
};
void solve(long long N, long long M, std::vector<long long> x, std::vector<long long> y){
    vector<vll> G(N);
    TopologicalSort st(N);
    REP(i, M){
        G[x[i]].push_back(y[i]);
        st.add_edge(x[i], y[i]);
    }
    vll order; 
    st.sort(order);

    vll dp(N, 0);
    for(ll u: order){
        for(ll v: G[u]){
            chmax(dp[v], dp[u] + 1);
        }
    }
    ll res = 0;
    REP(i, N) chmax(res, dp[i]);
    cout<<res<<endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> x(M);
    std::vector<long long> y(M);
    for(int i = 0 ; i < M ; i++){
        scanf("%lld",&x[i]);
        scanf("%lld",&y[i]);
        x[i]--;
        y[i]--;
    }
    solve(N, M, std::move(x), std::move(y));
    return 0;
}


Measured memory_bytes: 15868
#include <iostream>
#include <vector>
#include <stack>
#define int long long
#define WHITE 0
#define GRAY 1
#define BLACK 2
typedef long long ll;
using namespace std;

int N, Q, p[200000]={0}, score[200000]={0}, color[200000]={0};
vector<int> E[200000];

void dfs(int s){
    stack<int> S;
    S.push(s);
    score[s] = p[s];
    color[s]=GRAY;
    while(!S.empty()){
        int u=S.top();
        S.pop();
        for(int i=0;i<E[u].size();i++){
            if(color[E[u][i]]==WHITE){
                color[E[u][i]] = GRAY;
                score[E[u][i]] = score[u]+p[E[u][i]];
                S.push(E[u][i]);
            }
        }
        color[u]=BLACK;
    }
}

signed main(){
    int a, b;
    cin >> N >> Q;
    for(int i=0;i<N-1;i++) {
        cin >> a >> b;
        a--;
        b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }
    for(int i=0;i<Q;i++) {
        cin >> a >> b;
        a--;
        p[a] += b;
    }
    dfs(0);
    for(int i=0;i<N;i++) {
        if(i) cout << " " << endl;
        cout << score[i];
    }
    return 0;
}

Measured memory_bytes: 20208
def dsum(x):
  ans,str_x=0,str(x)
  for i in range(len(str_x)):ans+=int(str_x[i])
  return ans
n,a,b=map(int,input().split())
ans=0
for i in range(1,n+1):
  if a<=dsum(i)<=b:ans+=i
print(ans)

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

#define ll long long
#define ld long double
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long

using namespace std;
const int INF = 1e18;
const int MB = 20;
const int MOD = 998244353;
const int maxN = 1e6;

void solve() {
	int n;
	cin >> n;
	int res = 1;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		if (res && INF / res < x) {
			res = INF + 1;
		}
		else {
			res *= x;
		}
	}
	cout << (res > INF ? -1 : res);
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout << fixed;
	cout.precision(12);
	srand(time(0));
	int t = 1;
	//int t;
	//cin >> t;
	while (t--) solve();
}


Measured memory_bytes: 3648