akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define LOCAL
#pragma region Macros
typedef long long ll;
#define ALL(x) (x).begin(),(x).end()
const long long MOD=1e9+7;
// const long long MOD=998244353;
const int INF=1e9;
const long long IINF=1e18;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
const char dir[4]={'D','R','U','L'};

template<typename T>
istream &operator>>(istream &is,vector<T> &v){
    for (T &x:v) is >> x;
    return is;
}
template<typename T>
ostream &operator<<(ostream &os,const vector<T> &v){
    for (int i=0;i<v.size();++i){
        os << v[i] << (i+1==v.size()?"": " ");
    }
    return os;
}
template<typename T,typename U>
ostream &operator<<(ostream &os,const pair<T,U> &p){
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}
template<typename T,typename U>
ostream &operator<<(ostream &os,const map<T,U> &m){
    os << '{';
    for (auto itr=m.begin();itr!=m.end();++itr){
        os << '(' << itr->first << ',' << itr->second << ')';
        if (++itr!=m.end()) os << ',';
        --itr;
    }
    os << '}';
    return os;
}
template<typename T>
ostream &operator<<(ostream &os,const set<T> &s){
    os << '{';
    for (auto itr=s.begin();itr!=s.end();++itr){
        os << *itr;
        if (++itr!=s.end()) os << ',';
        --itr;
    }
    os << '}';
    return os;
}

void debug_out(){cerr << '\n';}
template<class Head,class... Tail>
void debug_out(Head&& head,Tail&&... tail){
    cerr << head;
    if (sizeof...(Tail)>0) cerr << ", ";
    debug_out(move(tail)...);
}
#ifdef LOCAL
#define debug(...) cerr << " ";\
cerr << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << '\n';\
cerr << " ";\
debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

template<typename T> T gcd(T x,T y){return y!=0?gcd(y,x%y):x;}
template<typename T> T lcm(T x,T y){return x/gcd(x,y)*y;}

template<class T1,class T2> inline bool chmin(T1 &a,T2 b){
    if (a>b){a=b; return true;} return false;
}
template<class T1,class T2> inline bool chmax(T1 &a,T2 b){
    if (a<b){a=b; return true;} return false;
}
#pragma endregion

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,K; cin >> N >> K;
    vector<int> P(N),C(N);
    for (int i=0;i<N;++i) cin >> P[i],--P[i];
    for (int i=0;i<N;++i) cin >> C[i];
    ll ans=-IINF;
    for (int i=0;i<N;++i){
        int now=i;
        vector<ll> cnt(N+1,0);
        vector<int> used(N,0);
        int cycle=1;
        for (int j=0;j<N;++j,++cycle){
            used[now]=1;
            now=P[now];
            cnt[j+1]=cnt[j]+C[now];
            if (used[now]) break;
        }
        if (K<=cycle||cnt[cycle]<=0){
            for (int j=1;j<=min(cycle,K);++j) chmax(ans,cnt[j]);
            continue;
        }
        ll sum=cnt[cycle]*((K-cycle)/cycle);
        int nK=K-(K-cycle)/cycle*cycle;
        for (int j=1;j<=N;++j){
            chmax(ans,sum+(j<=nK%cycle?cnt[cycle]:0)+cnt[j]);
        }
    }
    cout << ans << '\n';
}

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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3

ll n,k;

