akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/stack:256000000")
#include<utility>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<functional>
#include<random>
#include<climits>
#include<queue>
#include<stack>
#include<deque>
#include<bitset>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<cassert>
#include<ccomplex>

//4Head
#define all(x) x.begin(), x.end()
#define mp make_pair
#define X first
#define Y second

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
mt19937_64 gen(time(NULL));

// belik's shit
ll const mod = 1e9 + 7;
namespace {
	ll mult(ll& a, ll& b) {
		ll val = a * b - (ll)((ld)a * b / mod) * mod;
		if (val < 0) {
			val += mod;
		}
		if (val >= mod) {
			val -= mod;
		}
		return val;
	}
	ll poww(ll a, ll b)
	{
		ll val = 1;
		a %= mod;
		while (b > 0) {
			if (b % 2) val = mult(a, val);
			a = mult(a, a);
			b >>= 1;
		}
		return val % mod;
	}
	ll inv(ll a) {
		return poww(a, mod - 2);
	}
}

ll const maxn = 1e6 + 6;

vector<ll> z_function(string s) {
	ll n = (ll)s.length();
	vector<ll> z(n);
	for (ll i = 1, l = 0, r = 0; i < n; ++i) {
		if (i <= r)
			z[i] = min(r - i + 1, z[i - l]);
		while (i + z[i] < n && s[z[i]] == s[i + z[i]])
			++z[i];
		if (i + z[i] - 1 > r)
			l = i, r = i + z[i] - 1;
	}
	return z;
}
ll n;
vector<ll>g[maxn];
ll col[maxn];
ll predok[maxn];
ll xyi = -1;
ll cycle_end, cycle_st;

bool dfs1(ll u) {
	col[u] = 1;
	for (ll v : g[u]) {
		if (col[v] == 0) {
			predok[v] = u;
			if (dfs1(v)) return true;
		}
		else if (col[v] == 1) {
			predok[v] = u;
			xyi = v;
			cycle_st = v;
			cycle_end = u;
			return true;
		}
	}
	col[u] = 2;
	return false;
}

bool used[maxn];
ll num[maxn];
vector<ll>topsort;
void dfs(ll u) {
	used[u] = 1;
	ll k = 0;
	for (ll v : g[u]) {
		if (!used[v]) dfs(v);
	}
	topsort.push_back(u);
}
ll dp[maxn];

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	string s; cin >> s;
	string t; cin >> t;
	n = s.size() + 1;
	string shit = t + "#" + s + s;
	while (shit.size() <= 4 * t.size() + 1) {
		shit += s;
	}
	auto z = z_function(shit);
	set<ll>verts;
	for (ll i = t.size() + 1; i < shit.size(); i++) {
		ll pos = i - t.size() - 1;
		if (z[i] == t.size()) {
			verts.insert(pos % s.size());
		}
	}
	for (auto v : verts) {
		ll vv = v + t.size();
		vv %= s.size();
		if (verts.count(vv)) {
			g[v].push_back(vv);
		}
	}
	fill_n(predok, maxn + 1, -1);
	for (ll i = 0; i < n; i++) {
		if (col[i] == 0) if (dfs1(i)) break;
	}
	if (xyi == -1) {
		for (ll i : verts) {
			if (!used[i]) dfs(i);
		}
		reverse(topsort.begin(), topsort.end());
		for (ll i = 0; i < topsort.size(); i++) {
			num[topsort[i]] = i; dp[i] = 1;
		}
		ll mx = 0;
		for (ll i = 0; i < topsort.size(); i++) {
			for (ll x : g[topsort[i]]) {
				dp[num[x]] = max(dp[i] + 1, dp[num[x]]);
			}
		}
		for (ll i = 0; i < topsort.size(); i++) {
			mx = max(mx, dp[i]);
		}
		cout << mx << endl;
	}
	else {
		cout << -1 << endl;
	}

	return 0;
}
/*

*/

Measured memory_bytes: 125908
#include <stdio.h>
 
int main(){
   int x, y, z, i, a;
   scanf("%d %d\n",&x, &y);
   i=1;
   if(y > x){
      a=x;
      x=y;
      y=a;
   }
   for(;i>0;){
      z=x%y;
      if(z==0){
         printf("%d\n",y);
         break;
      }
      x=y;
      y=z;
   }
   return 0;
}
 
 

Measured memory_bytes: 2748
#include <iostream>
#include <algorithm>
#include <vector>
#include <assert.h>
#include <stdio.h>


using namespace std;

#define MAXN 21
long long MM =(1e9+7);


int A[MAXN+1][MAXN+1];


int number_1_bit(int set) {
  int count = 0;
  while (set != 0) {
    count += (set & 1);
    set = set >> 1;
  }

  return count;
}

int main() {
  // task O
  assert( (1 << 1) == 2);

  assert( number_1_bit(7) == 3 );
  assert( number_1_bit(8) == 1 );
  assert( number_1_bit(0) == 0 );
  assert( number_1_bit(0b101010100) == 4 );
  assert( number_1_bit(0b001010100) == 3 );

  int N;
  cin >> N;
  assert(N > 0 && N <= 21);
  // count from 0 -> N-1
  for(auto i=0;i<N; i++) {
    for(auto j=0;j<N; j++) scanf("%d", &A[i][j]);
  }

  vector<int> F( (1<<N) + 1, 0);

  F[0] = 1; // there is a way to match two empty sets

  for (int subset = 1; subset < (1 << N); subset++) {
    auto size = number_1_bit(subset);
    // matching subset (women) with the set {0 .. |subset|-1} (men)

    for (auto i=0; i<N; i++) { // consider matching (size-1)-th man <-> i-th bit woman
      if(  subset & (1<<i) ) { // in the subset
        if ( A[size-1][ i ] == 1) {  // a match, consider a sub problem, disable i-th bit
          auto sub = subset - (1<<i);
          F[subset] = (F[subset] + F[sub]) % MM;
        }
      }
    }
  }

  cout << F[ (1<<N) - 1] << endl;
  return 0;
}


Measured memory_bytes: 8448
import math


