akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=10005,INF=1<<28;
vector<pair<int,double>> G[MAX];
double dis[MAX];

void dijkstra(int u){
    dis[u]=0;
    priority_queue<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>>> PQ;
    
    PQ.push(make_pair(0,u));
    while(!PQ.empty()){
        double a=PQ.top().first;
        int b=PQ.top().second;
        PQ.pop();
        if(dis[b]<a) continue;
        for(int i=0;i<G[b].size();i++){
            int c=G[b][i].first;
            double d=G[b][i].second;
            if(dis[c]>dis[b]+d){
                dis[c]=dis[b]+d;
                PQ.push(make_pair(dis[c],c));
            }
        }
    }
    return;
}//a,dが長さ

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    while(1){
        int K,N,M,s,g;cin>>K>>N>>M>>s>>g;
        if(K+N==0) break;
        s--;g--;
        
        for(int i=0;i<N*(1<<K);i++){
            dis[i]=INF;
            G[i].clear();
        }
        vector<double> S(K);
        for(int i=0;i<K;i++) cin>>S[i];
        
        for(int q=0;q<M;q++){
            int a,b;
            double c;cin>>a>>b>>c;
            a--;b--;
            
            for(int bit=0;bit<(1<<K);bit++){
                for(int use=0;use<K;use++){
                    if(bit&(1<<use)) continue;
                    
                    G[bit*N+a].push_back({(bit|(1<<use))*N+b,c/S[use]});
                    G[bit*N+b].push_back({(bit|(1<<use))*N+a,c/S[use]});
                }
            }
        }
        
        dijkstra(0*N+s);
        
        double ans=INF;
        
        for(int bit=0;bit<(1<<K);bit++){
            ans=min(ans,dis[bit*N+g]);
        }
        
        if(ans==INF) cout<<"Impossible"<<endl;
        else cout<<setprecision(25)<<ans<<endl;
    }
}





Measured memory_bytes: 26020
import math
A, B, H, M = map(int, input().split())

kakuA = 30 * H + 30 * M / 60
kakuB = 360 * M / 60

dkaku = abs(kakuA - kakuB)
dkaku = min(dkaku, 360 - dkaku)
print(math.sqrt(A ** 2 + B ** 2 - 2 * A * B * math.cos(math.radians(dkaku))))

Measured memory_bytes: 62372
import collections

n = int(input())
s = []
for i in range(n):
    s.append(input())
c = collections.Counter(s)
c_most = c.most_common()

i = 0
ans = []
while (True):
    ans.append(c_most[i][0])
#    print(c_most[i][0])
    i += 1
    if i == len(c_most):
        break
    if c_most[i][1] != c_most[i - 1][1]:
        break
ans.sort()
for i in range(len(ans)):
    print(ans[i])

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

int main() {
   int X, N;
   cin >> X >> N;
   if (N == 0) cout << X << endl;
   else {
       vector<bool> num(101, false);
       for (int i = 0; i < N; i++) {
           int tmp;
           cin >> tmp;
           num[tmp] = true;
       }
       int sub = 10000;
       int ans = 100;
       for (int i = 100; i >= 0; i--) {
           if (!num[i]) {
              int sub_tmp = abs(X-i);
              if (sub >= sub_tmp) {
                 sub = sub_tmp;
                 ans = i;
              }
           }
       }
       if ((101-X) < sub) ans = 101;
       cout << ans << endl;
   }
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>   
using namespace std;
using namespace __gnu_pbds;
typedef long long ll; 
#define int long long
typedef unsigned long long lu;
typedef vector<ll> v;
typedef vector<vector<ll> > vv;
typedef vector<string>  vs;
typedef vector<pair<ll,ll>> vpr;
typedef long double ld;
#define f(i,n) for(ll i = 0; i < n; i++)
#define ff(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define endl "\n"
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define amax(x,y) if(y>x) x=y;
#define amin(x,y) if(y<x)x=y;
#define bg(x) x.begin()
#define sz(x) (ll)x.size()
#define in(x,n) for(ll i=0;i<n;i++)cin>>x[i]
#define out(x,n) for(ll i=0;i<n;i++)cout<<x[i]<<" " 
#define mxt(a) *(max_element(a.begin(),a.end()))
#define mnt(a) *(min_element(a.begin(),a.end())
#define tc ll t;cin>>t;while(t--)
typedef pair<ll,ll> pi;
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
#define yesno(f) if(f) yes else no
const v dx = {1, -1, 0, 0};
const v dy = {0, 0, 1, -1};
const ll mod=1e9+7;
const ld PI = 2 * acos(0.0);
ll m(ll a){ return (a+mod)%mod;}
ll cel(ll x1,ll y1){if((x1%y1)==0)return x1/y1;else return x1/y1+1;}
ll power(ll a,ll b,ll m)
{
	if(b==0)
		return 1;
	ll d=power(a,b/2,m);
	d=(d*d)%m;
	if(b&1)
		d=(d*a)%m;
	return d;
}
// set_name.find_by_order(k) It returns to an iterator to the kth element (counting from zero) in the set in O(logn) time
// set_name.order_of_key(k) It returns to the number of items that are strictly smaller than our item k in O(logn) time.
/*string operations :
str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
str.substr (x) : returns a substring str[x],... end of string
str.find(qtr) : returns the first occurenece of qtr in str */
int MOD(int a)
{
	if(a < 0)
		a+=mod;
	if(a>mod)
		a%=mod;
	return a;
}

int32_t main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int tt=1;
	int N=1e5;
	N*=2;
	vv div(N);
	for(int i=1;i<N;i++)
	{
		for(int j=2*i;j<N;j+=i)
			div[j].pb(i);
	}
	int n;cin>>n;
	int k;cin>>k;
	int ans=0;
	v freq(k+1,0);
	for(int g=k;g>=1;g--)
	{

		int k1=k/g;
		freq[g]+=power(k1,n,mod);
		freq[g]=MOD(freq[g]);
		for(auto it:div[g])
		{
			freq[it]-=freq[g];
			freq[it]=MOD(freq[it]);
		}
		ans+=(freq[g]*g)%mod;
		ans=MOD(ans);
		// cout<<freq[g]<<" "<<g<<endl;

	}

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

Measured memory_bytes: 37232
n = int(input())
a = [int(i) for i in input().split()]
even_number = [i for i in a if i % 2 == 0]

answer = 0
while len([i for i in even_number if i % 2 == 0]) > 0:
  even_number = [i / 2 for i in even_number if i % 2 == 0]
  answer += len(even_number)

print(answer)


Measured memory_bytes: 4212
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <complex>
#include <iomanip>
#include <cmath>
#include <tuple>
using namespace std;

long long const MOD = 1000000007LL;

int yakusu[1001];

void soinsubunkai(int i) {
    int now = 2;
    while (i > 1) {
        if (i % now == 0) {
            ++yakusu[now];
            i /= now;
        } else {
            ++now;
        }
    }
    return;
}

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

    for (int i = 1; i <= n; i++) yakusu[i] = 0;

    for (int i = 1; i <= n; i++) soinsubunkai(i);

    long long res = 1;
    for (int i = 1; i <= n; i++) {
        res %= MOD;
        res *= (yakusu[i] + 1) % MOD;
    }

    cout << res % MOD << endl;
}