int main(){
	cin>>n>>k;
  ll res=INF;
  rep(i,n){
    ll a=1;
    rep(j,i+1)a*=2;
    rep(j,n-i-1)a+=k;
    minch(res,a);
  }
  cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<limits>
#include<string.h>
#include<vector>
#include<stack>
#include<queue>
using namespace std;


int main()
{
	int n, m, c;
	int b[25],a[25][25];
	cin >> n >> m >> c;
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	int d = 0;
	int e = 0;
	for (int i = 0; i < n; i++) {
		e = 0;
		for (int j = 0; j < m; j++) {
			e = e + b[j] * a[i][j];
		}
		e = e + c;
		if (e > 0) {
			d++;
		}
	}
	cout << d;
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#pragma GCC optimize("Os")
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);
#define FO cout.tie(NULL);
#define FI cin.tie(NULL);
#define IN cin>>
#define OUT cout<<
#define loop(i,a,n) for(ll i=a; i<n; i++)
#define rloop(i,a,n) for(int i=a; i>=n; i--)
#define endl "\n";
#define pb push_back
#define mp make_pair
#define set_bits(a) __builtin_popcountll(a)
#define ll long long int
#define ld long double
#define vll vector<long long int>
#define pll pair<long long int, long long int>
#define mod 1000000007
#define M 998244353
using namespace std;
ll gcd(ll a, ll b)
{
    return (b?gcd(b,a%b):a);
}
ll P(ll B, ll power, ll modulo)
{
    ll ans=1LL;
    while(power>0LL)
    {
        if(power%2LL==1LL)
        {
            ans=(ans*B)%modulo;
        }
        B=(B*B)%modulo;
        power/=2LL;
    }
    return ans;
}
bool isPrime(ll n)
{
    if(n<=1LL)
    {
        return false;
    }
    if(n<=3LL)
    {
        return true;
    }
    if(n%2==0LL || n%3==0LL)
    {
        return false;
    }
    for(ll i=5LL; (i*i)<=n; i+=6LL)
    {
        if(n%i==0LL || n%(i+2LL)==0LL)
        {
            return false;
        }
    }
    return true;
}
void vok()
{
    FAST
    FO
    FI
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        freopen("error.txt","w",stderr);
    #endif
}
const int mxN=int(5e5)+100;
vll fac(mxN), ifac(mxN);
ll ncr(ll n, ll r)
{
    ll res=fac[n];
    res*=ifac[n-r];
    res%=mod;
    res*=ifac[r];
    res%=mod;
    return res;
}
int main()
{
    vok();
    fac[0]=fac[1]=1LL;
    ifac[0]=P(fac[0],mod-2,mod);
    ifac[1]=ifac[0];
    loop(i,2,mxN)
    {
        fac[i]=((ll)(i)*fac[i-1])%mod;
        ifac[i]=P(fac[i],mod-2,mod)%mod;
    }
    ll n,m;
    IN n>>m;
    ll ans=ncr(m,n)*fac[n];
    ans%=mod;
    vll dp(n+1,0);
    dp[0]=1;
    dp[1]=m-n;
    loop(i,2,n+1)
    {
        dp[i]=(dp[i-1]*(i+m-n-1))%mod;
        dp[i]+=((dp[i-2]*(i-1))%mod);
        dp[i]%=mod;
    }
    ans*=dp[n];
    ans%=mod;
    OUT ans<<endl
    return 0;
}

Measured memory_bytes: 14724
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;

int main() {
        int n;
        scanf("%d", &n);
        string s;
        cin >> s;
        map<pair<string, string>, int> cnt;
        string hoge = s.substr(0, n);
        string fuga = s.substr(n, n);
        reverse(fuga.begin(), fuga.end());
        for (int i = 0; i < (1 << n); i ++) {
                string unko = "";
                for (int j = 0; j < n; j ++) {
                        if ((i >> j) & 1) {
                                unko += hoge[j];
                        }
                }
                string unko2 = "";
                for (int j = n - 1; j >= 0; j --) {
                        if (!((i >> j) & 1)) {
                                unko2 += hoge[j];
                        }
                }
                cnt[make_pair(unko, unko2)] ++;
        }
        long long ans = 0;
        for (int i = 0; i < (1 << n); i ++) {
                string unko = "";
                for (int j = 0; j < n; j ++) {
                        if ((i >> j) & 1) {
                                unko += fuga[j];
                        }
                }
                string unko2 = "";
                for (int j = n - 1; j >= 0; j --) {
                        if (!((i >> j) & 1)) {
                                unko2 += fuga[j];
                        }
                }
                ans += cnt[make_pair(unko, unko2)];
        }
        printf("%lld\n", ans);
        return 0;
}


Measured memory_bytes: 91904
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <numeric>

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int main() {
    int n;
    vector<int> p;
    int ans = 0;

    cin >> n;

    for (int i = 0; i < n; i++){
        int pp;
        cin >> pp;
        p.push_back (pp);
    }

    for (int i = 2; i < n; i++){
        if ((p[i] < p[i-1] && p[i-1] < p[i-2]) || (p[i] > p[i-1] && p[i-1] > p[i-2])) ans++;
    }

    cout << ans << endl;
}

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

int main(){
  int a, b, k;
  cin >> a >> b >> k;
  
  int n = min(a, b);
  
  int cnt = 0;
  
  for (int i = n; i >= 1; i--) {
    if (a % i == 0 &&b % i == 0) {
      cnt++;
    }
    if (cnt == k) {
      cout << i << endl;
      return 0;
    }
  }
  
  
}

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

char c[3][3];

int main(){
    for(int i=0;i<2;i++){
        for(int j=0;j<3;j++){
            char a;
            cin>>a;
            c[i][j]=a;
        }
    }
    if(c[0][0]==c[1][2]&&c[0][1]==c[1][1]&&c[0][2]==c[1][0]){
        cout<<"YES"<<endl;
    }
    else cout<<"NO"<<endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,a[105];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	int a1=0,b1=0;
	for(int i=n-1;i>=0;i-=2){
			a1+=a[i];
	}
	for(int i=n-2;i>=0;i-=2){
		b1+=a[i];
	}
	cout<<a1-b1<<endl;
return(0);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

// 素数判定O(√n)
bool is_prime(ll n){
    if(n==1) return false;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0) return false;
    }
    return true;
}

vector<int> a(100010);

int main(){
    for(int i=1;i<100010;i+=2){
        if(is_prime(i) && is_prime((i+1)/2)) a[i]=1;
    }

    vector<int> s(100010,0);
    rep(i,100010) s[i+1]=s[i]+a[i];

    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        r++;
        cout<<s[r]-s[l]<<endl;
    }
    return 0;
}

 

Measured memory_bytes: 1408
import std.stdio, std.conv, std.string;
import std.algorithm, std.array, std.container;
import std.numeric, std.math;
import core.bitop;

T RD(T = string)() { static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }
T[] ARR(T)(in string str) { return str.split.to!(T[]); }
size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

long mod = pow(10, 9) + 7;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

struct UnionFind
{
	void init(long n) { par = new long[](n); foreach (i; 0..n) par[i] = i; }
	long root(long i) { return par[i] == i ? i : (par[i] = root(par[i])); }
	bool same(long i, long j) { return root(i) == root(j); }
	void unite(long i, long j) { i = root(i); j = root(j); if (i == j) return; par[i] = j; }
	long[] par;
}

void main()
{
	auto N = RD!long;
	auto K = RD!long;

	writeln(N / 2 + (N % 2) >= K ? "YES" : "NO");
	stdout.flush();
}

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