def resolve():
    import sys
    input = sys.stdin.readline
    row1 = [int(x) for x in input().rstrip().split(" ")]
    # row2 = [int(x) for x in input().rstrip().split(" ")]
    s = input().rstrip()

    n = row1[0]
    a = row1[1]
    b = row1[2]

    kokunai = 0
    kaigai = 0
    for char in s:
        if char == "a":
            if(kaigai + kokunai < a + b):
                print("Yes")
                kokunai += 1
                continue

        elif char == "b":
            if((kaigai + kokunai < a + b) and (kaigai < b)):
                print("Yes")
                kaigai += 1
                continue
        print("No")








if __name__ == "__main__":
    resolve()


Measured memory_bytes: 9312
a = list(map(int,[input() for i in range(5)]))
k = int(input())

ans = True
for i in range(5):
    for j in range(i+1,5):
        if (a[j]-a[i]) > k:
            ans = False

if ans:
    print('Yay!')
else:
    print(':(')

Measured memory_bytes: 38256
import java.util.Scanner;

class Main {
	public static void main(String[] args){
		Scanner input=new Scanner(System.in);
		int sortLong=input.nextInt();
		
		int[] sortNumber=new int[sortLong];
		
		for(int i=0;i<sortLong;i++)
			sortNumber[i]=input.nextInt();
		
		int number=sort(sortNumber);
		for(int i=0;i<sortNumber.length-1;i++)
			System.out.print(sortNumber[i]+" ");
		System.out.println(sortNumber[sortNumber.length-1]);
		
		System.out.println(number);
		
	}
	
	public static int sort(int[] sortArray){
		int t,sw=0,minj;
		
		for(int i=0;i<sortArray.length-1;i++){
			minj=i;
			for(int j=i;j<sortArray.length;j++){
				if(sortArray[j]<sortArray[minj])
					minj=j;
			}
			
			t=sortArray[i];
			sortArray[i]=sortArray[minj];
			sortArray[minj]=t;
			
			if(i!=minj)
				sw++;
		}
		
		return sw;
	}

}

Measured memory_bytes: 26312
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

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

    // hの読込;
    vector<int> h(N);
    rep(i, N)   cin >> h.at(i);

    //DPの実行
    vector<int> cost(N);
    for (int i = 0; i < N; i++) {
        cost.at(i) = 999999;
    }
    cost.at(0) = 0;
    for (int i = 0; i < N; i++) {
        if (i == 0) continue;
        if (i == 1) {
            cost.at(i) = cost.at(i - 1) + abs(h.at(i - 1) - h.at(i));
            continue;
        }
        cost.at(i) = min({ cost.at(i - 1) + abs(h.at(i - 1) - h.at(i)), cost.at(i - 2) + abs(h.at(i - 2) - h.at(i))});
    }
    cout << cost.at(N-1);
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
  long long x = 100;
  long long y;
  cin >> y;
  long long i;
  for(i=1;x<y;i++){
    x *= 1.01;
  }
  cout << i-1 << endl;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
int main(void){
    string S;
    int ans = 700;
    cin >> S;
    for (int i=0; i<S.size(); i++)
    {
        if (S[i] == 'o') ans += 100;
    }
    cout << ans << endl;
    return 0;
}


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

int main(void) {
    int N,M;cin>>N>>M;
    char A[N][N],B[M][M];
    for (int i = 0; i < N; i++) {
        string a;cin>>a;
        for (int j = 0; j < N; j++) A[i][j] = a[j];
    }
    for (int i = 0; i < M; i++) {
        string b;cin>>b;
        for (int j = 0; j < M; j++) B[i][j] = b[j];
    }
/*
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%c", A[i][j]);
        }
        cout << endl;
    }
    cout << endl;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < M; j++) {
            printf("%c", B[i][j]);
        }
        cout << endl;
    }
*/
    // 左上の位置をずらして、ループ
    for (int start_x = 0; start_x <= N - M; start_x++) {
        for (int start_y = 0; start_y <= N - M; start_y++) {
            bool flg = true;
            for (int i = start_x; i < start_x + M; i++) {
                for (int j = start_y; j < start_y + M; j++) {
                    if (A[i][j] != B[i - start_x][j - start_y]) flg = false;
                }
            }
            if (flg) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "


// CHECK THE LIMITS
typedef long long ll;

const int MOD = 1000000007;
const ll INFLL = 1e18;
const int INF = 1e9;
const int NMAX = 1000001;

int gcd(int a, int b) {
  return b ? gcd(b, a%b) : a;
} 

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	int n,k;
	cin >> n >> k;
	int ct =0;
	while(n)
	{
		ct++;
		n/=k;
	}
	cout<< ct;


    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <iomanip>
#include <stack>
  
using namespace std;

#define pi 3.141592653589793

struct Thread {
	int num;
	string node;
	int children[1001];
	int dotnum;
};

typedef struct Thread th;

void result(th m[], int cn[], int n)
{
	for(int i = 0; i < m[n].dotnum; i++){
		cout << ".";
	}
	cout << m[n].node << endl;
	if(cn[n] == 0) return;
	for(int i = 0; i < cn[n]; i++){
		result(m, cn, m[n].children[i]);
	}
	return;
}

int main()
{
	int n;
	cin >> n;
	int k[1001], children_num[1001] = {};
	th m[1001];
	for(int i = 0; i < n; i++){
		cin >> k[i] >> m[i].node;
	}
	m[0].dotnum = 0;
	for(int i = 1; i < n; i++){
		int parent = k[i] - 1;
		m[i].num = i;
		m[k[i] - 1].children[children_num[parent]] = i;
		children_num[parent]++;
		m[i].dotnum = m[parent].dotnum + 1;
	}
	result(m, children_num, 0);
	return 0;
}

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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;

using namespace std;
using ll = long long;

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

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

	int N=in();
	vector<int> A(N);
	int max_a=0,next_a=0;
	int max_i,next_i;
	REP(i,N){
		A[i] = in();
		if(max_a<A[i]){
			if(max_a>0){
				next_a = max_a;
				next_i = max_i;
			}
			max_a = A[i];
			max_i = i;
		}
		else if(next_a<A[i]){
			next_a = A[i];
			next_i = i;
		}
	}
	REP(i,N){
		if(i==max_i) cout << next_a << endl;
		else cout << max_a << endl;
	}
	return 0;
}


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

double dp[22][200002],c[22],ans=1e9;
int n;

vector<int>v[200002];

void init(){
	r(i,21)r(j,200002)dp[i+1][j]=1e9;
	r(j,200002)dp[0][j]=abs(c[0]-j)/c[0];
	for(int i=1;i<200002;i++){
		for(int j=1;j*j<=i;j++){
			if(i%j==0){
				if(i!=j*j)v[i].push_back(j);
				v[i].push_back(i/j);
			}
		}
	}
}



int main(){
	cin>>n;
	r(i,n)cin>>c[i];
	init();
	for(int i=1;i<n;i++){
		r(j,200002){
			r(k,v[j].size()){
				int x=v[j][k];
				dp[i][j]=min(dp[i][j],max(dp[i-1][x],abs(c[i]-j)/c[i]));
				if(i==n-1)ans=min(ans,dp[i][j]);
			}
		}
	}
	printf("%.9f\n",n==1?0:ans);
}


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


int check(const string& temp,vector<int>& D)
{
    for(int i = 0;i < temp.size();i++)
    {
            int number = (int)temp[i] - (int)'0';
            if(find(D.begin(),D.end(),number) != D.end())
            {
                return -1;
            }
    }
    return 1;
}

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

    vector<int> D(K);

    for(int i = 0;i < K;i++)
    {
        cin >> D[i];
    }
    string temp = "";
    for(int n = N;;n++)
    {
        temp = to_string(n);

        if(check(temp,D) == 1)
        {
            cout << temp << endl;
            return 0;
        }
    }
}

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

using namespace std;

using ll = long long;

ll solve(const vector<pair<ll, ll>> &va, vector<vector<ll>> &memo, int l = 0,
         int r = 0) {
  if (l + r == va.size()) {
    return 0;
  }

  if (memo[l][r] < 0) {
    auto [a, idx] = va[l + r];
    ll n = static_cast<ll>(va.size());
    memo[l][r] = max(solve(va, memo, l + 1, r) + a * abs(idx - l),
                     solve(va, memo, l, r + 1) + a * abs(idx - (n - r - 1)));
  }

  return memo[l][r];
}

int main(int argc, const char *argv[]) {
  int n;
  cin >> n;

  vector<pair<ll, ll>> va;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    va.push_back({a, i});
  }

  sort(va.begin(), va.end(), greater<pair<ll, ll>>());
  vector<vector<ll>> memo(n + 1, vector<ll>(n + 1, -1));
  cout << solve(va, memo) << '\n';
  return 0;
}

