akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <string>
#include <stdlib.h>
#include<vector>
#include<iostream>
#include<set>
#include<map>
#include<algorithm>
using namespace std;




int main() {
	int n,m;
	cin >> n >> m;
	
	vector<char> res(n,'.');
	
	bool f = true;
	for(int i=0;i<m;++i){
		int s;
		char c;
		cin >> s >> c;
		s--;
		if(res[s] != '.' && res[s] != c){
			f = false;
			//cout << res[s] << " " << s << " " << c <<endl;
		}
		//cout << s << " " << c <<endl;
		res[s] = c;
	}
	
	for(int i=0;i<n;++i){
		if(res[i] == '.' && i==0 && n!=1) res[i] = '1';
		else if(res[i] == '.') res[i] = '0';
		//cout << res[i] << " " <<endl;
	}
	
	
	if(f== false || (res[0] == '0' && n!=1)){
		cout << -1 <<endl;
		return 0;
	}
	
	for(int i=0;i<n;++i){
		cout << res[i];
	}cout <<endl;
	
	
	
	
    return 0;
}


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

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (int)(m); i < (int)(n); ++i)


int main()
{
    string s;
    cin >> s;

    int n = s.size();

    // 木が構築できるかどうか
    bool can_build = true;
    if(s[0] == '0' or s[n-1] == '1') can_build = false;
    REP(i, n-1){
        if(s[i] != s[n-i-2]) can_build = false;
    }

    // 具体的な木の構築
    vector<int> G(n-1);  // G[i]: i の親
    int root = 1, child = 0;
    while(root < n){
        while(root < n-1 and s[root] == '0') ++root;
        FOR(i, child, root) G[i] = root;
        child = root;
        ++root;
    }

    // output the answer
    if(can_build) REP(i, n-1) cout << i+1 << " " << G[i]+1 << endl;
    else cout << -1 << endl;

    return 0;
}

Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll N, A, B, C, D;
bool iscov(ll i1, ll i2, ll j1, ll j2) {
    assert(i1 <= i2);
    assert(j1 <= j2);
    if (i1 > j1) {
        swap(i1, j1);
        swap(i2, j2);
    }
    return j2 <= i2;
}
int main () {
    cin >> N >> A >> B >> C >> D;
    const ll K = N - 1;

    for(int i = 0; i <= K; ++i) {
        int j = K - i;
        ll up = i * D - j * C;
        ll low = i * C - j * D;
        if (A + up < B) continue;
        if (A + low > B + D) break;
        if (
            B >= A + low && B <= A + up
        ) {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
}

Measured memory_bytes: 256
gets.to_i
line = gets.split.map(&:to_i)
max = line.max
ary = Array.new(max + 1, 0)

line.each { |l| l.step(max, l) { |n| ary[n] += 1 } }

puts line.count { |i| ary[i] == 1 }

Measured memory_bytes: 35328
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <map>
#include <tuple>
#include <iostream>
#include <deque>
#include <array>
#include <set>
#include <functional>
#include <memory>
#include <stack>
#include <numeric>
#include <climits>
#include <cfloat>
#include <bitset>
int gcd(const int a, const int b) {
	if (b == 0) return a;
	else gcd(b, a % b);
}

int main() {
	int a, b, c; std::cin >> a >> b >> c;
	if (c % gcd(a, b) == 0) std::cout << "YES\n";
	else std::cout << "NO\n";
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
mod = 1000000007

N = int(input())
S1 = input().rstrip()
S2 = input().rstrip()

# 探索済みかどうかの管理
s = set()

# 答え
ans = 1

if S1[0] == S2[0]:
    ans *= 3
    ans %= mod
    s.add(S1[0])
else:
    ans *= 3 * 2
    ans %= mod
    s.add(S1[0])
    s.add(S2[0])

for i in range(1, N):
    # タテ
    if S1[i] == S2[i]:
        if S1[i - 1] == S2[i - 1]:
            ans *= 2
            ans %= mod
        s.add(S1[i])
    
    # ヨコ
    elif S1[i] not in s and S1[i - 1] == S2[i - 1]:
        ans *= 2
        ans %= mod
        s.add(S1[i])
        s.add(S2[i])
    elif S1[i] not in s:
        ans *= 3
        ans %= mod
        s.add(S1[i])
        s.add(S2[i])

print(ans)

Measured memory_bytes: 3192
#include <bits/stdc++.h>
#define int long long
#define ll long long 
#define rep(i,a,b) for(signed i=a;i<(b);++i)
#define erep(i,a,b) for(signed i=a;i<=(b);++i)
#define per(i,a,b) for(signed i=(a);i>(b);--i)
#define eper(i,a,b) for(signed i=(a);i>=b;--i)
#define fore(i, x, a) for(auto &&x:a) 
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define pb emplace_back
#define mp make_pair
#define ALL(x) begin(x),end(x)
#define F first
#define S second
#define debug(x)  cout << #x << ": " << (x) << '\n';
const long long INF=1001001001001001001;
const int MOD=(int)1e9 + 7;
const double EPS=1e-9;
using namespace std;
using Pii = pair<int,int>;
using vii = vector<int>;
template<class T>using  PS_queue = priority_queue<T, vector<T>, greater<T> >;
template<class T>using vv = vector<T>;
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; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val){fill( (T*)array, (T*)(array+N), val );}
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T>T gcd(T a, T b){ return b ? gcd(b, a % b) : a; }
template<class T>T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct edge { int from, to, cost; };
int dy[]={0, 1, -1, 0}; int dx[]={1, 0, 0, -1};
// cout << fixed;
// cout << setprecision(10) << val;

int r, d, x;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
  cin >> r >> d >> x;
  rep(i, 0, 10) {
    x = x * r - d;
    cout << x << endl;
  }
  return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[107],b[107];
ll dp[2][100007];
int n,k;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
	int cur=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=k;j++)
		{
			dp[cur][j]=dp[1-cur][j];
			if(a[i]<=j) dp[cur][j]=max(dp[cur][j],dp[1-cur][j-a[i]]+b[i]);
		}
		cur=1-cur;
	}
	cout<<dp[n%2][k];
}