int main()
{
  int height,width;
  cin >> height >> width;
  
  for(int i = 0; i < height + 2; i++)
    for(int r = 0; r < width + 2; r++)
    {
      if(i == 0)
      {
        cout << "#";
        if(r == width + 1)
        {
          cout << endl;
        }        
        continue;
      }
      else if(i == height + 1)
      {
         cout << "#";
        if(r == width + 1)
        {
          cout << endl;
        }        
        continue;
      }
        
      if(r == 0)
      {
        cout << "#";
        continue;
      }
      else if(r == width + 1)
      {
        cout << "#" << endl;
        continue;
      }
      char pixel;
      cin >> pixel;
      cout << pixel;
    }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>

int cmp(const void* a,const void* b){
	return *((int *)b)-*((int *)a);
}

int main(void){
		int n=0,tmp=0,cnt=1;
		scanf("%d",&n);
		int d[n];
		for(int i=0;i<n;i++){
			scanf("%d", &d[i]);
		}
		qsort(d,n,sizeof(d[0]),cmp);
		tmp=d[0];
		for(int i=1;i<n;i++){
			if(tmp>d[i]){
				tmp=d[i];
				cnt++;
			}
		}
		printf("%d",cnt);

		return 0;
}


Measured memory_bytes: 128
# include <bits/stdc++.h>
# define rr register
const int N=100010,INF=0x3f3f3f3f;
inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
int main(void){
	int n=read();
	for(rr int i=1;i<=n;++i){
		int x=read();
		if(x%2==0&&(!(x%3==0||x%5==0))){
			puts("DENIED");
			return 0;
		}
	}
	puts("APPROVED");
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define rep(i,q) for(int i = 0; q > i; i++)
#define dep(i,q) for(int i = q; 0 < i; i--)
int main(){
  int n,x;
  cin >> n >> x;
  int a[n];
  rep(i,n) cin >> a[i];
  long long kekka = 0;
  if(a[0] > x){
    kekka += a[0] - x;
    a[0] = x;
  }
  rep(i,n-1){
    if(x < a[i] + a[i+1]){
      kekka += a[i+1] - (x-a[i]);
      a[i+1] = x-a[i];
    }
  }
  cout << kekka << endl;
  return 0;
}

Measured memory_bytes: 640
use proconio::input;

// はじめにxは絶対値をとって共通して正にいることにする
// 1. 往復にたどり着く前にKを使い切る
//   - 答え: x - d * k
//   - 制約: x - d * k > 0, d * k でオーバーフロー
//      - x >= dk -> x / d > kで解決！
// 2. 往復する
//   - 往復にたどり着くまで: x / d
//   - その後 -d, +d を繰り返す( k - x / d = k'回 -> 偶数or奇数)

fn main() {
    input! {
        mut x: i64,
        mut k: i64,
        d: i64,
    }

    x = x.abs();

    if (x/d > k) {
        // 往復にたどり着くまでにKを使い切る
        println!("{}", x - d * k);
    } else {
        // 往復し始めるのはe回目
        let e = x / d;
        k -= e;
        x %= d;
        if k % 2 == 1 {
            x = (x - d).abs();
        }
        println!("{}", x);
    }
}


Measured memory_bytes: 2176
// C++ code to find number of distinct numbers
// in a subarray
#include<bits/stdc++.h>
using namespace std;
  
const int MAX = 500005;
  
// structure to store queries
struct Query
{
    int l, r, idx;
};
  
// cmp function to sort queries according to r
bool cmp(Query x, Query y)
{
    return x.r < y.r;
}
  
// updating the bit array
void update(int idx, int val, int bit[], int n)
{
    for (; idx <= n; idx += idx&-idx)
        bit[idx] += val;
}
  
// querying the bit array
int query(int idx, int bit[], int n)
{
    int sum = 0;
    for (; idx>0; idx-=idx&-idx)
        sum += bit[idx];
    return sum;
}
  
void answeringQueries(int arr[], int n, Query queries[], int q)
{
    // initialising bit array
    int bit[n+1];
    memset(bit, 0, sizeof(bit));
  
    // holds the rightmost index of any number
    // as numbers of a[i] are less than or equal to 10^6
    int last_visit[MAX];
    memset(last_visit, -1, sizeof(last_visit));
  
    // answer for each query
    int ans[q];
    int query_counter = 0;
    for (int i=0; i<n; i++)
    {
        // If last visit is not -1 update -1 at the
        // idx equal to last_visit[arr[i]]
        if (last_visit[arr[i]] !=-1)
            update (last_visit[arr[i]] + 1, -1, bit, n);
  
        // Setting last_visit[arr[i]] as i and updating
        // the bit array accordingly
        last_visit[arr[i]] = i;
        update(i + 1, 1, bit, n);
  
        // If i is equal to r of any query  store answer
        // for that query in ans[]
        while (query_counter < q && queries[query_counter].r == i)
        {
            ans[queries[query_counter].idx] =
                     query(queries[query_counter].r + 1, bit, n)-
                     query(queries[query_counter].l, bit, n);
            query_counter++;
        }
    }
  
    // print answer for each query
    for (int i=0; i<q; i++)
        cout << ans[i] << endl;
}
  
// driver code
int main()
{
    
    
    int n;
    cin >> n;
    int q;
    cin >> q;
    int a[n];
    for(int i=0; n>i; i++){
        cin >> a[i];
    }
    Query queries[q];
    for(int i=0; q>i; i++){
        cin >> queries[i].l >> queries[i].r;
        queries[i].l--;
        queries[i].r--;
        queries[i].idx = i;
    }
    
    sort(queries, queries+q, cmp);
    
    answeringQueries(a, n, queries, q);
}


Measured memory_bytes: 17396
#include <stdio.h>

#define MAX 45

int main() {
  int fib[MAX], n, i;

  scanf("%d", &n);

  fib[0] = fib[1] = 1;

  for (i = 2; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
  }

  printf("%d\n", fib[n]);
  
  return 0;
}



Measured memory_bytes: 2108
#include <bits/stdc++.h>
using namespace std;
vector<long long>d;

int main() {
	long long x,y,a,b,c;
	long long sum=0;

	cin >> x>>y>>a>>b>>c;
	vector<long long> p(a);
	for(int i=0;i<a;i++){
		cin >> p[i];
	}
	vector<long long> q(b);
	for(int i=0;i<b;i++){
		cin >> q[i];
	}
	vector<long long> r(c);
	for(int i=0;i<c;i++){
		cin >> r[i];
	}
	sort(p.begin(),p.end());
	reverse(p.begin(),p.end());
	sort(q.begin(),q.end());
	reverse(q.begin(),q.end());
	sort(r.begin(),r.end());
	reverse(r.begin(),r.end());
	for(int i=0;i<x;i++){
		d.push_back(p[i]);
	}
	for(int i=0;i<y;i++){
		d.push_back(q[i]);
	}
	long long t;
	t=min(c,x+y);
	for(int i=0;i<t;i++){
		d.push_back(r[i]);
	}
	sort(d.begin(),d.end());
	reverse(d.begin(),d.end());
	for(int i=0;i<x+y;i++){
		sum +=d[i];
	}
	cout << sum <<endl;
	return 0;
}


Measured memory_bytes: 8688
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin, (x).end()

int main(){
	int n; cin>>n;
	int x,y; cin>>x>>y;
	bool flag = false;
	
	for(int i=x; i<=y; i++){
		if(i%n==0){
			flag =true;
			break;
		}
	}
	if(flag)cout<<"OK"<<endl;
	else cout<<"NG"<<endl;
	return 0;
}

Measured memory_bytes: 3632
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
const int INF = 1e9;
const ll mod = ll(1e9)+7;

int main() {
  ll n, k, total = 0;
  cin >> n >> k;
  ll min = 0, max = 0;
  rep(i, k) {
    min += i;
    max += n-i;
  }
  for(int i = k; i <= n+1; ++i) {
    total %= mod;
    total += (max - min + 1) % mod;
    if (i == n + 1) break;
    min += i;
    max += n - i;
  }
  cout << total << endl;
}

Measured memory_bytes: 3596
#include <iostream>
#include <set>
using namespace std;
typedef pair<int, int> P;
int main(void){
    int n, ans = 0;
    set<P> s;
    cin >> n;
    for(int i=0;i<n;i++){
        int a;
        cin >> a;
        a *= -1;
        auto itr = s.upper_bound(P(a, n));
        if(itr == s.end()){
            s.insert(P(a, ans++));
        }else{
            int c = itr->second;
            s.erase(itr);
            s.insert(P(a, c));
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 4992
sx,sy,tx,ty = map(int,input().split())
x,y = tx-sx,ty-sy
ans = "U"*y+"R"*x+"D"*y+"L"*(x+1)+"U"*(y+1)+"R"*(x+1)+"DR"+"D"*(y+1)+"L"*(x+1)+"U"
print(ans)

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

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  
  if (A >= B && B >= C || A >= C && A >= B) {
    cout << A * 10 + B + C<< endl;
  } else if (B >= A && A >= C || B >= C && C >= A) {
    cout << B * 10 + A + C << endl;
  } else if (C >= A && A >= B || C >= B && B >= A) {
    cout << C * 10 + A + B << endl;
  }
}

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

int sort(const void *a, const void *b)
    {
    return *(int*)a - *(int*)b;
    }
    
int main(void){
    int n;
    scanf("%d",&n);
    int a[n],x[n];
    for (int i=0; i<n; i++){
        scanf("%d",&x[i]);
        a[i]=x[i];
    }
    
    qsort (a,n,sizeof(int),sort);
    
    for (int i=0; i<n; i++){
        if(x[i]>=a[n/2]){
            printf ("%d\n",a[n/2-1]);
        } else {
            printf ("%d\n",a[n/2]);
        }
    }
    return 0 ;
}

Measured memory_bytes: 3692
N = int(input())

A = []

for i in range(N):
  A.append(int(input()))

max_value = max(A)           

max_index = A.index(max_value)

B = A[:]

del B[max_index]

if max(B) == max_value:
  for i in range(N):
    print(max_value)
else:
  for i in range(N):
    if A[i] == max_value:
      print(max(B))
    else:
      print(max_value)


Measured memory_bytes: 70104
# include <bits/stdc++.h>
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
using namespace std;
using ll = long long;
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 main()
{
    ll n,k;
    cin >> n >> k;

    ll a = n/k;

    ll ans = min(n-k*a,k*(a+1)-n);

    cout << ans << endl;
}

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

using namespace std;

int main() {
    int n;
    cin >> n;
    vector< vector<int> > a(2, vector<int>(n));
    for (int i = 0; i < 2; ++i) for (int j = 0; j < n; ++j) cin >> a.at(i).at(j);
    int max = a.at(0).at(0);
    for (int i = 0; i < a.at(1).size(); ++i) max += a.at(1).at(i);
    int now = max;
    for (int i = 1; i < n; ++i) {
        now = now - a.at(1).at(i - 1) + a.at(0).at(i);
        if (max < now) max = now;
    }
    cout << max << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int main()
{
    int n,a[105][105]={0},b[105][105]={0};
    scanf("%d",&n);
    for(int i=1;i<=2;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
        }
    b[1][1]=a[1][1];
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==1)
                b[i][j]=b[i][j-1]+a[i][j];
            else
                b[i][j]=max(b[i-1][j],b[i][j-1])+a[i][j];
            }
        }
    printf("%d\n",b[2][n]);
    return 0;
}

Measured memory_bytes: 384
import java.io.IOException;
import java.util.Scanner;

public class Main {

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

		new Main().run();
	}

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		h = scanner.nextInt();
		w = scanner.nextInt();
		n = scanner.nextInt();
		map = new char[h][w];
		for (int i = 0; i < h; i++)
			map[i] = scanner.next().toCharArray();
		dp = new int[3][h + 1][w + 1];
		for (int i = 1; i <= h; i++)
			for (int j = 1; j <= w; j++)
				for (int k = 0; k < 3; k++)
					dp[k][i][j] = dp[k][i - 1][j] + dp[k][i][j - 1]
							- dp[k][i - 1][j - 1] + (map[i - 1][j - 1] == c[k] ? 1
							: 0);
		ans = new int[3];
		while (n-- > 0) {
			int a = scanner.nextInt() - 1;
			int b = scanner.nextInt() - 1;
			int c = scanner.nextInt();
			int d = scanner.nextInt();
			for (int i = 0; i < 3; i++)
				ans[i] = dp[i][c][d] - dp[i][c][b] - dp[i][a][d] + dp[i][a][b];
			System.out.printf("%d %d %d\n", ans[0], ans[1], ans[2]);
		}
	}

	int w, h, n;
	int[] ans;
	int[][][] dp;
	char[][] map;
	char[] c = { 'J', 'O', 'I' };

}