Measured memory_bytes: 34624
#include <bits/stdc++.h>
using namespace std;
int main(void) {
  long a, b, c, k;
  cin >> a >> b >> c >> k;
  if (k <= a) {
    cout << k << endl;
  } else if (k <= a + b) {
    cout << a << endl;
  } else {
    cout << a - (k - a - b) << endl;
  }
  return 0;
}


Measured memory_bytes: 3616
#include <stdio.h>
#include <string.h>
#define M 100000
int main(){
	int i,m,n,flag=0;
	scanf("%d",&i);
	char str[M];
	while(getchar()!='\n');
	gets(str);
	int j = strlen(str);
	for(m=0; m<j; m++){
		if(str[m] != str[m+1])
			flag++;
	}
	printf("%d",flag);
	return 0;
}

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

using namespace std;

void solve() {
  int64_t n, a, b;
  cin >> n >> a >> b;

  if (a == 0) {
    cout << 0 << endl;
  } else {
    auto total = a + b;
    auto q = n / total;
    auto m = n % total;
    auto ans = q * a + min(a, m);
    cout << ans << endl;
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/




int N;
#define vacant "Vacant"
#define male "Male"
#define female "Female"
//---------------------------------------------------------------------------------------------------
int debug = 0;
string res[5] = { male, female, vacant, male, female };
string a0;
string ask(int i) {
    printf("%d\n", i);

    if (debug) return res[i];
    
    fflush(stdout);
    string res; cin >> res;
    return res;
}
//---------------------------------------------------------------------------------------------------
void f(int l, int r) {
    int md = (l + r) / 2;

    auto res = ask(md);
    if (res == vacant) return;

    if ((md % 2 == 0 and a0 == res) or (md % 2 == 1 and a0 != res)) f(md + 1, r);
    else f(l, md);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    a0 = ask(0);
    if (a0 == vacant) return;

    f(1, N);
}

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

#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false

int main()
{
   int n;
   while(cin>>n,n){
       vector<int> data;
       rep(i,n){
           int temp;
           cin>>temp;
           data.push_back(temp);
       }
       SORT(data);
       long ans=0;
       REP(i,1,n-1){
           ans+=data[i];
       }
       cout<<ans/(n-2)<<endl;;
   }
   return 0;
}

Measured memory_bytes: 3112
// ABC139_A
#include<bits/stdc++.h>
using namespace std;
int main(){

    string S, T;
    int cnt=0;
    cin >> S >> T;
    for(int i=0; i<S.size(); i++){
        if(S.at(i) == T.at(i)){
            cnt++;
        }
    }
    cout << cnt << endl;

}

Measured memory_bytes: 256
N = int(input())
X = sorted(list(map(int, input().split(" "))))
min = -1
for i in range(X[0], X[-1]+1):
  s = sum((x - i) ** 2for x in X)
  if min == -1:
    min = s
  if s < min:
    min = s
print(min)

Measured memory_bytes: 3060
#include <stdio.h>

int x[100010];
long long int s[100010];
int main()
{
	int a;
	scanf("%d",&a);
	for(int i=0;i<=a;i++) scanf("%d",&x[i]);
	for(int i=a;i>=0;i--) s[i] = s[i+1] + x[i];
	
	long long int S = 1;
	long long int ans = 0;
	for(int i=0;i<=a;i++)
	{
		ans += S;
		if(S<x[i])
		{
			printf("-1");
			return 0;
		}
		S -= x[i];
		S*=2;
		S = S<s[i+1]?S:s[i+1];
	}
	printf("%lld",ans);
}


Measured memory_bytes: 2884
n = int(input())
a = list(map(int,input().split()))
a.sort()
mx = a[-1]
c = [0 for _ in range(mx+1)]
ans = 0
if a[0] == 1:
  if n == 1:
    print(1)
    exit()
  if a[1] == 1:
    print(0)
    exit()
  else:
    print(1)
    exit()
i = 0
while i < n:
  if c[a[i]] == 0:
    p = a[i]
    for _ in range(2,mx//a[i]+1):
      p += a[i]
      c[p] = 1
    flag = True
    while i+1 < n and a[i+1] == a[i]:
      i += 1
      flag = False
    if flag:
      ans += 1
  i += 1
print(ans)

Measured memory_bytes: 164312
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;

#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let line: Vec<usize> = read_as_vec();
    let (_, k) = (line[0], line[1]);

    let v: Vec<i64> = read_as_vec();

    let max_num_op = cmp::min(k, v.len());
    let mut ops: Vec<(usize, usize)> = Vec::new();
    for i in 0..max_num_op+1{
        for j in 0..cmp::max(max_num_op-i+1, 0){
            if i != 0 || j != 0{
                ops.push((i, j));
            }
        }
    }

    let mut ans = std::i64::MIN;
    for elem in &ops{
        let num_left = &elem.0;
        let num_right = &elem.1;
        //println!("{}, {}", num_left, num_right);
        let mut got_jewelry = v.iter().take(*num_left).collect::<Vec<_>>();
        let right_jewelry = v.iter().rev().take(*num_right).collect::<Vec<_>>();

        got_jewelry.extend(right_jewelry);
        got_jewelry.sort();
        //println!("{:?}", got_jewelry);

        let num_removal = k - num_left - num_right;

        //If got_jewelry.len() <= num_removal || *got_jewelry[num_removal-1] < 0{
        if num_removal == 0{
            ans = cmp::max(ans, got_jewelry.into_iter().sum());
        }else if num_removal >= got_jewelry.len(){
            ans = cmp::max(ans, got_jewelry.into_iter().filter(|x| **x > 0).sum());
        }else if *got_jewelry[num_removal-1] < 0{
            ans = cmp::max(ans, got_jewelry.into_iter().skip(num_removal).sum());
        }else{
            ans = cmp::max(ans, got_jewelry.into_iter().filter(|x| **x > 0).sum());
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <iostream>
#include<cstring>
#include<cmath>
#include <algorithm>
#include <vector>
using namespace std;
long long n;
long long w[100],v[100],dp[100001][101]={};
long long fun(long long weight, long long i)
{
	if(weight<0)
	return -pow(10,18);
	if(i<0)
	return 0;
	if(dp[weight][i]!=0)
	return dp[weight][i];
	long long ans=max(fun(weight-w[i],i-1)+v[i] , fun(weight,i-1));
	dp[weight][i]=ans;
	return ans;
}
int main()
{
	long long weight;
	cin>>n>>weight;
	
	for(long long i=0;i<n;i++)
	{
		cin>>w[i]>>v[i];	
	}
	cout<<fun(weight,n-1);
	return 0;
}

Measured memory_bytes: 78848
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>

#define max  100000

//qsort(str, n, sizeof(int), up_comp);
int up_comp(const void *a, const void *b){return *(int*)a - *(int*)b;}
int down_comp(const void *a, const void *b){return *(int*)b - *(int*)a;}
int count_digit(int a){int i=0;while(a!=0){a=a/10;i++;}return i;}
int euclid( int a, int b ){int temp;if(a<b){temp=a;a=b;b=temp;}if(b<1)return -1;if(a%b==0) return b;return euclid(b,a%b);}
int int_sort( const void * a , const void * b ) {
  return strcmp(( char * )a , ( char * )b );
}

int main()
{
    int A[1]={1};
    char s[max];
    
    scanf("%s", s);
    
    if (strcmp(s, "ABC")==0) {
        printf("ARC");
    } else {
        printf("ABC");
    }
    
    return 0;
} 



Measured memory_bytes: 1736
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define lli long long int

const lli MOD = 1e9 + 7;
const lli INF = 1e15;

const lli MAX_N = 200010;
vector<pair<lli, lli> > G[MAX_N];
vector<lli> dijkstra(lli start){
    vector<lli> dist(MAX_N, INF);
    dist[start] = 0;//dist[i] :=　start->iまでの最短距離
    priority_queue<pair<lli, lli>, vector<pair<lli, lli> >, greater<pair<lli, lli> > >  que;
    que.push(make_pair(0, start));
    while(!que.empty()){
        lli cost, w;//今までにかかった時間 現在の頂点
        cost = que.top().first, w = que.top().second;
        que.pop();
        if(dist[w] < cost) continue;
        for (auto tmp : G[w]){
            lli v = tmp.first, time = tmp.second;//隣接する頂点 その頂点まで行く時間
            if(dist[v] > dist[w] + time){//u->v
                dist[v] = dist[w] + time;
                que.push(make_pair(dist[v], v));
            }
        }
    }
    return dist;
}

lli n, m;
lli u[100010], v[100010], c[100010];

signed main(void){

    cin >> n >> m;
    lli data[100010];
    rep(i,100010)data[i]=0;
    
    rep(i, m){
        cin >> u[i]>>v[i]>>c[i];
        u[i]--; v[i]--;
        data[u[i]]++;
        data[v[i]]--;
        G[u[i]].pb(mp(v[i], c[i]));
    }
    rep(i,100010-1){
        G[i+1].push_back(mp(i,0));
    }

    auto dist1 = dijkstra(0);
    lli ans = dist1.at(n-1);
    if(ans!=INF)cout<<ans<<endl;
    else cout<<-1<<endl;

    return 0;
}

Measured memory_bytes: 15228
/**
 * Created by rasrivastava on 10/17/16.
 */
class CodeFestival(val destination: String) {
  def inputStr(source : String) : Int = {
    var count = 0
    for (i <- 0 to source.length-1) {
      val sch = source.charAt(i)
      val dch = destination.charAt(i)
      if (sch != dch) {
        count += 1
      }
    }

    count
  }

}

object Main extends App {
  val line = readLine()
  val codeFestival = new CodeFestival("CODEFESTIVAL2016")
  println(codeFestival.inputStr(line))
}


Measured memory_bytes: 21572
import java.io.*;
import java.nio.CharBuffer;
import java.util.NoSuchElementException;

public class Main {

    public static void main(String[] args) {
        SimpleScanner scanner = new SimpleScanner(System.in);
        PrintWriter writer = new PrintWriter(System.out);

        int n = scanner.nextInt();
        int k = scanner.nextInt();
        char[] s = scanner.next().toCharArray();
        s[k - 1] = Character.toLowerCase(s[k - 1]);
        writer.println(new String(s));

        writer.close();
    }

    private static class SimpleScanner {

        private static final int BUFFER_SIZE = 10240;

        private Readable in;
        private CharBuffer buffer;
        private boolean eof;

        SimpleScanner(InputStream in) {
            this.in = new BufferedReader(new InputStreamReader(in));
            buffer = CharBuffer.allocate(BUFFER_SIZE);
            buffer.limit(0);
            eof = false;
        }


        private char read() {
            if (!buffer.hasRemaining()) {
                buffer.clear();
                int n;
                try {
                    n = in.read(buffer);
                } catch (IOException e) {
                    n = -1;
                }
                if (n <= 0) {
                    eof = true;
                    return '\0';
                }
                buffer.flip();
            }
            return buffer.get();
        }

        void checkEof() {
            if (eof)
                throw new NoSuchElementException();
        }

        char nextChar() {
            checkEof();
            char b = read();
            checkEof();
            return b;
        }

        String next() {
            char b;
            do {
                b = read();
                checkEof();
            } while (Character.isWhitespace(b));
            StringBuilder sb = new StringBuilder();
            do {
                sb.append(b);
                b = read();
            } while (!eof && !Character.isWhitespace(b));
            return sb.toString();
        }

        int nextInt() {
            return Integer.valueOf(next());
        }

        long nextLong() {
            return Long.valueOf(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}

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


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

	int ans = 0;
	ll k=1;
	while(N>=k){
		k = k*K;
		ans++;
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        string s = Console.ReadLine();

        char c;
        int count = 0;
        for (int i = 1; i < n; i++)
        {
            if (s[i] == s[i - 1])
            {
                count++;
            }
        }

        Console.WriteLine(n - count);
    }

}


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

for i in range(n):
    out_cnt = 0
    score = 0
    runner = [0,0,0,0]
    while True:
        event = input()
        if event=="OUT":
            out_cnt += 1
            if out_cnt == 3:
                break

        elif event=="HIT":
            if 1 in runner:
                for ind in range(len(runner)-1,-1,-1):
                    if runner[ind] == 1:
                        if ind != 3:
                            runner[ind] = 0
                            runner[ind+1] = 1
                            if not 1 in runner[:ind]:
                                break
                if runner[-1]==1:
                    runner[-1] = 0
                    score += 1    
                runner[0] = 1           
            else:
                runner[0] = 1

        elif event=="HOMERUN":
            score += sum(runner)+1
            runner = [0,0,0,0]
    print(score)


Measured memory_bytes: 5596
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
	ll n, h; cin >> n >> h;
	vector<pair<ll, bool>> v;
	for(ll i = 0; i < n; i++){
		ll a, b; cin >> a >> b;
		v.push_back(pair<ll, bool>(a, 0));
		v.push_back(pair<ll, bool>(b, 1));
	}
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	queue<pair<ll, bool>> q;
	for(ll i = 0; i < v.size(); i++) q.push(v[i]);
	for(ll i = 1;; i++){
		h -= q.front().first;
		if(q.front().second){
			q.pop();
		}else{
			i += h / q.front().first + !!(h % q.front().first);
			h = 0;
		}
		if(h <= 0){
			cout << i << endl;
			return 0;
		}
	}
}

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

bool f(const long kind, const size_t n, const vector<long>& a){
    map<long,long> c;
    for(size_t i=1; i<n; i++){
        if(a[i-1]>=a[i]){
            c.erase(c.lower_bound(a[i]), c.end());
            long j=a[i]-1;
            c[j]++;
            for(;;){
                if(c[j] < kind){
                    break;
                }else if(j<=0){
                    return false;
                }else{
                    c[j]=0;
                    c[j-1]++;
                    j--;
                }
            }
        }
    }
    return true;
}

bool strict_increasing(const vector<long>& a){
    size_t n = a.size();
    for(size_t i=1; i<n; i++){
        if(a[i-1]>=a[i]){
            return false;
        }
    }
    return true;
}

int main(void){
    long n;
    cin >> n;
    vector<long> a(n);
    for(long i=0; i<n; i++){
        cin >> a[i];
    }
    if(strict_increasing(a)){
        cout << 1 << endl;
        return 0;
    }
    long left=1, right=n;
    for(;;){
        const long mid = (left+right)/2;
        if(right-left<=1){
            if(f(right, n, a)){
                cout << right << endl;
            }else{
                cout << left << endl;
            }
            return 0;
        }
        const bool b = f(mid, n, a);
        //printf("[%ld, %ld] %ld %s\n", left, right, mid, b ? "true" : "false");
        if(b){
            right=mid;
        }else{
            left=mid;
        }
    }
}


Measured memory_bytes: 1792
# encoding: utf-8

class UFSet
  def initialize(sz)
    @sz = sz
    @par = [0] * sz
    (0..sz - 1).each { |idx| @par[idx] = idx}
  end

  def find(x)
    if @par[x] == x
      x
    else
      @par[x] = find(@par[x])
    end
  end

  def same(x, y)
    find(x) == find(y)
  end

  def unite(x, y)
    fx = find(x)
    fy = find(y)
    @par[fx] = fy if fx != fy
  end
end

class Graph
  def initialize(v)
    @v = v
    @edge = []
  end

  def add_edge(u, v, w)
    @edge << { from: u, to: v, weight: w}
  end

  def mst_kruskal
    ans = 0
    @edge = @edge.sort_by { |x| x[:weight]}
    ufset = UFSet.new(@v)
    @edge.each do |ee|
      u, v, c = ee[:from], ee[:to], ee[:weight]
      if not ufset.same(u, v)
        ans += c
        ufset.unite(u, v)
      else
        next
      end
    end
    ans
  end
end

def main
  n = gets.rstrip.to_i
  g = Graph.new(n)
  (0..n - 1).each do |row|
    r = gets.lstrip.rstrip.split(/\s/).map(&:to_i)
    r.each_with_index do |node, idx|
      g.add_edge(row, idx, node) if node >= 0
    end
  end
  puts g.mst_kruskal
end

main

Measured memory_bytes: 7628
import sys
import numpy as np
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
MOD = 1_000_000_007
def dot_MOD(x1, x2, MOD):
    """行列の積とＭＯＤ

    ＭＯＤを取りつつ行列の積をもとめる。

    Args:
        x1 (2Dndarry of int): 被積の行列
        x2 (2Dndarry of int): 加積の行列

    Returns:
        ret (2Dndarry of int): 求まった行列

    Raises:
        例外の名前: 例外の説明 (例 : 引数が指定されていない場合に発生 )

    Yields:
        戻り値の型: 戻り値についての説明

    Examples:
        関数の使い方について記載

    Note:
        注意事項などを記載

    """
    ret = np.zeros((x1.shape[1],x2.shape[0]), dtype='int64')
    for i in range(x1.shape[0]):
        for j in range(x2.shape[1]):
            ret[i][j] = np.mod(x1[i,:] * (x2[:,j][np.newaxis:]), MOD, dtype='int64').sum()
    ret %= MOD
    return ret

def x2_MOD(x, MOD):
    """行列の自冪とＭＯＤ

    ＭＯＤを取りつつ行列の自冪をもとめる。

    Args:
        x1 (2Dndarry of int): 行列

    Returns:
        ret (2Dndarry of int): 求まった行列

    Raises:
        例外の名前: 例外の説明 (例 : 引数が指定されていない場合に発生 )

    Yields:
        戻り値の型: 戻り値についての説明

    Examples:
        関数の使い方について記載

    Note:
        注意事項などを記載

    """
    ret = np.empty(x.shape, dtype='int64')
    for i in range(x.shape[0]):
        for j in range(x.shape[0]):
            ret[i][j] = np.mod(x[i,:] * (x[:,j][np.newaxis:]), MOD, dtype='int64').sum()
    ret %= MOD
    return ret

N, K = map(int, input().split())
A = np.array(list(map(int, read().split())), dtype='int64').reshape((N, N))
ans = np.eye(N, dtype='int64')
while K:
    if K&1:
        ans = dot_MOD(ans,A,MOD)
    A = x2_MOD(A, MOD)
    K >>= 1
print(np.mod(ans.sum(), MOD, dtype='int64'))

Measured memory_bytes: 27192
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

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

    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        int[] A = new int[N];
        A[0] = -1;
        for (int i = 1; i < N; i++) {
            A[i] = scan.nextInt()-1;
        }
        int[] ans = new int[N];
        for (int i = N-1; 0 <= i; i--) {
            int current = i;
            int boss = boss(A, current);
            if (boss == -1) {
                continue;
            }
            ans[boss] += 1;
        }
        for (int i = 0; i < N; i++) {
            System.out.println(ans[i]);
        }
    }
    private int boss(int[] A, int current) {
        return A[current];
    }
}


Measured memory_bytes: 55036
#include<iostream>

int main(){
  int64_t n,a,b;
  std::cin>>n>>a>>b;
  int64_t ans = 0;
  int64_t prv,cur;
  std::cin>>prv;
  for(int i=1;i<n;++i){
    std::cin>>cur;
    ans += std::min(a*(cur-prv),b);
    prv = cur;
  }
  std::cout<< ans <<std::endl;
}


Measured memory_bytes: 3576
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<cmath>
#include<string>

#define ls (t<<1)
#define rs ((t<<1)+1)
#define mid ((l+r)>>1)
#define fi first
#define se second
#define mk make_pair
#define pb push_back

#define N 100005
#define M 200005
#define seed 23333

using namespace std;
int i,j,m,n,p,k,dep[N],deg[N],a[N],Q[N],l,B[N];
vector<int>v[N];
inline bool cmp(int a,int b)
{
		return a>b;
}
int main()
{
	scanf("%d",&n);
	for (i=2;i<=n;++i) scanf("%d",&a[i]),v[a[i]].pb(i),deg[a[i]]++;
	for (i=1;i<=n;++i) if (!deg[i]) Q[++Q[0]]=i;
	for (l=1;l<=Q[0];++l)
	{
			int p=Q[l]; B[0]=0;
			for (i=0;i<(int)v[p].size();++i)
				  B[++B[0]]=dep[v[p][i]];
			sort(B+1,B+B[0]+1,cmp);
			for (i=1;i<=B[0];++i) dep[p]=max(dep[p],B[i]+i);
			--deg[a[p]];
			if (!deg[a[p]]) Q[++Q[0]]=a[p];
	}
	printf("%d\n",dep[1]); 
}


Measured memory_bytes: 7296
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> P;

int main() {
	int n, m;

	cin >> n >> m;

	int count1 = 0;
	int count2 = 0;
	if (n > 1) {
		for(int i = 1; i < n; i++) {
			count1 = count1 + i;
		}
	}

	if (m > 1) {
		for(int i = 1; i < m; i++) {
			count2 = count2 + i;
		}
	}
	cout << count1 + count2 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main(void)
{
    std::string a, b, c;
    std::cin >> a >> b >> c;
    char x = a[0], y = b[0], z = c[0];
    x -= 0x20;
    y -= 0x20;
    z -= 0x20;
    std::cout << x << y << z << std::endl;
    return 0;
}


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

int main() {
  string s;
  
  cin >> s;
  
  if (s[0] == s[1] && s[1] == s[2])
  cout << "Yes" << endl;
  else if (s[1] == s[2] && s[2] == s[3])
  cout << "Yes" << endl;
  else 
  cout << "No" << endl;

}

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

int main(void) {
	int a[3], m[3];

	for(int i = 0; i < 3; i++)
		cin >> a[i] >> m[i];

	while(a[0] + a[1] + a[2] + m[0] + m[1] + m[2]) {
		int b[3];
		int hoge;

		for(int i = 0; i < 3; i++) {
			int tmp = 0;
			for(int j = 1; !tmp || j != 1; j = j * a[i] % m[i]) tmp++;
			b[i] = tmp;
		}

		int p, q, r;
		p = max(b[0], b[1]); q = min(b[0], b[1]);
		while(p % q) {
			r = p % q;
			p = q;
			q = r;
		}

		hoge = q = b[0] * (b[1] / q);

		p = b[2];
		if(q > p) swap(p, q);
		while(p % q) {
			r = p % q;
			p = q;
			q = r;
		}

		cout << (long)hoge * (b[2] / q) << endl;

		for(int i = 0; i < 3; i++)
			cin >> a[i] >> m[i];
	}
}

Measured memory_bytes: 1160
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <complex>

using namespace std;
using ll = unsigned long long;
using R = long double;
const R PI = 4.0*atan(1.0);
using Pc = complex<R>;

void fft(int s, bool type, Pc c[]) {
    const int N = 1<<s;
    Pc *a = new Pc[N];
    Pc *b = new Pc[N];
    copy_n(c, N, a);
    for (int i = 1; i <= s; i++) {
        int H = 1<<(i-1), W = 1<<(s-i);
        Pc base = polar<R>(1, (type? -PI : PI) / H);
        Pc now = Pc(1, 0);
        for (int y = 0; y < (N>>1); y += W) {
            for (int x = 0; x < W; x++) {
                auto l = a[y<<1 | x];
                auto r = now * a[y<<1 | x | W];
                b[y | x] = l+r;
                b[y | x | N>>1] = l-r;
            }
            now *= base;
        }
        swap(a, b);
    }
    copy_n(a, N, c);
    delete[] a;
    delete[] b;
}

const int S = 18;
const int M = 1<<S;

ll res[2*M];
void mer(ll a[], ll b[]) {
    static Pc x[2*M], y[2*M];
    for (int i = 0; i < 2*M; i++) {
        x[i] = Pc(a[i], 0);
        y[i] = Pc(b[i], 0);
    }
    fft(S+1, false, x);
    fft(S+1, false, y);
    static Pc z[2*M];
    for (int i = 0; i < 2*M; i++) {
        z[i] = x[i]*y[i];
    }
    fft(S+1, true, z);
    for (int i = 0; i < 2*M; i++) {
        z[i] *= 1.0 / (1<<(S+1));
    }
    for (int i = 0; i < 2*M; i++) {
        res[i] = (ll)(round(z[i].real()));
    }
}



int main() {
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);

    static ll cl[2*M], cr[2*M];

    static ll al[2*M], ar[2*M];
    fill_n(al, 2*M, 0);
    fill_n(ar, 2*M, 0);

    int sm = 0;
    al[0]++;
    ar[M-0]++;
    for (int i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        sm += a;
        al[sm]++; ar[M-sm]++;
    }
    mer(al, ar);

    for (int i = M+1; i < 2*M; i++) {
        cl[i-M] = res[i];
    }

    fill_n(al, 2*M, 0);
    fill_n(ar, 2*M, 0);

    sm = 0;
    al[0]++;
    ar[M-0]++;
    for (int i = 0; i < m; i++) {
        int a;
        scanf("%d", &a);
        sm += a;
        al[sm]++; ar[M-sm]++;
    }
    mer(al, ar);

    for (int i = M+1; i < 2*M; i++) {
        cr[M-(i-M)] = res[i];
    }

    mer(cl, cr);

    for (int i = 0; i < q; i++) {
        int c;
        scanf("%d", &c);
        if (c == 0) {
            printf("%lld\n", res[M]);
        } else {
            printf("%lld\n", res[M-c]+res[M+c]);
        }
    }

    return 0;
}

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

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();

    int ans = 1e9;
    for (int i = 0; i <= n-m; ++i) {
        int cnt = 0;
        for (int j = 0; j < m; ++j) {
            if(s[i+j] != t[j]) cnt++;
        }
        ans = min(ans, cnt);
    }

    cout << ans << endl;
}


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

// macro
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define all(v) v.begin(), v.end()

// code starts
#define MOD 1000000007

ll pow(ll a, ll x)
{
	ll left=x;
	ll ret=1;
	ll ks=a;
	while(left>0)
	{
		if(left%2==1)ret=ret*ks%MOD;
		left/=2;
		ks=ks*ks%MOD;
	}
	return ret;
}

int main()
{
	ll n,k;cin>>n>>k;
	vector<ll> count(k+1,0);
	int i,j;
	for(i=k;i>=1;i--)
	{
		count[i]=pow(k/i,n);
		for(j=i*2;j<=k;j+=i)
		{
			count[i]+=MOD-count[j];
			count[i]%=MOD;
		}
	}
	ll ans=0;
	for(i=1;i<=k;i++)
	{
		ans=ans+count[i]*i%MOD;
		ans%=MOD;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 3996
from collections import defaultdict

N=int(input())
d = defaultdict(int)
for D in input().split():
    d[int(D)]+=1
M=int(input())
T=[int(i) for i in input().split()]

for t in T:
    if d[t]>=1:
        d[t]-=1
    else:
        print('NO')
        exit()
print('YES')

Measured memory_bytes: 46176
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            var list = new List<int>();
            for (int i = 0; i < n; i++)
            {
                list.Add(int.Parse(Console.ReadLine()));
            }
            list = list.OrderBy(x => x).ToList();
            list.Add(0);
            int now = list.First();
            bool exist = true;
            int ans = 0;
            for (int i = 0; i < n; i++)
            {
                if (now == list[i + 1])
                {
                    exist = !exist;
                }
                else
                {
                    if (exist) ans++;
                    now = list[i + 1];
                    exist = true;
                }
            }
            Console.WriteLine(ans);
        }
    }
}

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


int main(){
    int n;
    cin >> n;
    vector<ll> a(n), b;
    rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());
    int j = n - 1, k = 0;
    ll a1 = 0, a2 = 0;
    while (j > 0){
        if (a[j] == a[j - 1]){
            a1 = a[j];
            k = j - 2;
            break;
        }
        else j--;
    }
    while (k > 0){
        if (a[k] == a[k - 1]){
            a2 = a[k];
            break;
        }
        else k--;
    }
    cout << a1 * a2 << endl;
}

Measured memory_bytes: 1024
# DPL 3 A

def solve():
    H, W = map(int, input().split())
    c = [list(map(int, input().split())) for _ in range(H)]
    dp = [[0] * (W+1) for _ in range(H+1)]

    ans = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if c[i-1][j-1] == 1:
                dp[i][j] == 0
            else:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                ans = max(ans, dp[i][j])

    print(ans**2)


if __name__ == "__main__":
    solve()



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

int A[50],n;
int solve(int i,int m)
{
    if(m==0)
        return 1;
    if(i>=n)
        return 0;
    return solve(i+1,m)||solve(i+1,m-A[i]);
}

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

    int q,x;
    cin>>q;
     for(int i=0;i<q;i++)
    {
        cin>>x;
        if(solve(0,x))cout<<"yes\n";
        else cout<<"no\n";
    }
    return 0;

}