Measured memory_bytes: 5196
#include<bits/stdc++.h>
using namespace std;
#define max(a,b) ((a>b)?a:b);
#define min(a,b) ((b>a)?a:b);
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define pu push
#define pp pop_back
#define in insert
#define forn(low,high,i) for(i=low;i<high;i++)
#define forrev(high,low,i) for(i = high; i>= low;i--)                                 //g++ atc2.cpp -o atc2.exe
#define zeroes(x) memset(x,0,sizeof(x))                                        //all elements to 0
#define all(x) (x).begin(), (x).end()
typedef long long int ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
const ll mod =1e9+7;
const ll maxn=100000;







bool sortbysec(const pair<int,int> &a,                         //sorting of elements wrt second
              const pair<int,int> &b) 
{ 
    return (a.second < b.second); 
} 




int main()
{
	
long long int n,i,sum=0;
cin>>n;
char ch;
vector <char> v;
cin>>ch;
	v.push_back(ch);

for( i=1;i<n;i++)
{
	
	
	cin>>ch;
	v.push_back(ch);

		if(v[i]==v[i-1])
			sum++;
		
	
}
cout<<n-sum;

return 0;
}

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

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

    int h[n];
    for(int i=0; i<n; i++) cin>>h[i];

    int d[n];
    for(int i=0; i<n; i++) d[i]=1e9+5;
    d[0]=0;

    for(int i=0; i<n; i++){
        int j=i+1;
        int k=i+2;
        if(j<n) d[j] = min(d[j], d[i]+abs(h[i]-h[j]));
        if(k<n) d[k] = min(d[k], d[i]+abs(h[i]-h[k]));
    }

    cout<<d[n-1];
}


Measured memory_bytes: 1024
public class Hello {
    public static void Main(){
        // 1行に複数の入力値がある場合の例
        string [] inputs = System.Console.ReadLine().Split(' ');
        int a = int.Parse(inputs[0]);
        int b = int.Parse(inputs[1]);
        int c = (a * b);
        int d = (a + b) * 2;
        System.Console.WriteLine(c + " " + d);
    }
}



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

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  
  for (int i = 0; i < N; i++) {
    cin >> a.at(i);
    a.at(i)--;
  }
  
  int A = 0;
  int p = 0;
  
  for (int i = 0; i < N; i++) {
    if(a.at(p)==0){
      cout << "-1" << endl;
      break;
    }
    
    if(a.at(p)==1){
      cout << A + 1 << endl;
      break;
    }
    
    else{
      p = a.at(p);
      A++;
    }
    if(i==N - 1){
    cout << "-1" << endl;
    }
  }

}

Measured memory_bytes: 640
a,b=map(int,input().split(" "))
if a==1:
    i1=[]
    

    for n in range(0,b):
        x,y =map(int,input().split(" "))
        if x==1:
            i1.append(y)
    i1=list(set(i1))
    if len(i1)>1:
        print(-1)
    else:
        n1=0
        if len(i1)>0:
            for con1 in  i1:
                n1=con1
        print(n1)
elif a==2:
    i1=[]
    i10=[]

    for n in range(0,b):
        x,y =map(int,input().split(" "))
        if x==1:
            i10.append(y)
        else:
            i1.append(y)
    i10=list(set(i10))
    i1=list(set(i1))
    if len(i1)>1 or len(i10)>1:
        print(-1)
    else:
        n1=0
        n10=1
        if len(i1)>0:
            for con1 in  i1:
                n1=con1
        if len(i10)>0:
            for con1 in  i10:
                n10=con1
        if i10==0:
            print(-1)
        else:
            print(n10*10+n1)

elif a==3:
    i1=[]
    i10=[]
    i100=[]

    for n in range(0,b):
        x,y =map(int,input().split(" "))
        if x==1:
            i100.append(y)
        elif x==2:
            i10.append(y)
        else:

            i1.append(y)
    i100=list(set(i100))
    i10=list(set(i10))
    i1=list(set(i1))
    #print(i100)
    #print(i10)
    #print(i1)
    if len(i1)>1 or len(i10)>1 or len(i100)>1:
        print(-1)
    else:
        n1=0
        n10=0
        n100=1
        if len(i1)>0:
            for con1 in  i1:
                n1=con1
        if len(i10)>0:
            for con1 in  i10:
                n10=con1
        if len(i100)>0:
            for con1 in  i100:
                n100=con1
        if n100==0:
            print(-1)
        else:
            print(n100*100+n10*10+n1)




#print(max(m_l))


Measured memory_bytes: 3192
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define V vector<int>
#define ll long long
using namespace std;