Measured memory_bytes: 184708
from collections import Counter


N = int(input())
A = list(map(int, input().split()))


c = Counter(A)
for k,v in c.items():
    if k == 0:
        if N % 2 == 0:
            if v != 0:
                print(0)
                exit()
        else:
            if v != 1:
                print(0)
                exit()
    else:
        if v!= 2:
            print(0)
            exit()
import math
print(pow(2, math.floor(N/2), 10**9 + 7))

Measured memory_bytes: 14820
import numpy as np
from numba import njit

N = int(input())
scores = np.array(list(map(int, input().split())), dtype='int64')
dpt = np.full((N, N), -10**18, dtype='int64')

@njit('i8(i8[:],i8[:,:],i8,i8)', cache=True)
def get_max_score(scores, dpt, i, j):
    if i == j:
        dpt[i][j] = scores[i]
        return scores[i]
    else:
        if dpt[i][j] != -10**18:
            return dpt[i][j]
        result = max(scores[i] - get_max_score(scores, dpt, i+1, j), scores[j] - get_max_score(scores, dpt, i, j-1))
        dpt[i][j] = result
        return result

print(get_max_score(scores, dpt, 0, len(scores)-1))


Measured memory_bytes: 181376
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <stack>
#include <cstdio>
#include <cmath>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using P1 = pair<int, P>;
#define FOR(t, a, b) for (int t = (a); t < (b); ++t)
#define REP(t, n) FOR(t, 0, n)