Measured memory_bytes: 256
/* imports all std modules {{{*/
import
  std.algorithm,
  std.array,
  std.ascii,
  std.base64,
  std.bigint,
  std.bitmanip,
  std.compiler,
  std.complex,
  std.concurrency,
  std.container,
  std.conv,
  std.csv,
  std.datetime,
  std.demangle,
  std.encoding,
  std.exception,
  std.file,
  std.format,
  std.functional,
  std.getopt,
  std.json,
  std.math,
  std.mathspecial,
  std.meta,
  std.mmfile,
  std.net.curl,
  std.net.isemail,
  std.numeric,
  std.parallelism,
  std.path,
  std.process,
  std.random,
  std.range,
  std.regex,
  std.signals,
  std.socket,
  std.stdint,
  std.stdio,
  std.string,
  std.system,
  std.traits,
  std.typecons,
  std.uni,
  std.uri,
  std.utf,
  std.uuid,
  std.variant,
  std.zip,
  std.zlib;
/*}}}*/

/+---test
4
---+/

void main(string[] args) {
  const r = readln.chomp.to!long;
  (3*r.pow(2)).writeln;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		for (int i = 0; i < 3; i ++) {
			String s = sc.next();
			System.out.print(s.substring(0, 1).toUpperCase());
		}
	}
}


Measured memory_bytes: 21716
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


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

	int n, i, j, k;
	bool valid = true;
	string s, ss;
	cin >> n >> ss;
	set<string> w;
	w.insert(ss);
	for (i = 1; i < n; i++) {
		cin >> s;
		if (w.find(s) != w.end()) valid = false;
		if (s[0] != ss[ss.length() - 1]) valid = false;
		ss = s;
		w.insert(s);
	}
	if (valid) cout << "Yes\n";
	else cout << "No\n";

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <queue>
using namespace std;
#define SZ(v) ((int)(v).size())
const int maxint = -1u>>1;
const int maxn = 1000000 + 40;

int r, c, q;
int t[maxn * 4], a[maxn];

inline int to(int x, int y, int c) {
    return x * c + y;
}
int build(int x, int n, int lf, int rt) {
    if (lf == rt) {
        return t[to(x, n, c * 4)] = a[to(x, lf, c)];
    }
    int mid = (lf + rt) / 2;
    return t[to(x, n, c * 4)] = min(build(x, n * 2, lf, mid), build(x, n * 2 + 1, mid + 1, rt));
}

int query(int x, int n, int lf, int rt, int x1, int x2) {
    //printf("%d %d\n", x1, x2);
    if (lf == x1 && rt == x2) {
        //printf("%d %d %d: %d\n", x, n, c * 4, to(x, n, c * 4));
        return t[to(x, n, c * 4)];
    }
    int mid = (lf + rt) / 2;
    if (mid >= x2) {
        return query(x, n * 2, lf, mid, x1, x2);
    } else if (mid < x1) {
        return query(x, n * 2 + 1, mid + 1, rt, x1, x2);
    }
    return min(query(x, n * 2, lf, mid, x1, mid), query(x, n * 2 + 1, mid + 1, rt, mid + 1, x2));
}

void gao() {
    bool f = false;
    if (r > c) {
        swap(r, c);
        f = true;
        for (int i = 0; i < c; ++i) {
            for (int j = 0; j < r; ++j) {
                scanf ("%d", &a[to(j, i, c)]);
            }
        }
    } else {
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                scanf ("%d", &a[to(i, j, c)]);
            }
        }
    }
    for (int i = 0; i < r; ++i) {
        build(i, 1, 0, c - 1);
    }
    while (q--) {
        int r1, c1, r2, c2;
        scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
        if (f) swap(r1, c1), swap(r2, c2);
        int ans = query(r1, 1, 0, c - 1, c1, c2);
        for (int i = r1+1; i <= r2; ++i) {
            ans = min(ans, query(i, 1, 0, c - 1, c1, c2));
        }
        printf ("%d\n", ans);
    }
}

int main() {
    while (scanf ("%d%d%d", &r, &c, &q), r || c || q) {
        gao();
    }
    return 0;
}

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

#define ll long long

ll N, M, I1, I2, J1, J2;
char A[1000][1000];
vector < vector < ll > > dp(1000, vector < ll > (1000, 2e9));
vector < pair < ll, ll > > dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

bool isvalid(ll i, ll j){
	return (i >= 0 && i < N && j >= 0 && j < M);
}

void update(ll i, ll j, ll cost, queue < pair < ll, ll> > &Q){
    if (i >= N || i < 0 || j >= M || j < 0 || dp[i][j] != 2e9 || A[i][j] != '.')
        return;
    Q.push({i, j});
    dp[i][j] = cost;
    for (auto d : dir)
	    update(i + d.first, j + d.second, cost, Q);
}