int main() {
    int N; cin >> N;
    V a(3*N);
    rep(i, 0, 3*N) cin >> a[i];

    sort(a.begin(),a.end(),greater<>());

    ll ans = 0;
    
    for(int i = 1; i < 2*N; i+=2){
        ans += a[i];
    }

    cout << ans << "\n";

}

Measured memory_bytes: 1408
#include <stdio.h>
#include <math.h>

int main(void) {
	int n;
	while (scanf("%d", &n) == 1 && n != 0) {
		double s[1024];
		int i;
		double average = 0, sd = 0;
		for (i = 0; i < n; i++) {
			if (scanf("%lf", &s[i]) != 1) return 1;
			average += s[i];
		}
		average /= n;
		for (i = 0; i < n; i++) {
			sd += (s[i] - average) * (s[i] - average);
		}
		printf("%.15f\n", sqrt(sd / n));
	}
	return 0;
}



Measured memory_bytes: 2036
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<list>
#include <array>
using namespace std;
#define i64  long long
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807
#define INF I64_MAX
#define MOD 1000000007


 int f[10000000] = {0}; 

// 繰り返し二乗法 O(log n)

int MOD_pow(int x, int n){
    int res = 1LL;
    while(n > 0){
        if(n & 1) res = res * x % MOD;
        x = x*x % MOD;
        n >>= 1;
    }
    return res;
}

int MOD_inv(int x){
    return MOD_pow(x, MOD-2) % MOD;
}

// nCr % mod
int comb(int n, int r){
    return (((f[n] * MOD_inv(f[r])) % MOD) * MOD_inv(f[n-r])) % MOD;
}

void chmod(int &M){
    if(M >= MOD) M %= MOD;
    else if(M < 0){
        M += (abs(M)/MOD + 1)*MOD;
        M %= MOD;
    }
}
void solve(void)
{
  int H,W,A,B;
  cin>>H>>W>>A>>B;
  H--;
  W--;
    f[0] = f[1] = 1;
    for(int i=2; i<=H+W; ++i) f[i] = (i * f[i-1]) % MOD;
  // cout<<comb(4,2)<<endl;

  int P = 1, Q = comb(H+W-B,W-B);
  // cout<<Q<<endl;
  int ANS = 0;
  int I_P,I_Q;
  int I_A,I_B;
  I_A = H + W - B;
  for (int i = 0; i < H - A + 1; i++)
  {
    // cout<<Q<<endl;
    
    // ANS = (ANS + P*Q%MOD);
    // // cout<<P<<" "<<Q<<endl;
    // // cout<<ANS<<endl;
    // P = P*(B+1+i-1)/(i+1)%MOD;
    // Q = Q*2%MOD;
    // Q = Q/I_A;
    // I_A--;
    // Q = Q*(I_A - W + B + 1)%MOD;
    // Q = Q/2;
    // if(Q==0)break;
    // // cout<<ANS<<endl;
    ANS = (ANS + comb(B+i - 1,i)*comb(H + W - B - i , W - B ));
    // cout<<ANS<<endl;
    chmod(ANS);

    // cout<<ANS<<endl;
  }
  

    cout<<ANS;

  return;
}



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

  // std::cout << std::fixed;
  // std::cout << std::setprecision(8);

  solve();

 
  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>  // clang-format off
using namespace std;
using Int = long long;
#define REP_(i, a_, b_, a, b, ...) for (int i = (a), lim_i = (b); i < lim_i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
struct SetupIO { SetupIO() { cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(13); } } setup_io;
#ifndef _MY_DEBUG
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Fri Mar 20 14:54:46 JST 2020
 **/

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

signed main() {
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<Int> a(n), b(n), c(n);
    REP(i, n) cin >> a[i];
    REP(i, n) cin >> b[i];
    REP(i, n) c[i] = a[i] - b[i];
    dump(c);
    Int ans = 0;
    vector<Int> acc(n);
    auto dfs1 = [&](auto f, Int v, Int prv) -> void {
        acc[v] = c[v];
        for (Int s : g[v]) {
            if (s == prv) continue;
            f(f, s, v);
            acc[v] += acc[s];
        }
    };
    dfs1(dfs1, 0, -1);
    assert(acc[0] == 0);

    Int mi = 0;
    vector<Int> xs(n);
    auto dfs2 = [&](auto f, Int v, Int prv) -> void {
        for (Int s : g[v]) {
            if (s == prv) continue;
            xs[s] = xs[v] + acc[s];
            chmin(mi, xs[s]);
            f(f, s, v);
        }
    };
    dfs2(dfs2, 0, -1);
    dump(mi, xs);
    cout << -mi * n + accumulate(xs.begin(), xs.end(), 0LL) << endl;
}



Measured memory_bytes: 16136
#include<iostream>

using namespace std;

int main(void)
{
	long long n,k;
	cin >> n >> k;

	long long ans=0;
	ans+=(n/k)*(n/k)*(n/k);
	if(k%2==0)
	{
		long long x = n/(k/2)-n/k;
		ans+=x*x*x;
	}
	cout << ans << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define WHATIS(x) cout << #x << " is " << x << endl;
#define ERROR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<ll, II> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a << endl;
    err(++it, args...);
}

const ll MODBASE = 1000000007LL;
const int MAXN = 400010;
const int MAXM = 100010;
const int MAXK = 510;
const int MAXQ = 200010;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int x, y;
  cin >> x >> y;
  cout << x + y / 2;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