int main()
{
    int N, ans = 0;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int temp;
        cin >> temp;
        ans += temp - 1;
    }
    cout << ans << endl;

    return 0;
}


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

int main() {
	long long n, m, mod,x;
	mod = pow(10, 9) + 7;
	cin >> n >> m;
	vector<long long>  data1(n + 4);
	set<long long> data;
	data1[0] = 1;
	for (long long i = 0; i < m; i++) {
		cin >> x;
		data.insert(x);
	}
	for (long long i = 0; i < n; i++) {
		if (data.find(i+1)==data.end()) data1[i + 1] = (data1[i + 1] + data1[i]) % mod;
		if (data.find(i+2)==data.end()) data1[i + 2] = (data1[i + 2] + data1[i]) % mod;
	}
	cout << data1[n] << endl;
	return 0;
}

Measured memory_bytes: 5760
import sys
import math

def f(h,w):
    r = h**2 + w**2
    ary = []
    for hi in range(1,150+1):
        for wi in range(hi+1,150+1):
            ss = hi**2+wi**2
            if ss == r and hi>h:
                ary.append({
                    "ss": ss
                    ,"h": hi
                    ,"w": wi
                })
            elif ss > r:
                ary.append({
                    "ss": ss
                    ,"h": hi
                    ,"w": wi
                })
    mino = ary[0]
    for i,o in enumerate(ary):
        if mino["ss"]>o["ss"]:
            mino = o
        elif mino["ss"]==o["ss"] and mino["h"]>o["h"]:
            mino = o
    return (mino["h"],mino["w"])

while True:
    line = sys.stdin.readline()
    line = line.split(" ")

    h = int(line[0])
    w = int(line[1])

    if h==0 and w==0:
        break

    ret = f(h,w)
    print(str(ret[0])+" "+str(ret[1]))

Measured memory_bytes: 11548
#include<iostream> 
#include<cstring>
using namespace std;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f;
int main()
{
	int a[maxn]; 
	int dp[maxn];
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	 cin>>a[i];
	memset(dp,0x3f,sizeof(dp));
	dp[1]=0;
	for(int i=2;i<=n;i++)
		for(int j=1;j<=k;j++)
		{
			if(i-j<0)
				break;
			dp[i]=min(dp[i],dp[i-j]+(abs(a[i]-a[i-j])));
		}			
	cout<<dp[n]<<endl;
	return 0;
}

Measured memory_bytes: 4372
#include <cstdio>
#include <set>
#include <tuple>

struct C { int a, b, c, d; };

int main() {
    int n;
    std::set<std::tuple<int, int, int, int>> s;
    while (~scanf("%d", &n)) {
        for (int a = 0; a < 10 && a <= n; ++a) {
            for (int b = 0; b < 10 && a + b <= n; ++b) {
                for (int c = 0; c < 10 && a + b + c <= n; ++c) {
                    for (int d = 0; d < 10 && a + b + c + d <= n; ++d) {
                        if (a + b + c + d == n) {
                            s.insert(std::make_tuple(a, b, c, d));
                        }
                    }
                }
            }
        }
        printf("%lu\n", s.size());
        s.clear();
    }
}

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