int main(){
	cin >> N >> M >> I1 >> J1 >> I2 >> J2;
	I1 -= 1; J1 -= 1; I2 -= 1; J2 -= 1;
	for (ll i = 0; i < N; i ++)
		for (ll j = 0; j < M; j ++)
			cin >> A[i][j];
	queue < pair < ll, ll > > Q;
	update(I1, J1, 0, Q);
	long long cost = 1;
	while (Q.size() > 0){
		ll len = Q.size();
		while (len --){
			pair < ll, ll > U = Q.front();
			Q.pop();
			ll U1 = U.first, U2 = U.second;
			for (ll j = -2; j <= 2; j++){
				for (ll k = -2; k <= 2; k ++){
					if (U1 + j == U1 && U2 + k == U2) continue;
					update(U1 + j, U2 + k, cost, Q);
				}
			}
		}
		cost += 1;
	}
	cout << (dp[I2][J2] == 2e9 ? -1 : dp[I2][J2]) << "\n";
}



Measured memory_bytes: 12576
require 'pp'

#pp $t

def init()
	$t = Array.new(17).map{Array.new(17, 0)}
	$t[1][1] = 1
	$vert = Array.new(17).map{Array.new(17, true)}
	$horiz = Array.new(17).map{Array.new(17, true)}
end

def input_matatabi()
	a = gets.chomp.split(" ").map{|str| str.to_i}
	if a[0] == a[2]
		$vert[a[0] + 1][[a[1], a[3]].min + 1] = false
	else
		$horiz[[a[0], a[2]].min + 1][a[1] + 1] = false
	end
end

def calc_t()
	for i in 1..16
		for j in 1..16
			if $vert[i][j - 1]
				$t[i][j] += $t[i][j - 1]
			end
			if $horiz[i - 1][j]
				$t[i][j] += $t[i - 1][j]
			end
		end
	end
end

n = gets.chomp.to_i

n.times do
	init()

	gx, gy = gets.chomp.split(" ").map{|str| str.to_i}
	num_matatabi = gets.chomp.to_i

	num_matatabi.times do
		input_matatabi
	end

	calc_t()

	if ($t[gx + 1][gy + 1] == 0)
		puts "Miserable Hokusai!"
	else
		puts $t[gx + 1][gy + 1]
	end

#	pp $vert.map{|a| a.map{|value| value ? 0 : 1}}
#	pp $horiz.map{|a| a.map{|value| value ? 0 : 1}}
#	pp $t
end

Measured memory_bytes: 9132
def iin(): return int(input())

l = iin()
stack = []

ans = [[1, 2, 0]]
x = l
while True:
    if x == 1:
        break
    #x > 2を条件に加えた理由: 
    #x = 1 -> 2の操作を*2で済ませると[1, 2, 0], [2, 3, 0], [2, 3, 1] となり、
    #頂点数が21以上になるケースが出るため, x = 1 -> 2は+1で済ませる
    while x % 2 == 0 and x > 2:
        x //= 2
        stack.append('*2')
    if x == 1:
        break
    x -= 1
    stack.append('+1')

last_v_num = 2
x = 1#L, つまりパスの数
while len(stack) > 0:
    op = stack.pop()
#    print(op)
    if op == '+1':
        x += 1#パスの数を増やす
        ans.append([1, last_v_num, x - 1])#頂点1と最後の頂点を直接結ぶ, 辺の重みはパスの数 - 1
    elif op == '*2':
        x *= 2#パスの数を増やす
        for i in range(len(ans)):
            ans[i][2] *= 2#w *= 2して, 既存のパスの重みを2倍にする
        #最後の頂点の後ろに, 新たな頂点を加えて結ぶ, 辺の重みは0と1
        ans.append([last_v_num, last_v_num + 1, 0])
        ans.append([last_v_num, last_v_num + 1, 1])
        last_v_num += 1

N = last_v_num
M = len(ans)
print(N, M)
for u, v, w in ans:
   print(u, v, w)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1001001001
#define LINF 1001001001001001001
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LLP;

int main() {

    int A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;

    int max_P = 0;
    int max_Q = 100 * A;

    for (int a = 0; a * 100 <= F; a += A) for (int b = 0; (a + b) * 100 <= F; b += B) {
        if (a == 0 && b == 0) continue;
        int x = 100 * (a + b);
        for (int c = 0; c + x <= F; c += C) for (int d = 0; c + d + x <= F; d += D) {
            int y = c + d;
            if ((a + b) * E < y) continue;
            if (max_P * (x + y) < max_Q * 100 * y) {
                max_P = 100 * y;
                max_Q = x + y;
            }
        }
    }

    printf("%d %d\n", max_Q, max_P / 100);
    
    return 0;
}

Measured memory_bytes: 3656
#include<iostream>
#include<cmath>
using namespace std;
int main(){
    double x1,y1,x2,y2;
    cin >>x1>>y1>>x2>>y2;
    double d;
    d=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    printf("%lf\n",d);
    return 0;
}


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

int main() {
  int N;
  cin >> N;
  int a, count = 0;
  for(int i = 1; i <= N; i=i+2) {
    count = 0;
    for(int j = 1; j <= i; j++) {
      if(i%j == 0) {
        count++;
      }
    }
    if(count == 8) {
      a++;
    }
  }
  cout << a << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); i++)
#define all(vec) vec.begin(), vec.end()
#define MOD 1000000007
#define intt int64_t

int main() {
    int a, b, c, k;
    scanf("%d %d %d\n%d", &a, &b, &c, &k);

    int m=max(max(a, b), c),
        ans=a+b+c-m;
    rep(i,k) m*=2;
    ans+=m;
    printf("%d\n", ans);
}

Measured memory_bytes: 256
N = int(input())
L =[]
l2 = []
for _ in range(N):
   L.append(int(input()))
ma = max(L)

if L.count(ma) > 1:
  [print(ma) for _ in range(N)]
else:  
  for i in L:
    if i == ma:
      print(sorted(L)[-2])
    else:
      print(ma)