Measured memory_bytes: 3056
#include<cstdio>
#include<algorithm>
#include<set>
struct node{
	int x,y;
	bool operator<(node b)const{
		return x<b.x;
	}
}a[200100];
int n;
long long ans=0x3f3f3f3f3f3f3f3f;
std::multiset<int>A,B;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
		if(a[i].x<a[i].y)std::swap(a[i].x,a[i].y);
		A.insert(a[i].x),B.insert(a[i].y);
	}
	std::sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		A.erase(A.find(a[i].x));
		B.insert(a[i].x);
		B.erase(B.find(a[i].y));
		A.insert(a[i].y);
	  	ans=std::min(ans,(long long)(*A.rbegin()-*A.begin())*(*B.rbegin()-*B.begin()));
	}
	printf("%lld\n",ans);
} 

Measured memory_bytes: 23540
{-# LANGUAGE BangPatterns #-}
module Main (main) where

import Data.ByteString (ByteString)
import qualified Data.ByteString.Char8 as C8
import Data.Bool
import Data.Maybe
import Data.Char

main :: IO ()
main = do
  [n,k] <- readInts
  [s] <- readByteStrings
  print . showAnswer . solve $ (n,k,s)

type Input  = (Int,Int,ByteString)
type Output = ByteString

solve :: Input -> Output
solve (n,k,s) = C8.concat [s1, C8.singleton (toLower c), s3]
  where
    (s1, s2) = C8.splitAt (k-1) s
    c = C8.head s2
    s3 = C8.tail s2

showAnswer :: Output -> Answer
showAnswer = ByteString

-- utils
readInts :: IO [Int]
readInts = map (fst . fromJust . C8.readInt) . C8.words <$> C8.getLine

readStrings :: IO [String]
readStrings = map C8.unpack . C8.words <$> C8.getLine

readByteStrings :: IO [ByteString]
readByteStrings = C8.words <$> C8.getLine

data Answer
  = YesNo Bool
  | YESNO Bool
  | AB Bool
  | Number Int
  | String String
  | ByteString ByteString
  | Compare Ordering
  | Compare2 Ordering

instance Show Answer where
  show (YesNo b)       = bool "No" "Yes"  b
  show (YESNO b)       = bool "NO" "YES"  b
  show (AB b)          = bool "B"  "A"    b
  show (Number i)      = show i
  show (String s)      = s
  show (ByteString bs) = C8.unpack bs
  show (Compare o)     = ordering "<" "=" ">" o
  show (Compare2 o)    = ordering "Right" "Balanced" "Left" o

ordering :: a -> a -> a -> Ordering -> a
ordering lt eq gt o = case o of
  LT -> lt
  EQ -> eq
  GT -> gt



Measured memory_bytes: 380
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

	public static void main(String[] args) throws IOException {

		List<Double> list = new ArrayList<Double>();

		List<Integer> cnt = new ArrayList<Integer>();

		for(int i = 0; i < 6; i++){
			cnt.add(0);
		}


		InputStreamReader is = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(is);

		Integer num = Integer.parseInt(br.readLine());

		for(int i = 0; i < num; i++){

			list.add(Double.parseDouble(br.readLine()));

			if(list.get(i) < 165.0){
				cnt.set(0, cnt.get(0) + 1);
			} else if(165.0 <= list.get(i) && list.get(i) < 170.0){
				cnt.set(1, cnt.get(1) + 1);
			} else if(170.0 <= list.get(i) && list.get(i) < 175.0){
				cnt.set(2, cnt.get(2) + 1);
			} else if(175.0 <= list.get(i) && list.get(i) < 180.0){
				cnt.set(3, cnt.get(3) + 1);
			} else if(180.0 <= list.get(i) && list.get(i) < 185.0){
				cnt.set(4, cnt.get(4) + 1);
			} else{
				cnt.set(5, cnt.get(5) + 1);
			}
		}

		for(int i = 0; i < 6; i++){

			System.out.print(i + 1 + ":");

			for(int j = 0; j < cnt.get(i); j++){
				System.out.print("*");
			}
			System.out.println("");
		}
	}
}