int main(void){
    string s;
    cin >> s;
    // 塊の数を数える
    int ans = 0;
    for(int i=0; i<s.length()-1; i++){
        if(s[i] != s[i+1]) ans += 1;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
typedef long long int lli;
using namespace std;
 
int main()
{
  lli a, ans;
  for(lli i=0; i<5; i++)
  {
    cin >> a;
    if(a==0) ans=i;
  }
  cout << ans+1 << endl;
  return 0;
}

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

int main() {
    int N;
    cin >> N;
    map<string,int> dict;
    for (int i=0; i<N; ++i) {
        string s;
        cin >> s;
        if (dict.count(s)) ++dict[s];
        else dict[s] = 1;
    }

    int M;
    cin >> M;
    for (int i=0; i<M; ++i) {
        string s;
        cin >> s;
        if (dict.count(s)) --dict[s];
    }

    int ans = 0;
    for (auto i = dict.begin(); i != dict.end(); ++i) {
        if (i->second>ans) ans = i->second;
    }

    cout << ans << endl;

    return 0;
}

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

int main(){
	long int a, b, c;
	scanf("%ld %ld %ld",&a, &b, &c);


	if(c-a-b>=0 && 4*a*b<(c-a-b)*(c-a-b)){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;

int n;
int nums[8];

int main() {
  scanf("%d", &n);
  while (n--) {
    for (int i=0; i<8; i++) {
      scanf("%1d", &nums[i]);
    }
    sort(nums, nums+8);

    int mini = 0;
    for (int i=0; i<8; i++) {
      mini = mini*10 + nums[i];
    }

    sort(nums, nums+8, greater<int>());

    int maxi = 0;
    for (int i=0; i<8; i++) {
      maxi = maxi*10 + nums[i];
    }

    printf("%d\n", maxi-mini);
  }
}

Measured memory_bytes: 2536
//submitted by HimJ
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define pb push_back
#define fi first
#define se second
#define fr(i,s,e) for(i=s;i<e;i++)
#define ms(arr,val) memset(arr,val,sizeof(arr))
using namespace std;
const int mxn=1e5+1;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
  int t=1;
  //cin>>t;
    while(t--){
            int a,b,c,ans=0;
            cin>>a>>b>>c;
    if(a>b)
        swap(a,b);
    if(a>c)
        swap(a,c);
    if(b>c)
        swap(b,c);
    while(a<c&&b<c)
    {
        ans++;
        a++;
        b++;
    }
    while(a<c)
    {
        a+=2;
        ans++;
    }
    if(a>b)
        swap(a,b);
    if(a>c)
        swap(a,c);
    if(b>c)
        swap(b,c);
     //cout<<a<<" "<<b<<" "<<c<<"\n";
    while(a<c&&b<c)
    {
        ans++;
        a++;
        b++;
    }
    while(a<c)
    {
        a+=2;
        ans++;
    }
    cout<<ans;

    }
  return 0;
  }



Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define NIL NULL
struct node{
  struct node *right,*left,*parent;
  int key;
};
typedef struct node *Node;
Node root;
Node findTree(Node x,int k){
  if(x==NIL||x->key==k) return x;
  if(x->key>k) return findTree(x->left,k);
  else return findTree(x->right,k);
}
void insert(int k){
  Node y=NIL;
  Node x=root;
  Node z;
  z=malloc(sizeof(struct node));
  z->key=k;
  z->left=NIL;
  z->right=NIL;
  while(x!=NIL){
    y=x;
    if(z->key<x->key) x=x->left;
    else x=x->right;
  }
  z->parent=y;
  if(y==NIL) root=z;
  else if(z->key<y->key) y->left=z;
  else y->right=z;
}
void inorder(Node x){
  if(x->left!=NIL) inorder(x->left);
  printf(" %d",x->key);
  if(x->right!=NIL) inorder(x->right);
  
}
void preorder(Node x){
  if(x!=NIL){
    printf(" %d",x->key);
  }
  if(x->left!=NIL) preorder(x->left);
  if(x->right!=NIL)  preorder(x->right);
}
int main(){
  int n,i,x;
  char c[20];
  Node f;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",c);
    if(c[0]=='f'){
      scanf("%d",&x);
      f=findTree(root,x);
      if(f!=NIL) printf("yes\n");
      else printf("no\n");
    }
    if(c[0]=='i'){
      scanf("%d",&x);
      insert(x);
    }
    else if(c[0]=='p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }
  return 0;
}

Measured memory_bytes: 19364
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <algorithm>
#include <unordered_map>
#include <iomanip>
#include <time.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<pair<int, int> > pairs(n);
  rep(i, n){
    int a;
    cin >> a;
    pairs[i] = make_pair(a, i+1);
  }
  sort(pairs.begin(), pairs.end());
  rep(i, n){
    cout << pairs[i].second;
    if(i != n-1) cout << " ";
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>
#include <numeric>
#include <iomanip>
#include <cstring> 
using namespace std;
using ll=long long;

#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define LLONG_MAXs 9223372036854775800

#include <iostream>
#include <cmath>
using namespace std;
 

 
bool isPrimeNum( ll x ){ // 素数である場合 true を返す
  if( x <= 1 ){ // 1以下である場合は素数でないことがすぐにわかる
    return false;
  }
  // sqrt( double型 ) は引数の平方根を double型で返すので、int型でキャスト
  int n = (int)sqrt( (double)x );
  for( int i = 2; i <= n; i++ ){
    if( x % i == 0 ){ // 割り切る整数がある場合、即判定終了
      return false;
    }
  }
  return true; // 割り切る整数がない場合、素数である
}

constexpr ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
constexpr ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll abs(ll a,ll b){
if(a>=b)return a-b;
if(a<b)return b-a;
}
constexpr ll min(ll a,ll b){
if(a>=b)return b;
if(a<b)return a;
}

constexpr ll max(ll a,ll b){
if(a>=b)return a;
if(a<b)return b;
}

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

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main() {
  ll N,M;

  cin>>N>>M;

  ll A[M];
  ll B[M];
  ll ans=0;
  FOR(i,0,M-1){
    cin>>A[i]>>B[i];
  }
  FOR(i,0,M-1){
    UnionFind tree(N);
    FOR(j,0,M-1){
      if(i!=j){tree.unite(A[j]-1,B[j]-1);}
    }
    int flag=0;
    FOR(j,0,M-1){
      if(!tree.same(A[j]-1,B[j]-1)){
        flag=1;
      }
    }
    if(flag==0)ans++;

  }

  cout<<M-ans<<endl;
  return 0;


 
}
 


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int main()
{
    int a[6]={0,9,909,90909,9090909,};
    int n;
    scanf("%d",&n);
    int t=n;
    int num=0,sum=0,ans=10;
    while(t)
    {num++;t/=10;}
    if(num&1)
    sum+=n-pow(10,num-1)+1;
    n-=sum;
    for(int i=1;i<=6;i++)
        if(a[i]>=n)
        {sum+=a[i-1];break;}
    printf("%d\n",sum);
    return 0;
}


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

using namespace std;
typedef long long ll;
int n,m;
int main() {
    cin>>n>>m;
    int i;
    for(i=0;i<=20;i++){
    	int t  = i*(n-1)+1;
    	if(t>=m)
    		break;
	}
	cout<<i<<endl;
    return 0;
}


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

int main(){
  int A,B,K ;
  cin >> A >> B >>K ;
  int ans ;
  int i = 0 ;
  if(A >= B){
    ans = A ;
    while(i<K){
      if(A % ans == 0 && B % ans == 0){
        i ++;
        ans --;
      }
      else{
        ans --;
      }
    }
    cout << ans+1 << endl ;
  }
  else if(A < B){
    ans = B ;
    while(i<K){
      if(A % ans == 0 && B % ans == 0){
        i ++;
        ans --;
      }
      else{
        ans --;
      }
    }
    cout << ans+1 << endl ;
  }
}

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

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

int main() {

    ll n; cin >> n;

    ll ans = 0;
    for (ll i = 1; i <= n; ++i) {
        ll t = n / i; // nまでにiの倍数が何個あるか

        ans += i * t * (t + 1) / 2; // iの倍数の数分を答えに足す
    }

    cout << ans << endl;
}

Measured memory_bytes: 3640
s=input()
if s[0] != 'A':
    print('WA')
    exit()
if s[2:len(s)-1].count('C') != 1:
    print('WA')
    exit()
for i in range(1,len(s)):
    if s[i]=='C':
        continue
    if s[i].isupper() == True:
        print('WA')
        exit()
print('AC')

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

#define mp make_pair
#define pb push_back

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> l4;


const int maxn = 2e5+1, mod = 1e9+7;
ll f[maxn], inv[maxn];
ll power(ll base, ll p)
{
  ll ret = 1;
  while (p)
    {
      if (p&1)
	ret = ret * base % mod;
      base = base * base % mod;
      p >>= 1;
    }
  return ret;
}
ll h, w, a, b;
ll cb(ll n, ll k)
{
  return f[n] * inv[k] % mod * inv[n-k] % mod;
}
inline void add(ll &a, ll b)
{
  a = a + b;
  if (a > mod)
    a %= mod;
}
int main()
{
  f[0] = 1;
  for (ll i = 1; i < maxn; ++i)
    f[i] = f[i-1] * i % mod;
  inv[maxn-1] = power(f[maxn-1], mod-2);
  for (ll i = maxn-1; i >= 1; --i)
    inv[i-1] = inv[i] * i % mod;
  scanf("%lld %lld %lld %lld", &h, &w, &a, &b);
  ll ret = 0;
  for (ll i = b+1; i <= w; ++i)
    add(ret, cb(h-a+i-2, h-a-1)*cb(a+w+1-i-2, a-1)%mod);
  printf("%lld\n", ret);
}


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

void call(int n){
  int i = 1;
 CHECK_NUM:
  int x = i;
  if ( x % 3 == 0 ){
    cout << " " << i;
    goto END_CHECK_NUM;
  }
 INCLUDE3:
  if ( x % 10 == 3 ){
    cout << " " << i;
    goto END_CHECK_NUM;
  }
  x /= 10;
  if ( x ) goto INCLUDE3;
 END_CHECK_NUM:
  if ( ++i <= n ) goto CHECK_NUM;

  cout << endl;
}

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


Measured memory_bytes: 3104
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n = f()[0]
    a = f()

    a = sorted(a)

    mx = a[-1]
    
    midiff = abs(mx/2 - a[0])
    minum = a[0]

    for i in a[:-1]:
        if abs(i - mx/2) < midiff:
            midiff = abs(mx/2 - i)
            minum = i
    
    print(mx, minum)

    

solve()


Measured memory_bytes: 14052
n = int(input())
a = list(map(int, input().split()))
from collections import defaultdict
d = defaultdict(int)

ans=1
for num in a:
    if num==0:
        ans*= (3 - d[0])
    else:
        ans*= (d[num-1] - d[num])

    ans%=1000000007
    d[num]+=1

print(ans)

Measured memory_bytes: 62252
#include<cstring>
#include<string>
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<list>
#include<set>
#include<map>
#include<sstream>
#include<climits>
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const int MAX_M = 20, MAX_N = 50000, INF = 1e9;
int n, m;
int c[MAX_M+1], dp[MAX_N+1];

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

  for (int i = 0; i <= n; ++i) dp[i] = INF;
  dp[0] = 0;

  for (int i = 1; i <= m; ++i) {
    for (int j = 0; j <= n; ++j) {
      if (j >= c[i]) dp[j] = min(dp[j], dp[j-c[i]]+1);
    }
  }

  cout << dp[n] << endl;

  return 0;
}

Measured memory_bytes: 3280
def main()
  s = gets.strip.chomp.chars
  n = s.size
  ans = []
  n.times{ ans << 0 }
  
  cnt = 0
  (0..n-1).each do |j|
    if (s[j] == 'R')
      cnt = cnt+1
    else
      ans[j] = ans[j] + cnt/2
      ans[j-1] = ans[j-1] + (cnt+1)/2
      cnt = 0
    end
  end
  (0..n-1).reverse_each do |j|
    if (s[j] == 'L')
      cnt = cnt+1
    else
      ans[j+1] = ans[j+1] + (cnt+1)/2
      ans[j] = ans[j] + (cnt)/2
      cnt = 0
    end
  end
  puts ans.join(" ")
end

main

Measured memory_bytes: 11316
#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
#define MOD 1000000007

template<class T> inline void chmax(T& a, T b) { if (a < b) a = b; }
template<class T> inline void chmin(T& a, T b) { if (a > b) a = b; }

int dp[1002][1002];
int main()
{
	string S1, S2; cin >> S1 >> S2;
	int L1 = S1.size(), L2 = S2.size();

	//memset(dp, 0, sizeof(dp));
	dp[0][0] = 0;
	for (int i = 0; i < 1001; ++i) {
		dp[i + 1][0] = dp[i][0] + 1;
		dp[0][i + 1] = dp[0][i] + 1;
	}

	for (int i1 = 0; i1 <= L1; ++i1) {
		for (int i2 = 0; i2 <= L2; ++i2) {
			if (S1[i1] == S2[i2]) dp[i1 + 1][i2 + 1] = dp[i1][i2];	//等しい
			else dp[i1 + 1][i2 + 1] = dp[i1][i2] + 1;		//置換
			chmin(dp[i1 + 1][i2 + 1], dp[i1 + 1][i2] + 1);	//削除
			chmin(dp[i1 + 1][i2 + 1], dp[i1][i2 + 1] + 1);	//挿入	
		}
	}
	cout << dp[L1][L2] << endl;
	return 0;
}



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

int main() {
  string S;
  cin >> S;
  if(S.at(0)!='k'){
    if(S.substr(S.size()-7,7)=="keyence") cout << "YES" << endl;
    else cout << "NO" << endl;
  }
  else if(S.at(S.size()-1)!='e'){
    if(S.substr(0,7)=="keyence") cout << "YES" << endl;
    else cout << "NO" << endl;
  }
  else if(S.at(0)=='k' && S.at(S.size()-1)=='e'){
    if(S.substr(0,1)=="k" && S.substr(S.size()-6,6)=="eyence") cout << "YES" << endl;
    else if(S.substr(0,2)=="ke" && S.substr(S.size()-5,5)=="yence") cout << "YES" << endl;
    else if(S.substr(0,3)=="key" && S.substr(S.size()-4,4)=="ence") cout << "YES" << endl;
    else if(S.substr(0,4)=="keye" && S.substr(S.size()-3,3)=="nce") cout << "YES" << endl;
    else if(S.substr(0,5)=="keyen" && S.substr(S.size()-2,2)=="ce") cout << "YES" << endl;
    else if(S.substr(0,6)=="keyenc" && S.substr(S.size()-1,1)=="e") cout << "YES" << endl;
    else cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i],  y[i] = map(int, input().split())


distance = 0
count = 0

for i in range(N-1):
    for j in range(i+1, N):
        distance += ((x[i] - x[j])**2 + (y[i] - y[j])**2) ** (1/2)
        count += 1

print(distance/(count/(N-1)))

Measured memory_bytes: 38356
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;

int main(){
  string s;
  cin >> s;
  int n=s.size();
  string ans={};
  rep(i,n){
    if(s[i]=='0'||s[i]=='1'){ans+=s[i];}
    if(s[i]=='B'&&ans.size()!=0){ans.pop_back();}
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main()
{
    char code[5];
    scanf("%s", code);
    int flag=0;
    for(int i=0; i<3; i++)
    {
        if(code[i]==code[i+1])
            flag=1;
    }
    if(flag==0)
        printf("Good");
    else    
        printf("Bad");
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
const int MOD=1000000007;
const int INF=1000000000;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> P;
ll N;
string s;
string ans="";
void judgement(char zero,char one)
{
  //animals.resize(N);
  char animals[100005];
  animals[0]=zero;
  animals[1]=one;
  char lastanimal;
  for (int i = 0; i < N; ++i)
    {
      if(s[i]=='o' && animals[i]=='S')
	{
	  if(i==0)
	    {
	      lastanimal=animals[i+1];
	    }
	  else if(i<N-1)
	    {
	      animals[i+1]=animals[i-1];
	    }
	  else if(i==N-1)
	    {
	      if(animals[i]==lastanimal)
		{
		  if(animals[i-1]==animals[0])
		    {
		      for(int i=0;i<N;i++) ans+=animals[i];
		    }
		}
	    }
	}
      else if(s[i]=='x' && animals[i]=='S')
	{
	  if(i==0)
	    {
	      if(animals[i+1]=='S')
		{
		  lastanimal='W';
		}
	      else
		{
		  lastanimal='S';
		}
	    }
	  else if(i<N-1)
	    {
	      if(animals[i-1]=='S')
		{
		  animals[i+1]='W';
		}
	      else
		{
		  animals[i+1]='S';
		}
	    }
	  else
	    {
	      if(animals[i]==lastanimal)
		{
		  if(animals[i-1]!=animals[0])
		    {
		      for(int i=0;i<N;i++) ans+=animals[i];
		    }
		}
	    }
	}
      else if(s[i]=='o' && animals[i]=='W')
	{
	  if(i==0)
	    {
	      if(animals[i+1]=='S')
		{
		  lastanimal='W';
		}
	      else
		{
		  lastanimal='S';
		}
	    }
	  else if(i<N-1)
	    {
	      if(animals[i-1]=='S')
		{
		  animals[i+1]='W';
		}
	      else
		{
		  animals[i+1]='S';
		}
	    }
	  else
	    {
	      if(animals[i]==lastanimal)
		{
		  if(animals[i-1]!=animals[0])
		    {
		      for(int i=0;i<N;i++) ans+=animals[i];
		    }
		}
	    }
	}
      else if(s[i]=='x' && animals[i]=='W')
	{
	  if(i==0)
	    {
	      lastanimal=animals[i+1];
	    }
	  else if(i<N-1)
	    {
	      animals[i+1]=animals[i-1];
	    }
	  else if(i==N-1)
	    {
	      if(animals[i]==lastanimal)
		{
		  if(animals[i-1]==animals[0])
		    {
		      for(int i=0;i<N;i++) ans+=animals[i];
		    }
		}
	    }
	}

    }
}
int main(void)
{
  cin >> N;
  cin >> s;
  judgement('S','S');
  judgement('S','W');
  judgement('W','S');
  judgement('W','W');
  if(int(ans.size())==0)
    {
      cout << -1 << endl;
    }
  else
    {
      for(int i=0;i<N;i++)
	{
	  cout << ans[i];
	}
      cout << endl;
      return 0;
    }
  return 0;
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define deb(x) cout << #x << "=" << x << endl
#define clr(x) memset(x, 0, sizeof(x))
#define rep(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
int M=1e9+7,N=205001;

int mm(int x,int y){x%=M,y%=M;return (x*y)%M;}//Modular Multiply
int po(int x,int y){ if(!y)return 1;int a=po(x,y/2)%M;if(y%2)return mm(a,mm(a,x));return mm(a,a);}//(x**y)%M


void solve() {
	int ans=0,c,h,w,k,i,j;
	cin>>h>>w>>k;
	char g[6][6];
	rep(i,0,h)
		rep(j,0,w)
			cin>>g[i][j];
		
	for(int bit=0;bit<(1<<(h+w));bit++){
		c=0;
		rep(i,0,h) rep(j,0,w)
			//if(g[i][j]=='#' and ((bit>>i) & 1) and ((bit>>(h+j)) &(1))) c++;
		if(g[i][j]=='#' and bit&(1<<i) and bit&(1<<(h+j))) c++;
		if(c==k) ans++; 
	}
	cout<<ans;
}
	



signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--) solve();
	return 0;
}





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

int main(){
	int n;
	cin>>n;
	ll sum=0;
	ll q=1;
//	int num=0;
	while(q<=n){
		if (q%3!=0 and q%5!=0){
//			cout<<q<<endl;
			sum+=q;
//			num++;
		}
		q++;
	}
	cout<<sum<<endl;
	return 0;
}



Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define VFOR(x,a,b) for(int x=(a);x<((a)+(b));x++)
const int INF = 987654321;
int main(){
  int H,N,A[1010],B[1010],dp[20030],maxA;
  cin >> H >> N;
  VFOR(i,0,N) cin >> A[i] >> B[i];
  VFOR(i,0,20030) dp[i] = INF;
  dp[0] = 0;
  maxA = *max_element(A,A+N);
  VFOR(i,0,N){
    for(int j = A[i]; j<=(H+maxA);j++){
      dp[j] = min(dp[j],dp[j-A[i]]+B[i]);
    }
  }
  int minMag = *min_element(dp+H,dp+H+maxA);
  cout << minMag;
  return 0;
}

Measured memory_bytes: 384