Measured memory_bytes: 19232
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
#define dbg(x) cerr << #x << ": " << x << endl

bool gt(string s, string t) {
  if(s.size() > t.size()) return true;
  if(s.size() < t.size()) return false;
  return s > t;
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> A(m);
  rep(i, m) cin >> A[i];
  vector<int> K = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};
  vector<string> dp(n + 1, "X");
  dp[0] = "";
  for(int j = 1; j <= n; j++) {
    rep(i, m) {
      int k = K[A[i]];
      if(j - k < 0) continue;
      if(dp[j - k] == "X") continue;
      char c = '0' + A[i];
      string s = dp[j - k] + c;
      if(dp[j] == "X" || gt(s, dp[j])) {
        dp[j] = s;
      }
    }
  }
  cout << dp[n] << endl;
  return 0;
}

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

int main() {
  int A,B;
  cin >> A >> B;
  int sum =0;
  int N = B - A + 1;
  int a, b, d, e;
  for ( int i = 0 ; i < N ; i++) {
    a = A % 10;
    b = A / 10 % 10;
    d = A / 1000 % 10;
    e = A / 10000;
    if ( a == e && b == d){
      sum += 1;
    }
    A += 1;
      }
  cout << sum << endl;
  // ここにプログラムを追記
}


Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;
use  std::collections::BTreeMap;
use std::cmp::min;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("faild to read char") as char)
        .take_while(|c| !c.is_whitespace())
        .collect();
    token
        .parse()
        .ok()
        .expect("faild to parse token")
}

enum Query {
    Rev,
    Insert {
        is_front : bool,
        val: char,
    }
}

fn main(){
    let s: String  = read();
    let q: usize = read();
    let mut query: Vec<Query> = Vec::with_capacity(q);
    for _ in 0..q {
        let t: usize = read();
        if t == 1 {
            query.push(Query::Rev);
        } else {
            query.push(Query::Insert{is_front: read::<u8>() == 2, val: read::<String>().chars().collect::<Vec<char>>()[0]});
        }
    }

    let mut rev = false;
    let mut front: Vec<char> = Vec::with_capacity(q);
    let mut back: Vec<char> = Vec::with_capacity(q);

    for qe in &query {
        match qe {
            &Query::Rev => { rev = !rev; },
            &Query::Insert { is_front, val } => {
                if rev ^ is_front {
                    back.push(val);
                } else {
                    front.push(val);
                }
            }
        }
    }

    if !rev{
        front.reverse();
        for f in &front {
            print!("{}", f);
        }
        print!("{}", s);
        for b in &back {
            print!("{}", b);
        }
        println!("");
    } else {
        back.reverse();
        for b in &back {
            print!("{}", b);
        }
        print!("{}", s.chars().rev().collect::<String>());
        for f in &front {
            print!("{}", f);
        }
        println!("");
    }
}


Measured memory_bytes: 8700
import java.util.regex.*;
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
   //   String[] nyu=sc.nextLine().split("");
     String nyu=sc.nextLine();

String str = nyu;
String[] regex = new String[10];
for(int i=0;i<10;i++){
regex[i]="(.)*"+i+"{2,}(.)*";

}

int flag=0;

for(int i=0;i<10;i++){
Pattern p = Pattern.compile(regex[i]);
Matcher m = p.matcher(str);

if (m.find())flag++;

}


if (flag>0) {
 System.out.println("Bad");
} else {
 System.out.println("Good"); // → こちら
}


//int num=Integer.parseInt(nyu);
//int numnext=Integer.parseInt(nyu[1]);
//int numend=Integer.parseInt(nyu[2]);

//System.out.println(numend);

//System.out.println(a/b);


	}
}

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

int compress(vector<int> bars){
  int ans = 1;
  set<int> cur;
  rep(i,bars.size()){
    if(cur.count(bars[i]) == 1 || cur.count(bars[i]+1) == 1){
      ans++;
      cur.clear();
    }
    cur.insert(bars[i]); cur.insert(bars[i]+1);
  }
  return ans;
}

int main(){
  int w,n;
  cin >> w >> n;

  vector<int> a(n);
  rep(i,n)cin >> a[i], a[i]--;

  vector<int> target(w);
  rep(i,w)target[i] = i;
  rep(i,n){
    swap(target[a[i]], target[a[i]+1]);
  }

  int ans = n;
  vector<int> perm(n);
  rep(i,n)perm[i] = i;
  do{
    vector<int> cur(w);
    rep(i,w)cur[i] = i;
    rep(i,n){
      swap(cur[a[perm[i]]], cur[a[perm[i]]+1]);
    }

    if(cur == target){
      vector<int> bars(n);
      rep(i,n)bars[i] = a[perm[i]];
      ans = min(ans, compress(bars));
    }

  }while(next_permutation(perm.begin(),perm.end()));

  cout << ans << endl;
}

Measured memory_bytes: 1216
N, M = map(int, input().split(" "))
X = list(map(int, input().split(" ")))

X = sorted(X)
gaps = sorted([X[i+1] - X[i] for i in range(M-1)], reverse=True)

if N >= M:
    print(0)
else:
    print(X[-1] - X[0] - sum(gaps[:N-1]))

Measured memory_bytes: 13968
int main(void)
{
	int n;
	scanf("%d", &n);
	int *a = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", a + i);
	}
	int max = 0;
	int buff;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			buff = abs(a[i] - a[j]);
			if (max < buff)		max = buff;
		}
	}
	printf("%d\n", max);
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<int> a(n), b(n);
  for(int i=0;i<n;i++) cin>>a[i];
  for(int i=0;i<n;i++) cin>>b[i];
  long long e=0; // excess
  long long t=0; // to_add
  for(int i=0;i<n;i++) {
    if((a[i]-b[i])%2){
        b[i]++;
        t+=2;
    }
    if(b[i]<a[i]){
      t+=2*(a[i]-b[i]);
      b[i]=a[i];
    }
    e+=b[i]-a[i];
  }
  if(e>=t)
    cout<<"Yes";
  else
   cout<<"No";
  return 0;
}