Measured memory_bytes: 24200
import numpy as np

# 何日目かは1~N 添え字は0~N-1
# dp[i][k] i日目でk番目の行動をしたときの幸福度の最大値　（k=0:A, 1:B, 2:C)
# 解答はmax(dp[N-1])
# dp[i][0]=max(dp[i-1][1]+a[i], dp[i-1][2]+a[i])
# dp[i][1]=max(dp[i-1][0]+b[i], dp[i-1][2]+b[i])
# dp[i][2]=max(dp[i-1][0]+c[i], dp[i-1][1]+c[i])

# 入力
N = int(input().strip())
h = []
for i in range(N):
    h.append(list(map(int, input().strip().split())))
H = np.array(h)

# 初期化
dp = np.zeros(N * 3, dtype=np.int).reshape(N, 3)

dp[0][0] = H[0][0]
dp[0][1] = H[0][1]
dp[0][2] = H[0][2]

for i in range(N-1):
    dp[i + 1][0] = max(dp[i][1] + H[i + 1][0], dp[i][2] + H[i + 1][0])
    dp[i + 1][1] = max(dp[i][0] + H[i + 1][1], dp[i][2] + H[i + 1][1])
    dp[i + 1][2] = max(dp[i][0] + H[i + 1][2], dp[i][1] + H[i + 1][2])

print(max(dp[N - 1]))


Measured memory_bytes: 44216