string s;
int main() {
	cin >> s;
	
	int ans=1;
	string lst=s.substr(0, 1);
	int i=1;
	while (i<s.size()) {
		if (s.substr(i,1)!=lst) {
			lst=s.substr(i,1);
			ans++;
			i++;
		} else {
			if (i+2>s.size()) break;
			lst=s.substr(i,2);
			ans++;
			i+=2;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 640
// abc165_e
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

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

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;


int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int N, M;
    cin >> N >> M;

    if (N % 2 == 0) N--;

    vector<P> ans;

    int odd = ((N/2 + 1) / 2) * 2 - 1; // 奇->そのまま、遇->遇-1
    int idx = 1;
    for (int i = odd; i >= 1; i -= 2) {
        ans.emplace_back(idx, idx + i);
        idx++;
    }

    int even = ((N/2) / 2) * 2; // 奇->奇-1、遇->そのまま
    idx = odd + 2;
    for (int i = even; i >= 2; i -= 2) {
        ans.emplace_back(idx, idx + i);
        idx++;
    }

    REP(i, M){
        print(ans[i].first, ans[i].second);
    }

    return 0;
}


Measured memory_bytes: 4188
#include <iostream>
#include <stdio.h>

using namespace std;
typedef long long ll;


int main(){
    int M,N,X;
    cin>>N>>M>>X;
    
    ll C[N];
    ll A[N][M];
    ll Al_SUM[M];
    
    ll C_SUM=0;
    ll min;
    ll min_inf;

    
    for(int i=0;i!=N;++i){
        cin>>C[i];
        for(int j=0;j!=M;++j){
            cin>>A[i][j];
        }
    }
    
    for(int i=0;i!=M;++i) Al_SUM[i]=0;
    for(int i=0;i!=N;++i) min_inf+=C[i];
    min=min_inf;
   /*
    for(int i=0;i!=N;++i){
        for(int j=0;j!=M;++j){
            cout<<"A["<<i<<"]["<<j<<"]"<<A[i][j]<<" ";
        }
    }
    cout<<endl;
    */
    
    
    for(int bit=0;bit<(1<<N);++bit){

        for(int i=0;i<N;++i){        //iは本の冊数
            if(bit&(1<<i)){
                for(int j=0;j!=M;++j){
                    Al_SUM[j]+=A[i][j];
                    //cout<<"Al_SUM["<<j<<"]:"<<Al_SUM[j]<<endl;
    
                }
                C_SUM+=C[i];
                //cout<<C_SUM<<endl;
            }
        }
        //for(int i=0;i!=M;++i)cout<<"Al_SUM["<<i<<"]:"<<Al_SUM[i]<<endl;
        bool ok=true;
        for(int j=0;j!=M;++j){
            if(Al_SUM[j]<X){
                ok=false;
                //cout<<flag<<endl;
                break;
            }else{
                
            }
        }
        if(ok){
        min=(C_SUM<min)?C_SUM:min;
        }
        for(int j=0;j!=M;++j)Al_SUM[j]=0;
        C_SUM=0;
    }
    
    //cout<<"flag:"<<flag<<endl;
    
    if(min!=min_inf){
        cout<<min<<endl;
       
    }else{
         cout<<-1<<endl;
    }
    
}



Measured memory_bytes: 3632
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (int64_t)(n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

#define chmax(a, b) (a) = max(a, b)

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

  using P = pair<int, int>;
  vector<P> a(N);
  rep(i, N) {
    int v;
    cin >> v;
    a[i] = P(v, i);
  }

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

  vector<vector<int64_t>> dp(
      N + 1, vector<int64_t>(N + 1, -1'000'000'000LL * 2'000 * 2'000));
  dp[0][0] = 0;
  for (int i = 1; i <= N; i++) {
    int v, idx;
    tie(v, idx) = a[N - i];
    irep(j, i) {
      if (i - 1 - j >= 0) {
        chmax(dp[i][j],
              dp[i - 1][j] + (int64_t)v * (N - 1 - (i - 1 - j) - idx));
      }
      if (j - 1 >= 0) {
        chmax(dp[i][j], dp[i - 1][j - 1] + (int64_t)v * (idx - (j - 1)));
      }
    }
  }

  int64_t result = 0;
  irep(i, N) { chmax(result, dp[N][i]); }
  cout << result << endl;

  return 0;
}

Measured memory_bytes: 34380
main = getContents >>= putStr.formatOut.map calc.formatIn

formatIn :: String -> [[Int]]
formatIn = map ((map toInt).words).takeWhile (/="0 0").lines
  where toInt =read :: String -> Int

formatOut :: [String] -> String
formatOut = unlines

calc :: [Int] -> String
calc (h:w:_) = unlines $map ((take w).draw) [1..h] 
  where draw n | n `mod` 2 == 1 = cycle ['#','.']
               | otherwise      = cycle ['.','#']

Measured memory_bytes: 5160
#include <bits/stdc++.h>
// statics
using namespace std;
using int64 = long long;
using PAIR = pair<int64, int64>;
constexpr int INF = 1 << 30;
constexpr int64 LINF = 1LL << 60;
constexpr int MOD = 1e9 + 7;
constexpr int MAX_N = 3e5 + 1;

// init/input
#define int int64
#define INIT ios::sync_with_stdio(false);cin.tie(0);
#define VAR(type, ...) type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T &t) {cin>>t;}
template<typename First, typename...Rest> void MACRO_VAR_Scan(First &first, Rest&...rest) {cin>>first;MACRO_VAR_Scan(rest...);}
#define VEC(type, c, n) vector<type> c(n);for(auto &&i:c)cin>>i;

// out
#define OUT(dist) cout<<(dist);
#define FOUT(n, dist) cout<<fixed<<setprecision(n)<<(dist);
#define SP cout<<" ";
#define BR cout<<endl;
#define zero(n) cout<<setfill('0')<<right<<setw(n)
#define debug(x) cerr<<#x<<":"<< (x);BR;

// utility
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, a) for(auto &&i:(a))
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)
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; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

signed main() {
  INIT;

  VAR(string,s);
  map<int,int> mp;
  vector<int> a(s.size(),0);
  REP(i,s.size()){
    a[i]=s[i]-97;
    mp[s[i]-97]++;
    //debug(s[i]-97);
  }

  int ans = INF;
  EACH(mi,mp){
    int i = mi.first;
    // iにする
    vector<int> b(a);
    bool ng = true;
    int cnt = 0;
    while(ng){
      bool ok = true;
      REP(j,b.size()-1){
        ok &= b[j+1]==b[j];
      }
      if(ok) {
        ng=false;
        continue;
      }
      REP(j,b.size()){
        if(b[j+1]==i || b[j]==i){
          b[j]=i;
        }
      }
      b.pop_back();
      ++cnt;
    }
    //debug(i);
    //debug(cnt);
    ans = min(ans,cnt);
  }
  OUT(ans)BR;
  
  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int man = 2e5+10;
#define IOS ios::sync_with_stdio(0)
template <typename T>
inline T read(){T sum=0,fl=1;int ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')fl=-1;
for(;isdigit(ch);ch=getchar())sum=sum*10+ch-'0';
return sum*fl;}
template <typename T>
inline void write(T x) {static int sta[35];int top=0;
do{sta[top++]= x % 10, x /= 10;}while(x);
while (top) putchar(sta[--top] + 48);}
template<typename T>T gcd(T a, T b) {return b==0?a:gcd(b, a%b);}
template<typename T>T exgcd(T a,T b,T &g,T &x,T &y){if(!b){g = a,x = 1,y = 0;}
else {exgcd(b,a%b,g,y,x);y -= x*(a/b);}}
#ifndef ONLINE_JUDGE
#define debug(fmt, ...) {printf("debug ");printf(fmt,##__VA_ARGS__);puts("");}
#else
#define debug(fmt, ...)
#endif
typedef long long ll;
const ll mod = 1e9+7;

int main() {
    #ifndef ONLINE_JUDGE
        //freopen("in.txt", "r", stdin);
        //freopen("out.txt","w",stdout);
    #endif
    int n;
    cin >>n;
    bool f = 0;
    for(int i = 1;i <= n;i++){
        int x;
        cin >> x;
        if(x&1)continue;
        if(x%5!=0&&x%3!=0)f = 1;
    }
    if(f)cout<<"DENIED\n";
    else cout << "APPROVED\n";
    return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef pair<int,int> pii;
typedef pair<long long, int> pli;

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

ll mod = 1e9+7;

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

  vi ret(n,-1);
  bool check = true;
  rep(i,m){
    int s,c;
    cin >> s >> c;
    s--;
    if(ret[s] == -1){
      ret[s] = c;
    }else if(ret[s] != c){
      check = false;
    }
  }
  rep(i,n){
    if(ret[i] == -1){
      if(i == 0 && n != 1)ret[i] = 1;
      else ret[i] = 0;
    }
  }
  if(ret[0] == 0 && n != 1)check = false;

  if(check){
    rep(i,n)cout << ret[i];
    cout << endl;
  }else{
    cout << -1 << endl;
  }
}

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

int score[100];
int n, i, k, ans;

int main() {
  for(;;) {
    scanf("%d", &n);
    if(n == 0) break;
    REP(i, n) scanf("%d", &score[i]);
    sort(score, score + n);
    int ans = 0;
    for(int j = 1; j <= n - 2; ++j) ans += score[j];
    printf("%d\n", ans / (n - 2));
  }
  return 0;
}

Measured memory_bytes: 1204
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vb=vector<bool>;
using vvb=vector<vb>;
using vc=vector<char>;
using vvc=vector<vc>;
using pii = pair<int,int>;
using pil = pair<int,ll>;
using pli = pair<ll,int>;
using pll = pair<ll,ll>;
using tiii = tuple<int,int,int>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define rep(i, n) for(int i=0;i<(int)n;i++)
#define rep2(i, s, n) for(int i=(s);i<(int)n;i++)
int INF=1e9+7;

int main() {
  int N;
  cin >> N;
  if(N%1000==0) cout << 0 << endl;
  else cout << (N/1000+1)*1000-N << endl;
}

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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

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

    int N;
    cin >> N;

    vector<int> A(N+2, 0);
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }

    vector<int> S(N+1);
    for (int i = 0; i <= N; i++) {
        S[i] = abs(A[i+1] - A[i]);
    }

    int sum = 0;
    for (int i = 0; i <= N; i++) {
        sum += S[i];
    }
    
    for (int i = 1; i <= N; i++) {
        cout << sum + abs(A[i-1] - A[i+1]) - (abs(A[i-1] - A[i]) + abs(A[i] - A[i+1]))<< endl;        
    }
    return 0;
}

Measured memory_bytes: 2048
a, b, c = map(int, input().split())
ans = float('inf')
ans = min(ans, a * b * ((c + 1) // 2) - a * b * (c // 2))
ans = min(ans, b * c * ((a + 1) // 2) - b * c * (a // 2))
ans = min(ans, c * a * ((b + 1) // 2) - c * a * (b // 2))
print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr int MOD = 1000000007;
constexpr int INF = 1e18;

using namespace std;


signed main() {
  int N, K;
  cin >> N >> K;

  vector<int> v(N);
  REP(i, N) cin >> v[i];

  int ans = 0;
  REP(l, N+1) REP(r, N-l+1){
    if(r+l > K) continue;
    int sum = 0;
    priority_queue<int, vector<int>, greater<int>> p;
    REP(i, l){
      sum += v[i];
      if(v[i] < 0) p.push(v[i]);
    }
    REP(i, r){
      sum += v[N-i-1];
      if(v[N-i-1] < 0) p.push(v[N-i-1]);
    }
    int cnt = 0;
    while(!p.empty() && K-cnt-r-l > 0){
      sum -= p.top(); p.pop();
      cnt++;
    }
    chmax(ans, sum);
  }

  cout << ans << endl;

  return 0;
}

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

int main()
{
    ll a, b, c, k;

    cin >> a >> b >> c >> k;
    cout << ((a < k ? a : k) - (a + b < k ? (k - a - b) : 0)) << endl;
}

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

#define ll long long

using namespace std;


int main(){
 string s;
 cin>>s;
 if(s=="SUN"){
    cout<<"7"<<endl;    
 }
 if(s=="FRI"){
    cout<<"2"<<endl;    
 }
 if(s=="THU"){
    cout<<"3"<<endl;    
 }
 if(s=="WED"){
    cout<<"4"<<endl;    
 }
 if(s=="TUE"){
    cout<<"5"<<endl;    
 }
 if(s=="MON"){
    cout<<"6"<<endl;    
 }
 if(s=="SAT"){
    cout<<"1"<<endl;    
 }
 
}

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

int main()
{
    int a, b;
    cin >> a >> b;
    if(a == 1){
        if(b != 1){
            cout << "Alice" << endl;
        }
        else{
            cout << "Draw" << endl;
        }
    }
    else if(b == 1){
        cout << "Bob" << endl;
    }
    else if(a>b){
        cout << "Alice" << endl;
    }
    else if(a<b){
        cout << "Bob" << endl;
    }
    else{
        cout << "Draw" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
// Starting with the name of Allah

#include <bits/stdc++.h>
#define ll long long
#define nl endl
#define Nayon ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define gcd(a,b)         __gcd(a,b)
#define lcm(a,b)         (a/gcd(a,b))*b
#define v_sum(a)         accumulate(a.begin(),a.end(),0)
#define v_max(a)         *max_element(a.begin(),a.end())
#define v_min(a)         *min_element(a.begin(),a.end())
#define v_uni(a)         a.erase(unique(a.begin(),a.end()),a.end())
# define pi           3.14159265358979323846

using namespace std;




int main()
{
	Nayon;
	float a,sum=0.0;
	cin>>a;
	sum=2*pi*a;
	printf("%0.20f\n",sum);
	return 0;
}


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

int main() {
	string s;
	cin >> s;
	int a, z;

	bool flag = true;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'A' && flag) {
			a = i;
			flag = false;
		}
		else if (s[i] == 'Z') z = i;
	}
	cout << z - a + 1 << endl;
}

Measured memory_bytes: 3760
import math
import sys
import os

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")


N,X,M = LI()

# ans = X
# for i in range(N-1):
#     X = X**2 % M
#     ans += X

# 訪れる順序、indexは移動回数
route = [X]
# 訪れた番号、高速検索用にhash tableを使う
visited = set([X])
next = X**2 % M

while True:
    if next in visited:
        loopStart = route.index(next)
        break
    else:
        route.append(next)
        visited.add(next)
        next = next**2 % M    

beforeLoop = route[:loopStart]
# print(beforeLoop)
loop = route[loopStart:]
# print(loop)

# loop前
if N < loopStart:
    ans = sum(beforeLoop[:N])
# loop後
else:
    numOfLoops,mod = divmod((N-(loopStart)),len(loop))
    # print(numOfLoops,mod)
    ans = sum(beforeLoop) + numOfLoops * sum(loop) + sum(loop[:mod])

print(ans)

Measured memory_bytes: 77268
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n); for(int i = 0;i < (int)(n);i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
int main(){
    int n,t;
    cin >> n >> t;
    vector<int>tx(n);
    rep(i,n)cin >> tx[i];
    int ans = t;
    rep(i,n-1){
        ans += t;
        if(tx[i+1]-tx[i]<=t)ans -= t-(tx[i+1]-tx[i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
process.stdin.resume();
process.stdin.setEncoding('utf8');
// Your code here!
function main(lines) {
    const input = lines.split(' ').map(function(val){return parseFloat(val);})
    const a = input[0]
    const b = input[1]
    console.log(parseInt(Math.floor(a/b),10) + ' ' + parseInt(Math.floor(a%b),10) + ' ' + (a/b).toFixed(5))

}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 15576
#define _GLIBCXX_DEBUG//TLEの原因になるので注意！！！！！！！！！！！
#include<cmath>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<int> arr;
stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define sz(x) int(x.xise())
#define mod 1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
deque<int> deq;
//#define int long long

//cerrはコメントアウトしなくても通る//ただしTLEを引き起こすことがある

int d[10];

ll f[30005];
//int n,k とかしておく

ll pw(ll x, ll y){//euclidの互除法より
    ll a= 1;
    while(y){
        if(y&1){//奇数なら
            a = a*x%mod;
        }
        x = x*x%mod;
        y /= 2;
    }
    return a;
}

ll modinv(ll x){//逆元を求める
    return pw(x, mod - 2 );
}

ll comb(int n,int r){
    if(n<r){
        return 0;
    }
    return f[n] * modinv(f[r])%mod*modinv(f[n-r])%mod;
}//対combination//ただしfは用意してね

/*
    f[0]=1;
    rep2(i,200005){
        f[i]=f[i-1]*i;
        f[i]%=mod;
    }
*/

vector<int> e[10];

int main(){
    f[0]=1;
    rep2(i,30002){
        f[i]=f[i-1]*i;
        f[i]%=mod;
    }
    int n;
    string s;
    cin >> n>> s;
    rep(i,n){
        d[s[i]-'0']++;
        e[s[i]-'0'].push_back(i);
    }
    ll ans=0;
    cerr<<"push"<<endl;
    rep(i,10){
        rep(j,10){
            rep(k,10){
                cerr<<i<<j<<k<<endl;
                if(e[i].size()==0){
                    continue;
                }
                int a=e[i][0];
                cerr<<a<<endl;
                auto b1=upper_bound(e[j].begin(),e[j].end(),a);
                int b;
                if(b1==e[j].end()){
                    b=-1;
                }else{
                    b=*b1;
                }
                cerr<<b<<endl;;
                auto c1=upper_bound(e[k].begin(),e[k].end(),b);
                int c;
                if(c1==e[k].end()){
                    c=-1;
                }else{
                    c=*c1;
                }
                //cerr<<a<<b1<<c1<<endl;
                cerr<<a<<b<<c<<endl;
                if(a<b&&b<c){
                    ans++;
                    cerr<<a<<b<<c<<endl;
                }
            }
        }
    }

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

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

const int N_MAX=100, M_MAX=100;
char p[N_MAX+1][M_MAX+1];

int main(){
	double a,b;
	cin >> a >> b;
	double x = ceil((a + b)/2);
	cout << x << endl;
	return 0;
}



Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define OUT(x) cout << (x) << endl
typedef long long ll;
const ll MOD = 1e9 + 7;

int main() {
    ll n;
    cin >> n;
    ll ans = 1;
    for (int i = 1; i <= n; i++) {
        ans *= i;
        ans %= MOD;
    }
    OUT(ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T>
using vec = std::vector<T>;

const ll MOD = 998244353;

struct mint {
    ll x;
    mint(ll x = 0) : x((x % MOD + MOD) % MOD) {
    }
    mint operator-() const {
        return mint(-x);
    }
    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 / 2);
        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;
    }
};

ostream &operator<<(ostream &os, const mint &a) {
    return os << a.x;
}


// 下記で初期化 1000009くらいが最大か
// → combination nCk(1000009);
// そのあとは自由に使える
// → nCk(100,3) → 161700

struct combination {
    vector<mint> fact, ifact;
    combination(int n) : fact(n + 1), ifact(n + 1) {
        assert(n < MOD);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i)
            fact[i] = fact[i - 1] * i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i)
            ifact[i - 1] = ifact[i] * i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * ifact[k] * ifact[n - k];
    }
};

int main() {
    ll N, M, K;
    cin >> N >> M >> K;
    combination nCk(1000009);
    mint ans = 0;
    rep(i,K+1){
        mint tmp = M-1;
        tmp = tmp.pow(N-i-1);
        
        ans += (mint)M*tmp*nCk(N-1,i);
    }
    cout << ans << endl;
}


Measured memory_bytes: 18836
import sys
import numpy as np
import math
import collections
import copy
from collections import deque 
from functools import reduce
from itertools import product

# input = sys.stdin.readline

D, G = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(D)]
ans = 10**8
for p in product((0, 1), repeat=D):
    nmax = -1
    num = 0
    total = 0
    need = 0
    for i, pi in enumerate(p):
        if pi == 1:
            num += pc[i][0]
            total += pc[i][0]*(i+1)*100 + pc[i][1]
        else:
            nmax = i
#     print(p)
#     print(nmax, num, total)
    if total < G:
        if nmax < 0:
            continue
        if total + nmax * 100 * pc[nmax][0] + pc[nmax][1] < G:
            continue
        need = (G - total + ((nmax+1)*100-1)) // ((nmax+1)*100)
    ans = min(ans, num+need)
#     print(nmax, num, total, need, ans)

print(ans)





Measured memory_bytes: 27120
#include <bits/stdc++.h>
using namespace std;
#define modulo 2019
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000000000001

int main(){
	string S;
	cin>>S;
	
	vector<vector<long long>> dp(2,vector<long long> (modulo,0));
	long long ans = 0;
	for(int i=0;i<S.size();i++){
		dp[1][S[i]-'0']++;
		for(int j=0;j<modulo;j++){
			dp[1][(j*10+S[i]-'0')%2019] += dp[0][j];
			dp[0][j]=0;
		}
		ans += dp[1][0];
		swap(dp[0],dp[1]);
	}
		
	cout<<ans<<endl;
		
	return 0;
}


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

int main() {
  int h,w;
  cin >> h >> w;
  
  vector<vector<char>>s(h,vector<char>(w));
  for(int i=0; i<h; i++){
   for(int j=0; j<w; j++){
     cin >> s[i][j]; 
   }
  }
  
  for(int i=0; i<h; i++){
   for(int j=0; j<w; j++){
    if(s[i][j]=='#'){
      cout << '#';
      if(j==w-1) cout << endl;
      continue;
    }
    int count=0;
    for(int k=-1; k<=1; k++){
     for(int l=-1; l<=1; l++){
       if(i+k<0 || i+k>h-1 || j+l<0 || j+l>w-1)continue;
       if(s[i+k][j+l]=='#') count++;
     }
    }
     cout << count;
     if(j==w-1) cout << endl;
   }
  }
  
}



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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
const ll INF = 1LL<<60;
//int INF = numeric_limits<int>::max();

int main(int, char**) {
	int n; cin >> n;
	vector<ll> A;
	ll last;
	A.push_back(0);
	for (int i=1; i<n; i++) {
		ll a; cin >> a;
		A.push_back(2*a - A[i - 1]);
	}
	ll diff; cin >> diff;
	diff -= A[n - 1]/2;
	vector<ll> f{1, -1};
	for (int i=0; i<n; i++) {
		cout << A[i] + (diff * f[i%2]) << " ";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 2292
#include<cstdio>
int n,m,i,l,r,a[1<<21];int f(){for(i=1;i<n;i++){if(a[n+i-1]>m==a[n+i]>m)return a[n+i]>m;if(a[n-i+1]>m==a[n-i]>m)return a[n-i]>m;}return a[1]>m;}main(){scanf("%d",&n);for(i=1;i<n+n;i++)scanf("%d",a+i);for(l=1,r=n+n-1;l<=r?1:!printf("%d",l);f()?l=m+1:r=m-1)m=(l+r)/2;}


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

#define int long long
#define double long double
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define all(x) begin(x), end(x)
#define uniq(x) (x).erase(unique(all(x)), end(x))
#define bit(n) (1LL << (n))
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr double pi = 3.1415926535897932384626433832795028L;
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

int N;
int A[220000];
map<int, int> mp;
signed main() {
    cin >> N;
    rep(i, N) {
        cin >> A[i];
        mp[A[i]]++;
    }
    int ans = 0;
    for (auto p:mp) { ans += p.second * (p.second - 1) / 2; }
    rep(i, N) {
        cout << ans - (mp[A[i]] - 1) << endl;
    }
}


Measured memory_bytes: 11008
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n; cin >> n;
	vector<int> r(n);
	for (int i = 0; i < n; i++) {
		cin >> r[i];
	}
	int minv = r[0];
	int maxv = -1e9;
	for (int j = 1;j < n; j++) {
		maxv = max(maxv, r[j] - minv);
		minv = min(minv, r[j]);
	}

	cout << maxv << endl;
}


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

long long int int_pow(int m) {
  long long int ans = 1;
  while(m > 0){
    ans *= 2;
    m --;
  }
  return ans;
}

int main() {
  long long int n,m;
  cin >> n >> m;
  
  long long int set_time;
  set_time = m * 1900 + (n-m) * 100;
  
  cout << set_time * int_pow(m) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define outmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;}
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define pb push_back
#define mod 1000000007
#define infi 1900000000
#define infl 1100000000000000000
#define cyes cout << "Yes" << endl
#define cno cout << "No" << endl
#define csp << " " <<
#define outset(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T> using ve = vector<T>;
template<typename T> using pq2 = priority_queue<T>;
template<typename T> using pq1 = priority_queue<T,vector<T>,greater<T>>;


struct edge {
    int to, cost;
};


int main()
{

    int N;
    cin >> N;
    ve<ve<edge>> G(N);
    rep(i,N-1){
        int u,v,w;
        cin >> u >> v >> w;
        u--,v--;
        G[u].pb({v,w});
        G[v].pb({u,w});
    }
    
    queue<int> Q;
    Q.push(0);
    ve<int> F(N,-1);
    F[0] = 0;
    while (!Q.empty()) {
        int a = Q.front();
        Q.pop();
        //cout << a << endl;
        for (edge P : G[a]) {
            if(F[P.to] >= 0) continue;
            
            if(P.cost % 2 == 0) F[P.to] = F[a];
            else F[P.to] = (F[a] == 0 ? 1 : 0);
            Q.push(P.to);
        }
        
    }
    
    rep(i,N) cout << F[i] << endl;

    
    
    
    

    return 0;
}


Measured memory_bytes: 6784
package main

import (
	"fmt"
)

func main() {
	var n,k int
	ans := 0.0

	fmt.Scan(&n,&k)

	for i:=1; i<n+1; i++ {
		p := i
		num := 1
		for ;; {
			if p>=k {
				break
			}
			p*=2
			num*=2
		}
		ans+=1.0/float64(num)/float64(n)
	}
	fmt.Printf("%.12f\n", ans)
}


Measured memory_bytes: 512