Measured memory_bytes: 384
# coding: utf-8
# Your code here!
n = int(input())
t ,a = map(int,input().split())
h = list(map(int,input().split()))
ans = 0
kar = 10**9
for i in range(n):
    tmp = t - h[i]*0.006
    if kar > abs(tmp-a):
        kar = abs(tmp-a)
        ans = i+1
    
print(ans)

Measured memory_bytes: 3064
n=int(input())
s=[ord(c)%3for c in input()]
d=[0]*3
for i in s:d[i]+=1
a=0
for i in range(n):
    d[s[i]]-=1
    b=d.copy()
    for j in range(i+1,n):
        b[s[j]]-=1
        if s[i]==s[j]:continue
        c=(0,2,1,0)[s[i]+s[j]]
        a+=b[c]
        k=j+j-i
        if k<n and s[k]==c:
            a-=1
print(a)

Measured memory_bytes: 68556
#include <stdio.h>
#include <algorithm>
typedef long long ll;
using namespace std;

int main(void) {
  ll i, j, k, a, b, c, n, ans = 1e9;
  scanf("%lld%lld", &n, &k);
  ll h[n];
  for(i = 0; i < n; ++i) scanf("%lld", &h[i]);
  sort(h, h + n);
  for(i = 0; i <= n - k; ++i) if(ans > h[i + k - 1] - h[i]) ans = h[i + k - 1] - h[i];
  printf("%lld", ans);
  return 0;
}

Measured memory_bytes: 896
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}

void main()
{
  int n, k; readV(n, k); --k;
  dchar[] s; readV(s);

  s[k] = s[k].toLower;
  writeln(s);
}


Measured memory_bytes: 256
#![allow(unused)]
use std::io::{self, Read};

fn get_stdin() -> String {
    let mut buf = String::new();
    let mut stdin = io::stdin();
    stdin.read_to_string(&mut buf);
    return buf
}

fn to_nums(ss: &str) -> Vec<i32> {
    ss.split_whitespace()
        .map(|x| x.parse::<i32>().unwrap())
        .collect()
}

fn main() {
    let input = get_stdin();
    let v: Vec<i32> = to_nums(&input);
    if v[0] < v[1] && v[1] < v[2] {
        println!("Yes");
    } else {
        println!("No");
    }
}



Measured memory_bytes: 5028
import sys
def input():
    return sys.stdin.readline()[:-1]
H,N=map(int,input().split())
l=[1000000000]*(H+1)
l[0]=0
for i in range(N):
    A,B=map(int,input().split())
    for j in range(1,min(A+1,H+1)):
        if l[j]>B:
            l[j]=B
    for j in range(H):
        if j+A<=H:
            if l[j]+B<l[j+A]:
                l[j+A]=l[j]+B
print(l[-1])

Measured memory_bytes: 42220
#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define sws ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
#define teto(a, b) ((a+b-1)/(b))
using namespace std;

const int MAX = 200000;
const int MOD = 1000000007;
const int INF = 1e8;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ld EPS = 1e-7;

// Extra
#define forn(i, n) for(int i = 0; i < (int)n; i++)
#define forne(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
//

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

    vi dv;
    int d = __gcd(a, b);
    for(int i = 1; i*i <= d; i++) {
        if(d%i == 0) {
            dv.pb(i);

            if(d/i != i)
                dv.pb(d/i);
        }
    }

    sort(dv.rbegin(), dv.rend());
    cout << dv[k-1] << endl;

    return 0;
}


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

    #define ll long long
    #define ff first
    #define ss second
    #define pb push_back
    #define vll vector<ll>
    #define mll map<ll,ll>
    #define MOD 1000000007
    #define pll pair<ll,ll>
constexpr ll INF = 1999999999999999997; 
    #define fastio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
    int main() {
        fastio;

        int n,x;
        cin>>n>>x;
        int ans=1;
        int d=0;
        for(int i=0;i<n;i++)
        {
           int y;
           cin>>y;
           d=y+d;
           if(d<=x)
            ans++;

        }
        cout<<ans<<endl;
    }

Measured memory_bytes: 3644
import sys
s = list(raw_input())
if len(s) == 2:
    if s[0] == s[1]:
        print 1, 2
    else:
        print -1, -1
else:
    for n in [3]:
        for i in xrange(len(s) - n + 1):
            sub = s[i:i+n]
            for char in set(sub):
                if sub.count(char) >= n / 2 + n % 2:
                    print i + 1, i + n
                    sys.exit()
    print -1, -1


Measured memory_bytes: 3460
#include<iostream>
#include<map>
int main(){
  int n;
  std::cin>>n;
  int64_t ans = 0;
  std::map<int,int64_t> mp;
  for(int i=1;i<=n;++i){
    int ai;
    std::cin>>ai;
    ans += mp[i-ai];
    mp[ai+i]++;
  }
  std::cout<< ans <<std::endl;
}

Measured memory_bytes: 26336
#include <iostream>
#include <string>
using namespace std;
int main(int argc, const char * argv[]) {
    string s, t;
    cin >> s >> t;
    int count = 0;
    for (int i = 0; i < 3; i++) {
        if (s[i] == t[i]) count++;
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	typedef double d;
    #define    thunder   ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL)
    int main()

    {
    thunder;
    double n,x;
    int t;
    cin>>n>>x>>t;
    int a=ceil(n/x);
    cout<<a*t<<endl;
    }

    

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

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}

const long long MOD = 1000000007;

int main(){
  int n, k;
  cin>>n>>k;
  int l = (n-1)*(n-2) / 2;
  if(k > l) {
    std::cout << -1 << std::endl;
    return 0;
  } else {
    l -= k;
    int m = 0;
    vector<pair<int,int>> v;
    for(int i=2; i<=n; i++) {
      v.push_back(make_pair(1,i));
      m++;
    }
    bool f = false;
    for(int i=2; i<=n; i++) {
      if(f) break;
      for(int j=i+1; j<=n; j++) {
	if(l == 0) {
	  f = true;
	  break;
	}
	v.push_back(make_pair(i,j));
	l--;
	m++;
      }
    }
    std::cout << m << std::endl;
    rep(i,m) std::cout << v[i].first << ' ' << v[i].second << std::endl;
  }
  return 0;
}


Measured memory_bytes: 384
#define _CRT_SECURE_NO_WARNINGS
#include"bits/stdc++.h"
#ifdef _DEBUG
#define DBG(n) n
#else
#define DBG(n)
#endif
#define INF          1e9
#define INFLL        1e18
#define EPS          1e-9
#define MOD          1000000007
#define REP(i,n)     for(ll i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)    for(ll i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)    for(ll i=(n)-1;i>=0;--i)
#define REPR1(i,n)   for(ll i=(n);i>0;--i)
#define REPC(i,obj)  for(auto i:obj)
#define ALL(obj)     (obj).begin(),(obj).end()
#define SETP(n)      cout<<fixed<<setprecision(n)
#define VV(T,h,w)    move(vector<vector<T>>(h,move(vector<T>(w))))
#define VVI(T,h,w,i) move(vector<vector<T>>(h,move(vector<T>(w,i))))
using namespace std;
using ll = long long;
template<typename T = ll>inline T in() { T ret; cin >> ret; return ret; }

int main()
{
	ll 	a = in(), b = in(), c = in();
	if (b >= c - 1 || a + b >= c - 1) {
		cout << b + c << endl;
	} else {
		cout << a + 2 * b + 1 << endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <vector>
#include <string>
#include <string.h>
#include <iomanip>
#include <limits>
typedef long long ll;
using namespace std;
const int INF=1e9, MOD=1e9+7;
const int MAX_N=10000;
int n,a;

int main(){
	cin >> n >> a;
	
	cout << n*n-a << endl;
	return 0;
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[9999999][3]={};

ll max3(ll a,ll b,ll c){
    return max(a,max(b,c));
}

int main(){
    int n;
    cin >> n;
    vector<int> a(n),b(n),c(n);

    for(int i = 0; i < a.size();i++){
        cin >> a[i] >> b[i] >> c[i];
    }

    for(int i=0; i <n;i++){
        dp[i+1][0] = max(dp[i][1],dp[i][2])+a[i];
        dp[i+1][1] = max(dp[i][0],dp[i][2])+b[i];
        dp[i+1][2] = max(dp[i][0],dp[i][1])+c[i];
    }

    cout << max(dp[n][0],max(dp[n][1],dp[n][2])) << endl;
    
}

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

#define int long long

int ans;

signed main () {

    int n, k;
    cin >> n >> k;
    for ( int i = k+1; i <= n; i++ ) {
        ans += ( i-k ) * ( n/i );
        ans += max(0ll, n%i-k+1);
    }
    if ( k == 0 ) ans -= n;

    cout << ans << endl;

    return 0;
}

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

import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

l = 1
for i in range(n):
    l = lcm(l, a[i])

ans = 0
for i in range(n):
    ans += (l - 1) % a[i]

print(ans)

Measured memory_bytes: 9312
N = int(input())
h = list(map(int,input().split()))
inf = float("inf")

dp = [inf]*N
dp[0] = 0 #initial situation
dp[1] = abs(h[1]-h[0])


for i in range(2,N):
	dp[i] = min(dp[i-1] + abs(h[i]-h[i-1]), dp[i-2] + abs(h[i]-h[i-2]))

print(dp[N-1])



Measured memory_bytes: 13928
#include<iostream>
#include<algorithm>
#include<cmath>
typedef long long ll;
using namespace std;
int main() {
	int n, k;
	cin >> n >> k;
	ll ans=k;
	for (int i = 1; i < n; i++) {
		ans = ans * (k - 1);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stdio.h>
#include <cmath>
#include <cctype>
#include <map>

const int INT_INF = 1000000000;                 // 10^9
const long long LONG_INF = 1000000000000000000; // 10^18

using namespace std;

int main()
{
    int x;
    cin >> x;
    if (x % 2 == 0 && x != 2)
    {
        x++;
    }

    while (true)
    {
        bool f = true;
        for (int i = 3; i <= floor(sqrt(x)); i++)
        {
            if (x % i == 0)
            {
                f = false;
                break;
            }
        }
        if (f)
            break;
        x += 2;
    }

    cout << x << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;


		       public class Main {

		           public static void main(String args[])  {
		        	   Scanner sc =new Scanner(System.in);
		        	   long start =sc.nextLong();
		        	   long parm = sc.nextLong();
		        	   long remainder = start%parm;
		        	   System.out.println(Math.min(remainder,Math.abs(remainder -parm)));
		        	   
		        	   
		           }
		       }


Measured memory_bytes: 21844
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int f(int x){
	return pow(x,2);
}

int main(){
	int	input(0);
	int N(600);
	int s(0);
	while(cin >> input){
		for (int i = 1; i < N / input -1; i++){
			s += f(input * i) * input;
		}
    s += f(N -input) * input;
	cout << s << endl;
        s= 0;

	}
}

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

int main(void) {
    int K; cin >> K;
    int A,B; cin >> A >> B;
    for(int i=A; i<=B; i++) {
        if(i%K==0) {
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;
    return 0;
}

Measured memory_bytes: 3592
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int num[] = new int[n];
        double ave = 0;
        for(int i = 0; i < n; i++){
        	num[i] = sc.nextInt();
            ave += num[i];
        }
        ave = ave / n;
        double min = Math.abs((double)num[0] - ave);
        int ans = 0;
        for(int i = 1; i < n; i++){
            double difnum = Math.abs((double)num[i] - ave);
        	if(min > difnum){
            	min = difnum;
                ans = i;
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 35932
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int f,q,x;

  string s,l,r;

  map<string,int>m;
  map<string,int>::iterator it1,it2;
  cin>>q;
  while(q--){
    cin>>f;

    if(f==0){
      cin>>s;
      cin>>x;
     m[s]=x;

    }
    else if(f==1){
      cin>>s;
      if(m.count(s))
        cout<<m[s]<<endl;
        else
          cout<<0<<endl;

    }
    else if(f==2){
      cin>>s;
      m.erase(s);
    }

    else{
      cin>>l>>r;
      it1=m.lower_bound(l);
      it2=m.upper_bound(r);
      for(;it1 !=it2;it1++)
        cout<<(*it1).first<<' '<<(*it1).second<<endl;
    }
  }
return 0;
}


Measured memory_bytes: 27668
A,B,N = map(int,input().split())
S = 0
n = N // B
r = N % B
if B > N:
    S = (A*N)//B
else:
    if  r == 0:
        S = (A*(N-1))//B - A * ((N-1)//B)
    elif r == B - 1:
        S = (A*N)//B - A * (N//B)
    else:
        S = (A*(n*B-1))//B - A * ((n*B-1)//B)

print(S)


Measured memory_bytes: 8908
//Code By PMD
#include<bits/stdc++.h>
#define faster() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long i64;
typedef pair <int,int> pii;
int n , cnt = 0;
vector < pii > a;
vector < int > x;
vector < bool > vis;
double res = 0.0;
double range(pii a , pii b ){
    int x = (a.first - b.first);
    int y = (a.second - b.second);
    return sqrt(x*x + y*y);
}
void input(){
    cin >> n;
    a.resize(n);
    x.resize(n+1);
    vis.assign(n+1,false);
    for(int i = 0 ; i < n ; i++){
        cin >> a[i].first >> a[i].second;
    }
}
void update(){
    cnt++;
    for(int i = 1 ; i < n ; i++){
        res += range(a[x[i]-1],a[x[i+1]-1]);
    }
}
void Try(int i){
    for(int j = 1; j <= n ; j++){
        if ( vis[j] == false){
            x[i] = j;
            vis[j] = true;
            if ( i == n )
                update();
            else Try(i+1);
            vis[j] = false;
        }
    }
}
void solve(){
    Try(1);
    printf("%.9lf",res/cnt);
}
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    faster();int t=1; 
    //cin>>t; cin.ignore();
    while(t--){ input();solve();}
    cerr << "\nRunning is : " << 1.0*clock()/1000 ;
    return 0;
}
//Code By PMD
 

Measured memory_bytes: 256
from math import log2
x, y = map(int, input().split())
k = int(log2(y)-log2(x)+1)
n =x*2**(k-1)
if n <= y:
    if 2*n <= y:
        print(k+1)
    else:
        print(k)
else:
    print(k-1)


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

int main() {

    int n;
    int a = 1;
    int comb[10][10];

    for(int i = 0; i < 10; ++i)
        for(int j = 0; j < 10; ++j)
        comb[i][j] = 0;


    cin >> n;


    for(int i = 1; i <= n; ++i) {

        int under = i % 10;

        if(a * 10 <= i)
            a *= 10;

        int top = i / a;
        comb[top][under]++;


    }

    long long int sum = 0;
    for(int i = 0; i < 10; ++i) {
        for(int j = 0; j < 10; ++j) {
            sum += comb[i][j] * comb[j][i];

        }
    }


    cout << sum << endl;

    return 0;


}

Measured memory_bytes: 256
// Ver19.02
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF 1 << 29
#define LLINF 4545454545454545454
#define MOD 1000000007
#define ll long long
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int upll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? -1 : *(ll *)a > *(ll *)b ? 1 : 0; }
int downll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? 1 : *(ll *)a > *(ll *)b ? -1 : 0; }
void sortup(ll *a, int n) { qsort(a, n, sizeof(ll), upll); }
void sortdown(ll *a, int n) { qsort(a, n, sizeof(ll), downll); }

int main()
{
  int a, b;
  scanf("%d%d", &a, &b);
  if (a + b < 10)
    printf("%d\n", a + b);
  else
    puts("error");

  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
int main(){ 
    int a;
    cin>>a;
    if(a==3||a==5||a==7){
        cout<<"YES";
    }else{
        cout<<"NO";
    }
    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15


def main():
    n = getN()
    po = 1
    while(n > 1):
        po += 1
        n = n//2

    print(2**po - 1)


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Measured memory_bytes: 38384
#include <bits/stdc++.h>
#define ms(x, n) memset(x,n,sizeof(x));
#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define rep1(i, n) for(int i = 1; i <= (int)n; ++i)
#define pb push_back
#define PI acos(-1.0)
#define LONG_LONG_MAX 9223372036854775807
#define LONG_LONG_MIN -9223372036854775808
typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;

int a;
string s;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> a;
    cin >> s;
    if (a < 3200) cout << "red" << endl;
    else cout << s << endl;
    return 0;
}


Measured memory_bytes: 256
import numpy as np
n = int(input())
d = np.array([input().split() for i in range(n)])

for i in range(n - 2):
    if d[i, 0] == d[i, 1] and d[i + 1, 0] == d[i + 1, 1] and d[i + 2, 0] == d[i + 2, 1]:
        print("Yes")
        exit()

print("No")

Measured memory_bytes: 27080
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <iomanip>
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const ll MOD=1000000007;
const ll MAX_N=500010;
const ll INF=999999999999;
ll fac[2010];

ll modpow(ll a, ll b){
    ll res=1;
    while(b>0){
        if(b&1) res=res*a%MOD;
        a=a*a%MOD;
        b=b>>1;
    }
    return res;
}

ll comb(ll n, ll r){
    ll res=1;
    res*=fac[n];
    res*=modpow(fac[r],MOD-2);
    res%=MOD;
    res*=modpow(fac[n-r],MOD-2);
    res%=MOD;
    return res;
}
int main(){
    ll n,k;
    cin>>n>>k;
    fac[0]=1;
    for(ll i=1;i<2010;i++){
        fac[i]=fac[i-1]*i%MOD;
    }
    for(ll i=1;i<=k;i++){
        ll ans=0;
        for(ll j=0;j<=n-k-i+1;j++){
            ans+=comb(k-1,i-1)*comb(j+i-1,j)%MOD;
            ans%=MOD;
        }
        cout<<ans<<endl;
    }
    return 0;
}

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

#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
// #define int long long
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using ul = unsigned long;

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

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }
ll LCM(ll a, ll b) { return a * b / GCD(a, b); }

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

inline bool inside(int y, int x, int H, int W) {
    return (y >= 0 && x >= 0 && y < H && x < W);
}

ll dp[101][200005];

int main(){
  int n,w; cin>>n>>w;
  vector<ll> W(n), V(n);
  rep(i,n) cin>>W[i]>>V[i];
  
  ll inf=1e11+1;
  rep(i,n+1) for(int j=0; j<=200005; j++) dp[i][j]=inf;
  rep(i,n+1) dp[i][0]=0;
  
  rep(i,n){
    for(int j=0; j<=100000; j++){
      if(dp[i][j]+W[i]<=w) dp[i+1][j+V[i]]=min(dp[i][j+V[i]], dp[i][j]+W[i]);
      chmin(dp[i+1][j], dp[i][j]);
    }
  }
  int ans=0;
  for(int i=100000; i>=0; i--) if(dp[n][i]!=inf) {
    ans=i;
    break;
  }
  cout<<ans<<endl;
}
 

Measured memory_bytes: 158080
H,n = map(int,input().split())
A = [0 for _ in range(n)]
B = [0 for _ in range(n)]
min_eff = 9999.
for i in range(n):
    A[i],B[i] = map(int,input().split())
    min_eff = min(min_eff,A[i]/B[i])

dp = [[int(H/min_eff+1) for _ in range(H+1)] for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0


for i in range(n):
    for h in range(H+1):
        idx = max(0,h-A[i])
        dp[i+1][h] = min(dp[i+1][idx] + B[i],dp[i][h])

print(int(dp[n][H]))


Measured memory_bytes: 125276
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
const ll MOD = 1000000007;

int main() {
    int k, x;
    cin >> k >> x;
    for (int i = x-k+1; i < x+k; i++)
        cout << i << " ";
    cout << endl;
}

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

const ll MOD = 1000000007;

string l;
int n;

ll modpow(ll x, ll n){
    ll res = 1;
    ll mul = x;
    while(n){
        if(n % 2) res = res * mul % MOD;
        mul = mul * mul % MOD;
        n /= 2;
    }
    return res;
}

ll ans(int i){
    if(i == n) return 1;
    if(l[i] == '0') return ans(i + 1);
    return (modpow(3, n - i - 1) + 2 * ans(i + 1)) % MOD;
}

int main()
{
    cin >> l;
    n = l.size();
    cout << ans(0) << endl;
}

Measured memory_bytes: 3584
T=input()
list=[]
for j in range(len(T)):
    if T[j]=="?":
        list.append(j)
tt=[]
for TT in range(len(T)):
    tt.append(T[TT])
for i in list:
    tt[i]="D"
answer=""
for p in range(len(T)):
    answer+=tt[p]
print(answer)

Measured memory_bytes: 18648
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###
import time

# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

N, A, B, C = mi()

MOD = 10**9+7
a = (A * modinv(A+B, MOD)) % MOD
b = (B * modinv(A+B, MOD)) % MOD
gyakugenofAB = (100 * modinv(A+B, MOD)) % MOD

# 累乗を返すリスト
#[0]行にはaの階乗を、[1]行にはbの階乗を入れる
powlist = [[-1] * (N+1) for _ in range(2)]
preA = 1
preB = 1
powlist[0][0] = 1
powlist[1][0] = 1
for i in range(1,N+1):
  preA = (preA * a) % MOD
  preB = (preB * b) % MOD
  powlist[0][i] = preA
  powlist[1][i] = preB


#cmb(m)でmCn-1を計算
import math
Nmin1fct = modinv(math.factorial(N-1),MOD) % MOD

#一度でも計算したらflagがオン
flag = 0
preans = 1
def cmb(k):
  global flag
  global preans
  ans = 1
  if flag == 0:
    flag = 1
    for i in range(max(1,k-1),k-N,-1):
      ans = (ans * i) % MOD
    preans = (ans * Nmin1fct) % MOD
    return preans
  else:
    preans = (preans * (k-1) * modinv(max(1, k-N),MOD)) % MOD
  return preans
#cmbの計算終わり


#期待値（確率×回数）を足し上げていく。
#N回目～2N-1回目についてループを回す
#m-1Cn-1なことに注意
e = 0
cnt = 0
for m in range(N, 2*N):
#  cnt += 1
#  if cnt % 1000 == 0: print(cnt)
#  start_time = time.perf_counter()
  e += (m * gyakugenofAB * (cmb(m) % MOD) * ((powlist[0][N] * powlist[1][m-N]) + (powlist[0][m-N] * powlist[1][N])))
  e %= MOD
#  print(time.perf_counter() - start_time)


print(e)


Measured memory_bytes: 95832
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 1000000000000000
int n,l,q,x[100005],p[100005][18];
int main(void){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
		scanf("%d",x+i);
	}
	scanf("%d",&l);
	for(int i=0;i<n;i++){
		p[i][0]=upper_bound(x,x+n,x[i]+l)-x-1;
	}
	for(int i=0;i+1<18;i++){
		for(int j=0;j<n;j++){
			p[j][i+1]=p[p[j][i]][i];
		}
	}
	scanf("%d",&q);
	while(q--){
		int a,b;
		scanf("%d%d",&a,&b);
		a--,b--;
		if(b<a)swap(a,b);
		int ans=1;
		for(int i=17;i>=0;i--){
			if(p[a][i]<b){
				ans+=(1<<i);
				a=p[a][i];
			}
		}
		printf("%d\n",ans);
	}
}


Measured memory_bytes: 8192
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,c,b[22][22],a[22],ans;
int main(){
    scanf("%d %d %d",&n,&m,&c);
    for(int i=1;i<=m;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        int sum = c;
        for(int j=1;j<=m;j++){
            int b;
            scanf("%d",&b);
            sum+=a[j]*b;
        }
        if(sum>0) ans++;
    }
    printf("%d",ans);
}


Measured memory_bytes: 256