akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define si(x)	scanf("%d",&x)
#define sl(x)	scanf("%lld",&x)
#define ss(s)	scanf("%s",s)
#define pi(x)	printf("%d\n",x)
#define pl(x)	printf("%lld\n",x)
#define ps(s)	printf("%s\n",s)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
int mpow(int base, int exp); 
void ipgraph(int m);
void dfs(int u, int par);
const int mod = 1000000007;
const int N = 3e5, M = N;
//=======================

vi g[N];
char f(string s){
	char x = s[0];
	return x-'a'+'A';
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int i,n,k,j;
	string a,b,c;
	cin >> a >> b >> c;
	cout<<f(a)<<f(b)<<f(c);

	return 0;
} 

int mpow(int base, int exp) {
	base %= mod;
	int result = 1;
	while (exp > 0) {
	if (exp & 1) result = ((ll)result * base) % mod;
	base = ((ll)base * base) % mod;
	exp >>= 1;
	}
	return result;
}

void ipgraph(int m){
	int i, u, v;
	fo(i, m){
		cin>>u>>v; 
		u++, v++;
		g[u-1].pb(v-1);
		g[v-1].pb(u-1);
	}
}

void dfs(int u, int par){
	for(int v:g[u]){
		if (v == par) continue;
		dfs(v, u);
	}
}

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

int gcd(int a, int b) {
    int remain = max(a, b) % min(a, b);
    if (remain == 0) return min(a, b);
    else return gcd(min(a,b), remain);
}

int main() {
    int n;
    cin >> n;
    int x0,x1,x;
    cin >> x0 >> x1;
    int g = gcd(x0, x1);
    for (int i = 0; i < n - 2; i++) {
        cin >> x;
        g = gcd(g, x);
        if (g == 1) break;
    }
    cout << g << endl;
}


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

int main() {
    int p, q, r;
    cin >> p >> q >> r;
    cout << min({p + q, q + r, p + r}) << endl;
    return 0;
}

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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

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

const int MAX = 1000005;
const int INF = 1001001001;
const int MOD = 1000000007;

vector<int> table;
void init(int N) {
    table.resize(N);
    for (int i = 1; i < N; ++i) {
        int x = i, res = 0;
        while (x > 0 && x % 2 == 0) {
            x /= 2;
            res++;
        }
        table[i] = table[i-1] + res;
    }
}

int f(vector<int>& V) {
    int N = V.size(), res = 0;
    rep(i, N) {
        if (table[N - 1] == table[i] + table[N - 1 - i]) {
            res += V[i];
        }
    }

    if (res % 2) return 1;
    if (count(V.begin(), V.end(), 1) > 0) return 0;
    for (int &i : V) i /= 2;
    if (count(V.begin(), V.end(), V[0]) == N) return 0;
    return 2 * f(V);
}

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

    vector<int> A(N);
    rep(i, N) A[i] = S[i] - '1';

    init(N);
    cout << f(A) << endl;
}

Measured memory_bytes: 9220
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define all(x) (x).begin(), (x).end()
#define MOD 1000000007
#define MAX 1000010
ll fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
map<ll, ll> prime_factor(ll n) {
    map<ll, ll> ret;
    for(ll i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            ret[i]++;
            n /= i;
        }
    }
    if(n != 1)
        ret[n] = 1;
    return ret;
}
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while(n > 0) {
        if(n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
int main() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    map<ll, ll> alp;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        auto pf = prime_factor(a[i]);
        for(auto itr = pf.begin(); itr != pf.end(); itr++) {
            alp[itr->first] = max(alp[itr->first], itr->second);
        }
    }
    COMinit();
    ll G = 1;
    for(auto itr = alp.begin(); itr != alp.end(); itr++) {
        G *= modpow(itr->first, itr->second, MOD);
        G %= MOD;
    }
    ll ans = 0;
    vector<ll> b(n);
    for(int i = 0; i < n; i++) {
        b[i] = G * inv[a[i]];
        b[i] %= MOD;
        ans += b[i];
        ans %= MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 24448
#include <bits/stdc++.h>
#include <iostream>
#include <utility> // pair
#include <string>
#include <vector>
#define MAX_N 50
#define rep(i, a, b) for(ll i=a; i<b; i++)
#define rer(i, a, b) for(ll i=a-1; i>=b; i--)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll n, a[MAX_N];
vector<P> v;

signed main(){
    cin >> n;
    ll h, l, ih, il;
    cin >> a[0];
    h = l = a[0]; ih = il = 0;
    rep(i, 1, n){
        cin >> a[i];
        if(h < a[i]){
            h = a[i];
            ih = i;
        }
        if(l > a[i]){
            l = a[i];
            il = i;
        }
    }
    if(h + l >= 0) {
        rep(i, 0, n){
            if(i != ih){
                a[i] += h;
                v.pb(P(ih, i));
            }
        }
        rep(i, 0, n-1){
            if(a[i+1] < a[i]){
                a[i+1] += a[i];
                v.pb(P(i, i+1));
            }
        }
    }else{
        rer(i, n, 0){
            if(i != il){
                a[i] += l;
                v.pb(P(il, i));
            }
        }
        rer(i, n-1, 0){
            if(a[i+1] < a[i]){
                a[i] += a[i+1];
                v.pb(P(i+1, i));
            }
        }
    }
    cout << v.size() << endl;
    for(P e: v){
        cout << e.first + 1 << " " << e.second + 1 << endl;
    }
    // rep(i, 0, n) cout << a[i] << " ";
    // cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int64_t MOD = 1e9 + 7;

int BitCount(int64_t x) {
    x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555);
    x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);
    x = (x & 0x0f0f0f0f0f0f0f0f) + (x >> 4 & 0x0f0f0f0f0f0f0f0f);
    x = (x & 0x00ff00ff00ff00ff) + (x >> 8 & 0x00ff00ff00ff00ff);
    x = (x & 0x0000ffff0000ffff) + (x >> 16 & 0x0000ffff0000ffff);
    x = (x & 0x00000000ffffffff) + (x >> 32 & 0x00000000ffffffff);
    return (int)(x);
}

const int N_MAX = 21;
int a[N_MAX][N_MAX];
// i, s => n : i番目までの男性をマッチングさせ、マッチング済みの女性がsであるときのペアの作り方n
int64_t dp[N_MAX][1 << N_MAX];
int main() {
    #ifdef DEBUG
    std::ifstream in("/home/share/inputf.in");
    std::cin.rdbuf(in.rdbuf());
    #endif
    int N;
    cin >> N;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> a[i][j];
        }
        for(int j = 0; j < (1 << N); j++) {
            dp[i][j] = 0;
        }
    }

    for(int i = 0; i < N; i++) {
        dp[0][1 << i] = a[0][i];
    }

    for(int i = 1; i < N; i++) {
        for(int j = 0; j < (1 << N); j++) {
            if (BitCount(j) != i || dp[i - 1][j] == 0) continue;
            for(int k = 0; k < N; k++) {
                if(j & (1 << k) || !a[i][k]) continue;
                dp[i][j | (1 << k)] += dp[i - 1][j];
                dp[i][j | (1 << k)] %= MOD;
            }
        }
    }
    cout << dp[N - 1][(1 << N) - 1];
    return 0;
}

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

int main()
{
	int n;
	cin >> n;
	switch(n / 100){
		case 4:
		case 5:printf("8\n");break;
		case 6:
		case 7:printf("7\n");break; 
		case 8:
		case 9:printf("6\n");break;
		case 10:
		case 11:printf("5\n");break;
		case 12:
		case 13:printf("4\n");break;
		case 14:
		case 15:printf("3\n");break;
		case 16:
		case 17:printf("2\n");break;
		case 18:
		case 19:printf("1\n");break;
	}
	return 0;
}

Measured memory_bytes: 3620
N=int(input())
A=list(map(int,input().split()))
M=0
X=[]
XX=[0]*N
for i in range(N-1,-1,-1):
  _=0
  for j in range(i+1,N+1,i+1):
    _+=XX[j-1]
  if A[i]==0 and _%2==1:
    M+=1
    X.append(i+1)
    XX[i]=1
  elif A[i]==1 and _%2==0:
    M+=1
    X.append(i+1)
    XX[i]=1
print(M)
print(*X)

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

int main (){
    int n;
    int i;
    int count=0;
    cin >> n;
    for(i=1;i<=n;i++){
        int x;
        x=log10((double)(i))+1;
        if(x%2==1) count++;
    }
    cout << count <<endl;
    return 0;
}



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

#define CH(N,A,B) (A<=N&&N<B)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=(b-1);a<=i;i--)

using namespace std;

int main() {

  int N, W, H;
  long long ximos[100005]={}, yimos[100005]={};
  cin>>N>>W>>H;
  REP(i,0,N){
    int x, y, w;
    cin>>x>>y>>w;
    ximos[max(0,x-w)]++; ximos[min(W,x+w)]--;
    yimos[max(0,y-w)]++; yimos[min(H,y+w)]--;
  }
  REP(i,1,W+1){
    ximos[i] += ximos[i-1];
  }
  REP(i,1,H+1){
    yimos[i] += yimos[i-1];
  }
  int flagx = true, flagy = true;
  REP(i,0,W){
    if(ximos[i] == 0) flagx = false;
  }
  REP(i,0,H){
    if(yimos[i] == 0) flagy = false;
  }

  if(flagx || flagy) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;

  return 0;
}

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

struct Edge {
    int to;
    int cost;
    Edge(int t, int c) : to(t), cost(c) { }
};
using Graph = vector<vector<Edge> >;

int N;
Graph G;
vector<int> color;

//頂点0を白く塗って、dfs.
void dfs(int v, int pv, int parity){
    color[v] = parity;

    for(auto next_v : G[v]){
        if(next_v.to == pv) continue;
        if(1 & next_v.cost) dfs(next_v.to, v, 1 - parity);
        else dfs(next_v.to, v, parity);
    }
}

int main(){
    cin >> N;
    G.resize(N);
    color.assign(N,-1);
    for(int i = 0;i<N-1;++i){
        int from, to, cost; cin >> from >> to >> cost;
        from --; to --;
        //cout  << from << " " << to << endl;
        G[from].push_back(Edge(to, cost));
        G[to].push_back(Edge(from, cost));
    }
    dfs(0, -1, 0);
    for(int i=0;i<N-1;++i){
        if(color[i] != -1)continue;
        dfs(i, -1, 0);
    }
    for(int i=0;i<N;++i){
        cout << color[i] << endl;
    }
}

Measured memory_bytes: 8960
#include<bits/stdc++.h> 
using namespace std; 
typedef  pair<int, int> iPair; 
//#define mod 1000000007
#define pb push_back
typedef long long ll;
typedef long double ld;
#define FOR(i,n) for(i=0;i<n;i++)
#define FORE(i,n) for(i=0;i<=n;i++)
 
 
ll gcd(ll a , ll b)
{
   if(b==0) return a;
   a%=b;
   return gcd(b,a);
   
}
    
ll maxl(ll a,ll b){
    if(a>b)return a;
    return b;
}
 
ll minl(ll a,ll b){
    if(a>b)return b;
    return a;
}
 
ll mod = 998244353;
 
ll mulmod(ll a, ll b,ll c){ 
    ll res = 0; 
    a = a % c; 
    while (b > 0){ 
        if (b % 2 == 1){ 
            res = (res + a) % c;
        }
        a = (a * 2) % c; 
        b /= 2; 
    } 
    return res % c; 
}
 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
        if (arr[mid] == x) 
            return mid; 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
        return binarySearch(arr, mid + 1, r, x); 
    } 
    return -1; 
} 
 
int a[100005];
int tree[200005];
 
void build(int st,int low,int high){
    if(low==high){
        tree[st] = a[high]%2;
        return;
    }
    int mid = low+(high-low)/2;
    build(2*st,low,mid);
    build(2*st+1,mid+1,high);
    tree[st] = tree[2*st]+tree[2*st+1];
}
 
void update(int st,int start,int end,int ind,int val){
    if(start==end){
        tree[st] = val%2;
        return;
    }
    int mid = start+(end-start)/2;
    if(ind<=mid){
        update(2*st,start,mid,ind,val);
    }
    else update(2*st+1,mid+1,end,ind,val);
    tree[st] = tree[2*st]+tree[2*st+1];
}
 
int query(int st,int start,int end,int low,int high){
    if(start>high || end<low)return 0;
    int mid = start + (end-start)/2;
    if(start==low && end==high){
        return tree[st];
    }
    if(low>mid)return query(2*st+1,mid+1,end,low,high);
    if(high<=mid)return query(2*st,start,mid,low,high);
    return query(2*st,start,mid,low,mid)+query(2*st+1,mid+1,end,mid+1,high);
}

int main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL),cout.tie(NULL);
        int n;
        cin >> n;
        int h[n];
        for(int i=0;i<n;i++)cin >> h[i];
        int maxi = 0;
        int curr = 0;
        for(int i=n-2;i>=0;i--){
            if(h[i]>=h[i+1]){
                curr++;
            }
            else{
                curr = 0;
            }
            maxi = max(maxi,curr);
        }
        cout << maxi << endl;
        return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define rep(i, n) for (int i = 0; i < n; i++)
#define rep1(i, n) for (int i = 1; i <= n; i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl;

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<long long, long long> pll;

const int INF = 1 << 30;
const long long INFL = 1LL << 62;
const int MOD = 1000000007;
const int MAX = 100010;
const int N = 100010;

struct mint {
    ll x;
    mint(ll x=0):x((x%MOD+MOD)%MOD){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {if ((x+=a.x)>=MOD) x-=MOD; return *this;}
    mint& operator-=(const mint a) {if ((x+=MOD-a.x)>=MOD) x-=MOD; return *this;}
    mint& operator*=(const mint a) {(x*=a.x)%=MOD; return *this;}
    mint operator+(const mint a) const {mint res(*this); return res+=a;}
    mint operator-(const mint a) const {mint res(*this); return res-=a;}
    mint operator*(const mint a) const {mint res(*this); return res*=a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(MOD-2);}
    mint& operator/=(const mint a) { return (*this) *= a.inv();}
    mint operator/(const mint a) const {mint res(*this); return res/=a;}
};

const int cmax = 100010;
mint fac[cmax],finv[cmax],inv[cmax];

void com_init() {
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for (int i=2; i<cmax; i++) {
        fac[i]=fac[i-1]*i;
        inv[i]=-inv[MOD%i]*(MOD/i);
        finv[i]=finv[i-1]*inv[i];
    }
}

ll com(int n, int k) {
    if (n<k) return 0;
    if (n<0||k<0) return 0;
	mint ret=fac[n]*finv[k]*finv[n-k];
    return ret.x;
}

ll a[N];
mint sa[N+1];

int main() {
	int n,k;cin>>n>>k;
	rep(i,n) cin>>a[i];
	sort(a,a+n);
	if(k==1) {cout<<0<<endl;return 0;}
	sa[0]=0;
	rep(i,n) {sa[i+1]=sa[i]+a[i];}
	com_init();
	mint ans=0;
	for(int i=k;i<=n;i++){
		mint c=com(i-2,k-2);
		ans+=c*(sa[n]-sa[i-1]-sa[n-i+1]);
	}
	cout<<ans.x<<endl;
}


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

const ll MOD = 1000000007;
const ll MAX = 100100;
const double PI = 3.1415926;

#define vll vector<ll>
#define max_heap priority_queue<int>
#define min_heap priority_queue<int , vector<int>, greater<int> >
#define pb push_back
#define all(container) container.begin(), container.end()
// #define traverse( container, it) for( typeof(container.begin()) it = container.begin(); it!=container.end(); it++)
ll n;
double arr[3001];
double dp[3001][3001];

double fill(ll s, ll h)
{
	if (s == 0)
	{
		if (h > n/2)
			return 1;
		return 0;
	}
	if (dp[s][h] != -1.0)
		return dp[s][h];
	else
	{
		dp[s][h] = fill(s - 1, h)*(1 - arr[s]) + fill(s - 1, h + 1)*(arr[s]);
		return dp[s][h];
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cout << setprecision(10) << fixed;
	for(int i = 0; i < 3001; i++)
	{
		for (int j = 0; j < 3001; j++)
			dp[i][j] = -1.0;
	}
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> arr[i];
	cout << fill(n, 0) << endl;
	return 0;
}

Measured memory_bytes: 70912
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll n,k,i,ans=0;
    cin>>n>>k;
    ll arr[n];
    for(i=0;i<n;i++)
        cin>>arr[i];
    sort(arr,arr+n);
    for(i=0;i<k;i++)
        ans+=arr[i];
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3660
def spaceinput():
    return list(map(int,input().split(" ")))


def merge(a,b):
    l=sorted([a[0],b[0]])
    r=sorted([a[1],b[1]])
    return l[1],r[0]


N,M=spaceinput()
gates=[]
for i in range(M):
    gates.append(spaceinput())

d=gates[0]
for i in range(1,M):
    d=merge(d,gates[i])

print(max(0,d[1]-d[0]+1))


Measured memory_bytes: 27332
#include <bits/stdc++.h>
#define repe(i, a, b) for (int i = (a); i <= (b); i++)
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define mst(a, b)   memset((a), (b), sizeof(a))
#define gc() gutchar()
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pr;
typedef long long ll;
const double eps = 1e-5;
const int inf = 0x3f3f3f3f;
const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};
const ll mod = 1e9+7;
const int N = 2e5+5;

int main()
{
	ll h, res, sum;
	res = 1; sum = 1;
	cin >> h;
	while (h != 1)
	{
		h >>= 1;
		res <<= 1;
		sum += res;
	}
	cout << sum;
	return 0;
}

Measured memory_bytes: 256
import java.io.IOException;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	
	public static class Walk implements Comparable<Walk> {
		int x, y, cost;

		public Walk(int x, int y, int cost) {
			this.x = x;
			this.y = y;
			this.cost = cost;
		}

		@Override
		public int compareTo(Walk arg0) {
			return this.cost - arg0.cost;
		}
		
	}

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		final int H = sc.nextInt();
		final int W = sc.nextInt();
		
		int map[][] = new int[H][W];
		
		for(int i = 0; i < H; i++){
			char[] ch = sc.next().toCharArray();
			for(int j = 0; j < W; j++){
				map[i][j] = ch[j] - '0';
			}
		}
		
		PriorityQueue<Walk> queue = new PriorityQueue<Walk>();
		queue.add(new Walk(0,0,map[0][0]));
		
		boolean[][] visited = new boolean[H][W];
		
		while(!queue.isEmpty()){
			Walk w = queue.poll();
			
			if(visited[w.y][w.x]){
				continue;
			}
			
			if(w.x == W - 1 && w.y == H - 1){
				System.out.println(w.cost);
				break;
			}
			
			visited[w.y][w.x] = true;
			
			if(w.x != W - 1 && !visited[w.y][w.x + 1]){
				queue.add(new Walk(w.x + 1, w.y, w.cost + map[w.y][w.x + 1]));
			}
			
			if(w.y != H - 1 && !visited[w.y + 1][w.x]){
				queue.add(new Walk(w.x, w.y + 1, w.cost + map[w.y + 1][w.x]));
			}
		}
		
	}

}

Measured memory_bytes: 12000
h,w = map(int, input().split())
mat = [list(input()) for _ in range(h)]

nrow = len(mat[0])
row_checked_mat = [row for row in mat if not row.count('.') == nrow]

ncol = len(row_checked_mat)
col_checked_mat = [col for col in zip(*row_checked_mat) if not col.count('.') == ncol]

for mat_i in zip(*col_checked_mat):
  print(*mat_i, sep='')

Measured memory_bytes: 4596
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>
#include <random>

//using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; ++i)
#define rep(i,b) Rep(i,0,b)
#define allof(a) (a).begin(), (a).end()

using ll =  long long;

constexpr int inf = 1e9 + 7;
constexpr ll infll = 1ll << 60ll;
constexpr ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

template<typename T> void chmax(T& a, T b) { a = std::max(a, b); }
template<typename T> void chmin(T& a, T b) { a = std::min(a, b); }
template<typename T> void chadd(T& a, T b) { a = a + b; }

namespace {  // 名前なし名前空間
	// gcd, lcm は C++17 でstdに標準入りしたので言語のバージョンに注意
	// 最大公約数
	ll gcd(ll a, ll b) {
		if (b == 0) return a;
		return gcd(b, a % b);
	}

	// 最小公倍数
	ll lcm(ll a, ll b) {
		return a / gcd(a, b) * b;
	}
}

// 素因数分解 pair.firstで素数、pair.secondで対応する指数
std::vector<std::pair<long long, long long> > prime_factorize(long long n) {
	std::vector<std::pair<long long, long long> > res;
	for (long long p = 2; p * p <= n; ++p) {
		if (n % p != 0) continue;
		int num = 0;
		while (n % p == 0) { ++num; n /= p; }
		res.push_back(std::make_pair(p, num));
	}
	if (n != 1) res.push_back(std::make_pair(n, 1));
	return res;
}

const int MAX = 2100000;

//二項係数を求める前処理 テーブルを作る　O(n)
// facは階乗
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		finv[i] = finv[i - 1] * inv[i] % mod;
	}
}

// 二項係数計算
ll COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

int main() {

	int x, y;
	std::cin >> x >> y;
	COMinit();

	// 右2下1の移動を何回するか
	// 右1下2の移動を何回するか
	// まずその回数を求める
	
	int right_num = 0;
	int down_num = 0;

	for (int i = 0; i <= 2 * x; ++i) {
		int dx = i * 2;
		int dy = i;
		int rest_x = x - dx;
		int rest_y = y - dy;
		// 残りの回数下2右1の移動をする
		if (rest_x * 2 == rest_y) {
			right_num = i;
			down_num = rest_x;
		}
	}

	if (down_num == 0 && right_num == 0) {
		std::cout << 0 << std::endl;
		return 0;
	}

	ll ans = 0LL;

	ans = COM(right_num + down_num, right_num);

	std::cout << ans << std::endl;

	return 0;
}

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

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

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

    bool res = false;
    unordered_map<int, bool> mp;
    for (int i = 0; i < N; i++) {
        if (mp[A[i]] == true) {
            res = true;
            break;
        }
        mp[A[i]] = true;
    }

    if (res) {
        cout << "NO";
    } else {
        cout << "YES";
    }
}


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

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

    int total = 0;
    rep(i, n) {
        int tmp;
        cin >> tmp;
        total += tmp;
        a.emplace_back(tmp);
    }

    double border = (double)total / (4 * m);

    int cnt = 0;
    rep(i, n) {
        if (a[i] >= border) cnt++;
    }

    cout << (cnt >= m ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader; 
import java.io.*;
import java.io.InputStreamReader; 
import java.util.Scanner; 
import java.util.StringTokenizer; 
import java.util.*;
import java.math.*;
public class Main 
{ 
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader()
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next()
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine();
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
   public static void main(String args[])
    {
        FastReader sc=new FastReader();
        PrintWriter pw=new PrintWriter(System.out);
        int t=1;//sc.nextInt();
        while(t-->0)
        {
           String s=sc.next(),st=sc.next();int f=0;
           for(int i=s.length();i>=0;i--)
           {
             String str=s.substring(i,s.length())+s.substring(0,i);
             if(str.equals(st)){pw.println("Yes");f=1;break;}
           }
           if(f==0) pw.println("No");
        }
           pw.close();
    }
}
  

Measured memory_bytes: 37320
#include<bits/stdc++.h>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }


using namespace std;

vector<int> par; // 親ノード
vector<int> depth; // ランク


void init(int n = 1) {
    par.resize(n); depth.resize(n);
    for (int i = 0; i < n; ++i) par[i] = i, depth[i] = 0;
}

int root(int x) {
    if (par[x] == x) {
        return x;
    }
    else {
        int r = root(par[x]);
        return par[x] = r;
    }
}

bool issame(int x, int y) {
    return root(x) == root(y);
}

bool merge(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return false;
    if (depth[x] < depth[y]) swap(x, y);
    if (depth[x] == depth[y]) ++depth[x];
    par[y] = x;
    return true;
}

int main(){
    int N, M;
    cin >> N >> M;
    int x[M], y[M], z[M];
    rep(i, M){
        cin >> x[i] >> y[i] >> z[i];
        x[i]--; y[i]--;
    }

    init(N);
    rep(i, M){
        merge(x[i], y[i]);
    }

    int c = 0;
    rep(i, N){
        if (root(i) == i) c++;
    }

    cout << c << endl;
}


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

int main(){
  int a,b,x; cin >>a >>b >>x; double angle=0;
  if(a*a*b>=2*x) angle=atan(a*b*b/2.0/x);
  else angle=atan((2.0*b-2.0*x/a/a)/a);
  cout <<fixed<<setprecision(10)<<angle*180/acos(-1);
return 0;}

Measured memory_bytes: 256
#!/usr/bin/env python
import sys
from collections import Counter
from itertools import permutations, combinations
from math import ceil, floor, gcd
sys.setrecursionlimit(10 ** 6)

def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    S = input()

    c = Counter(S)
    r_c = c['R']
    g_c = c['G']
    b_c = c['B']
    ans = r_c * g_c * b_c

    for i in range(N):
        for j in range(i+1, N):
            k = 2 * j - i
            if k > N-1:
                break
            elif i < j < k and S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                ans -= 1
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 74124
#include<iostream>
#include<string>
using namespace std;
int main()
{
    string s,t;
    cin>>s;
    cin>>t;
    int len1,len2;
    len1=s.size();
    len2=t.size();
    if(len2-len1!=1){
        cout<<"No"<<endl;
        return 0;
    }
    int key=0;
    for(int i=0;i<len1;i++){
        if(s[i]!=t[i]){
        cout<<"No"<<endl;
        return 0;
    }
    }
    cout<<"Yes"<<endl;
    return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <algorithm>
#include <string>
#include <limits.h>
#include <vector>

using namespace std;

int main()
{
    
	string str;

	cin >> str;

	bool n, w, s, e;
	n = false;
	w = false;
	s = false;
	e = false;
	
	for (auto& i : str) {
		if (i == 'N')n = true;
		else if (i == 'W')w = true;
		else if (i == 'S')s = true;
		else e = true;
	}

	if (n == s && w == e) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}




	return 0;

}




Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int n,m,x;
priority_queue <int> pq;
long long ans;
int main()
{
	scanf("%d%d",&n,&m);
	while(n--) scanf("%d",&x),pq.push(x);

	while(m--)
	{
		x=pq.top();
		pq.pop();

		if(x==0) return 0 * printf("0");
		pq.push(x>>1);
	}

	while(not pq.empty())
		ans+=pq.top(),pq.pop();
	printf("%lld",ans);
}

Measured memory_bytes: 892
N = int(input())
a = [int(i) for i in input().split()]
#s = [[int(j) for j in input().split()] for i in range(N)]

ave = sum(a)/N

bestId = 0
bestScore = abs(a[0]-ave)
for i in range(1,N):
    score = abs(a[i]-ave)
    if bestScore>score:
        bestId=i
        bestScore = score
print(bestId)



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

int main() {
  int A, B, C;
  cin >> A >> B >> C;

  cout << max(0,B + C - A) << endl;
  return 0;
}

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

typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, n) for(int (i)=0; (i)<(n); (i)++)
#define FOR1(i, n) for(int (i)=1; (i)<=(n); (i)++)
#define FORI(i, n) for(int (i)=n-1; (i)>=0; (i)--)

int main(int argc, char** argv) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << setprecision(15);
    if (argc == 2 && atoi(argv[1]) == 123456789) freopen("d:\\code\\cpp\\contests\\stdin", "r", stdin);

    int n;
    cin >> n;
    ll p = 1;
    ll x;
    const ll INF = 1e18;
    vector<ll> A(n);
    FOR(i, n) {
        cin >> A[i];
        if (A[i] == 0){
            cout << 0 << endl;
            return 0;
        }
    }
    FOR(i, n){
        x = A[i];
        if (x > INF / p){
            cout << -1 << endl;
            return 0;
        }
        p *= x;
    }
    cout << p << endl;

    if (argc == 2 && atoi(argv[1]) == 123456789) cout << clock()*1.0/CLOCKS_PER_SEC << " sec\n";
    return 0;
}

Measured memory_bytes: 3992
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int h,w;
    int n;
    int a[10010],b[10010];
    int c[110][110];
    while(scanf("%d%d",&h,&w)!=EOF)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        int bb=0,bbb=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<a[bbb];j++)
            {
                b[bb++]=i;
            }
            bbb++;
        }
        int ss=0;
        for(int i=0;i<h;i++)
        {
            if(i%2==0)
            {
                for(int j=0;j<w;j++)
                {
                    c[i][j]=b[ss++];
                }
            }
            else
            {
                for(int j=w-1;j>=0;j--)
                {
                    c[i][j]=b[ss++];
                }
            }
        }
        for(int i=0;i<h;i++)
        {
            printf("%d",c[i][0]);
            for(int j=1;j<w;j++)
            {
                printf(" %d",c[i][j]);
            }
            printf("\n");
        }
    }
}


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

vector<pair<int64_t, int64_t>> prime_factorize(int64_t N)
{
  vector<pair<int64_t, int64_t>> res;
  for (int64_t a = 2; a * a <= N; a++)
  {
    if (N % a != 0)
      continue;
    int64_t ex = 0;
    while (N % a == 0)
    {
      ex++;
      N /= a;
    }
    res.push_back({a, ex});
  }
  if (N != 1)
    res.push_back({N, 1});
  return res;
}

int main()
{
  int64_t N, P, ans = 1;
  cin >> N >> P;
  const auto &res = prime_factorize(P);
  for (auto p : res)
  {
    for (int i = 0; i < p.second / N; i++)
    {
      ans *= p.first;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3612
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		int[] num = new int[3];
		num[0] = sc.nextInt();
		num[1] = sc.nextInt();
		num[2] = sc.nextInt();
		Arrays.sort(num);
		int dis1 = num[2] - num[0];
		int dis2 = num[2] - num[1];
		int ans = 0;
		if( dis1%2==0 && dis2%2==0 ){
			ans = dis1/2 + dis2/2;
		}else if( dis1%2!=0 && dis2%2!=0 ){
			ans = dis1/2 + dis2/2 + 1;
		}else{
			ans = dis1/2 + dis2/2 + 2;
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 21844
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
#include<numeric>
using namespace std;
using ll = long long;
int main(){
  int n;
  cin >> n;
  string s, ans;
  cin >> s;
  vector<int> d(n + 1, 0);
  int x = 0;
  for(int i = 0; i < n; i++) {
    if(s[i] == '('){
      d[i + 1] = d[i] + 1;
    }else{
      d[i + 1] = d[i] - 1;
    }
    x = min(d[i + 1], x);
  }
  for(int i = 0; i < -x; i++){
    cout << '(';
  }
  cout << s;
  for(int i = 0; i < d[n] - x; i++){
    cout << ')';
  }
  cout << '\n';

  return 0;
}

Measured memory_bytes: 256
n = gets.to_i
ary = []
n.times{
  ary << 0
}

(1..100).each do |i|
  (1..100).each do |j|
    (1..100).each do |k|
      check = i*i + j*j + k*k + i*j + j*k + i*k
      next if check > n
      ary[check-1] += 1
    end
  end
end
puts ary

Measured memory_bytes: 14296
c[];main(n,m,i){for(;scanf("%d%d",&m,&n)*m;puts("")){int q[1001]={i=0},t=1,p=m;for(;n--;)for(*c=!scanf("%s",c+3),++i%3||strcat(c,"Fizz"),i%5||strcat(c,"Buzz"),*c||sprintf(c,"%d",i),strcmp(c+3,c)&&p>1&&(q[t]=p--);q[t=t%m+1];);for(t=i=0;m--;q[++i]||printf(" %d"+!t++,i));}}

Measured memory_bytes: 636
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define PI 3.14159265359
#define INF 1000100100
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define P pair<int, int>
#define PP pair<P,P>
#define pr(x) cout << x << endl;
using namespace std;

const int mod = 998244353;
//const int mod=1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

// 出力は.xで！！！！

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

ll mpow(ll a, ll b){
  ll ans=1;
  rep(i,b){
    ans*=a;
    ans%=mod;
  }
  return ans;
}

mint dp[201010];
mint rui[201010];

int main(){
  int n,k; cin >> n >> k;
  //rep(i,201010) rui[i]=0;
  vector<P> p(k);
  rep(i,k) cin >> p[i].first >> p[i].second;
  dp[0]=1;
  rui[1]=1;
  for(int i=1; i<=n-1; i++){
    rep(j,k){
      if(i-p[j].first>=0){
        dp[i]+=rui[i-p[j].first+1]-rui[max(0,i-p[j].second)];
      }
    }
    //cout << dp[i].x << endl;
    rui[i+1]=rui[i]+dp[i];
  }
  cout << dp[n-1].x << endl;
return 0;
}




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

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const ll Mod = 1e9 + 7;
const int Maxn = 3e2 + 10;
const ll Inf = 1e16;

ll dp[2][Maxn][Maxn];
vector<pll> Con[Maxn];

bool valid(int i, int j, int k){
	ll cnt = 0;
	for(auto x : Con[i]){
		cnt = 0;
		cnt += (x.F <= i);
		cnt += (x.F <= j);
		cnt += (x.F <= k);
		if(cnt != x.S) return false;
	}
	return true;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n, m;
	cin >> n >> m;
	ll l, r ,x;
	for(int i = 1; i <= m; i++){
		cin >> l >> r >> x;
		Con[r].pb({l, x});
	}
	dp[1][0][0] = 3;
	for(int i = 1; i < n; i++){
		int ii = i & 1;
		memset(dp[ii ^ 1], 0, sizeof dp[ii ^ 1]);
		for(int j = 0; j < i; j++){
			for(int k = j; k < i; k++){	
				if(!valid(i, j, k)) dp[ii][j][k] = 0;
				(dp[ii ^ 1][j][k] += dp[ii][j][k]) %= Mod;
				(dp[ii ^ 1][j][i] += dp[ii][j][k]) %= Mod;
				(dp[ii ^ 1][k][i] += dp[ii][j][k]) %= Mod;
			}
		}
	}
	ll ans = 0;
	for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) if(valid(n, i, j)) ans += dp[n & 1][i][j];
	cout << ans % Mod;
	return 0;
}



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

constexpr int MOD = 1e9 + 7;
using fint64 = int_fast64_t;
template<fint64 MOD>
struct ModInt {
	fint64 x;
	ModInt():x(0){}
	ModInt(fint64 x):
		x(x>=0?x%MOD:(MOD-(-x)%MOD)%MOD)
		{}
	// 負号
	ModInt operator -() const{
		return ModInt(-x);
	}
	// 加算
	ModInt &operator +=(const ModInt &rhs){
		x+=rhs.x;
		if(x>=MOD) x-=MOD;
		return (*this);
	}
	ModInt operator +(const ModInt &rhs) const{
		return ModInt(*this)+=rhs;
	}
	// 減算
	ModInt &operator -=(const ModInt &rhs){
		x+=MOD-rhs.x;
		if(x>=MOD) x-=MOD;
		return (*this);
	}
	ModInt operator -(const ModInt &rhs) const{
		return ModInt(*this)-=rhs;
	}
	// 乗算
	ModInt &operator *=(const ModInt &rhs){
		x*=rhs.x;
		if(x>=MOD) x%=MOD;
		return (*this);
	}
	ModInt operator *(const ModInt &rhs) const{
		return ModInt(*this)*=rhs;
	}
	// 除算
	ModInt &operator /=(const ModInt &rhs){
		(*this)*=rhs.inverse();
		return (*this);
	}
	ModInt operator /(const ModInt &rhs) const{
		return ModInt(*this)/=rhs;
	}
	// 等号
	bool operator ==(const ModInt &rhs){
		return x==rhs.x;
	}
	bool operator !=(const ModInt &rhs){
		return x!=rhs.x;
	}
	// 累乗
	ModInt pow(fint64 n) const{
		fint64 tmp=x;
		fint64 ret=1;
		while(n>0){
			if(n&1) ret=ret*tmp%MOD;
			tmp=tmp*tmp%MOD;
			n>>=1ll;
		}
		return ModInt(ret);
	}
	// 逆元
	ModInt inverse() const{
		fint64 a=x,b=MOD,s=1,t=0;
		while(b>0){
			fint64 u=a/b;
			a-=u*b;
			s-=u*t;
			swap(a,b);
			swap(s,t);
		}
		return ModInt(s);
	}
	// 入出力
	friend istream &operator >>(istream &lhs,ModInt<MOD> &rhs){
		fint64 x; lhs>>x;
		rhs=ModInt<MOD>(x);
		return lhs;
	}
	friend ostream &operator <<(ostream &lhs,const ModInt<MOD> &rhs){
		return lhs<<rhs.x;
	}
};
using mint = ModInt<MOD>;

mint dp[210][10010];
int main() {
	int n, W; cin >> n >> W;
	int w[n]; for(int i = 0; i < n; ++i) cin >> w[i];
	sort(w, w + n);
	reverse(w, w + n);
	dp[0][0] = 1;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j <= W; ++j) {
			dp[i + 1][j] += dp[i][j];
			if(j + w[i] <= W) dp[i + 1][j + w[i]] += dp[i][j];
		}
	}
	mint ans = 0;
	int sum = 0;
	for(int i = n - 1; i >= 0; --i) {
		for(int j = max(0, W - w[i] - sum + 1); j <= W - sum; ++j) {
			ans += dp[i][j];
		}
		sum += w[i];
	}
	if(sum <= W) ans += 1;
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 19592
S=list(input())
Q=int(input())
Rev=True
front=[]
back=[]
for i in range(Q):
    a=input()
    if a=='1':
        Rev=not(Rev)
    else:
        b,c,x=a.split()
        if c == '1':
            if Rev:
                front.append(x)
            else:
                back.append(x)
        else:
            if Rev:
                back.append(x)
            else:
                front.append(x)
if Rev:
    front.reverse()
    front.extend(S)
    front.extend(back)
    print("".join(front))
else:
    back.reverse()
    S.reverse()
    back.extend(S)
    back.extend(front)
    print("".join(back))


Measured memory_bytes: 75640
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    c = sorted(collections.Counter(LI()).values(), reverse=True) + [0]
    ci = 0
    t = n
    r = [0]
    for i in range(n,0,-1):
        while c[ci] > i:
            ci += 1
        t -= ci
        r.append(t // i)

    rr = []
    r.reverse()
    ri = 0
    for i in range(n,0,-1):
        while r[ri] >= i:
            ri += 1
        rr.append(ri)

    rr.reverse()

    return JA(rr,"\n")


print(main())




Measured memory_bytes: 39544
#include <utility>
#include <iostream>
#include <unordered_map>



int main()
{
    // using map_type = std::unordered_map< std::string, int > ;
    typedef std::unordered_map< std::string, int > map_type ; 
    map_type map ;

    std::string longest_word ;

    std::string word ;
    while ( std::cin >> word )
    {
        ++map[word] ;
        if ( longest_word.size() < word.size() )
        {
            longest_word = word ;
        }
    }

    std::pair< map_type::key_type, map_type::mapped_type> most_frequent_word ;
    for ( auto && elem : map )
    {
        if ( most_frequent_word.second < elem.second )
        {
            most_frequent_word = elem ;
            
        }
    }

    std::cout << most_frequent_word.first << ' ' << longest_word << '\n' ;
    
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
#define lol long long
#define SUM(n) ((n)+1)*(n)/2 //1〜nまでの総和を求める式
#define mp make_pair
#define fi first
#define se second
#define pu push_back
#define SYOU(x) fixed<<setprecision(x+1) //小数点桁数を指定する
#define abs(x,y) max(x,y)-min(x,y)
#define all(v) v.begin(),v.end()
#define UPDigit(a,b) (a+b-1)/b //小数点切り上げ
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD=int(1e9)+7; 
using namespace std;
using pii = pair<lol, lol>;
typedef vector<int> vit;

/*
struct SegmentTree{
  
  vector<lol> SumV(1000005,0);
  vector<lol> MaxV(1000005,0);
  vector<lol> MinV(1000005,0);
  int N;
  
  void update(int i,int x){
    i += N - 1;
    minv[i] = x;
    maxv[i] = x;
    sumv[i] = x;
    while(i > 0){
      i = (i - 1)/2;
      maxv[i] = max(maxv[i*2+1],maxv[i*2+2]);
      minv[i] = min(minv[i*2+1],minv[i*2+2]);
      sumv[i] = sumv[i*2+1]+sumv[i*2+2];
    }
  }
  
  void add(int i,int x){
    i += N - 1;
    sumv[i] += x;
    maxv[i] += x;
    minv[i] += x;
    while(i > 0){
      i = (i - 1)/2;
      sumv[i] = sumv[i*2+1]+sumv[i*2+2];
      minv[i] = min(minv[i*2+1],minv[i*2+2]);
      maxv[i] = max(maxv[i*2+1],maxv[i*2+2]);
    }
  }
  
  int getmax(int a,int b,int k,int l,int r){
    if(r <= a || b <= l) return -INF;
    if(a <= l && r <= b) return maxv[k];
    else{
      int c1 = getmax(a,b,2*k+1,l,(l+r)/2);
      int c2 = getmax(a,b,2*k+2,(l+r)/2,r);
      return max(c1,c2);
    }
  }
  
  int getmin(int a,int b,int k,int l,int r){
    if(r <= a || b <= l) return INF;
    if(a <= l && r <= b) return minv[k];
    else{
      int c1 = getmin(a,b,2*k+1,l,(l+r)/2);
      int c2 = getmin(a,b,2*k+2,(l+r)/2,r);
      return min(c1,c2);
    }
  }
  
  int getsum(int a,int b,int k,int l,int r){
    if(r <= a || b <= l) return 0;
    if(a <= l && r <= b) return sumv[k];
    else{
      int c1 = getsum(a,b,2*k+1,l,(l+r)/2);
      int c2 = getsum(a,b,2*k+2,(l+r)/2,r);
      return c1+c2;
    }
  }
}
*/

//最大公約数
lol gcd(lol x, lol y){
  if(x < y) swap(x, y);
  lol r = x % y;
  while(r != 0){
    x = y;
    y = r;
    r = x % y;
  }
  return y;
}
//最小公倍数
lol lcm(lol x, lol y){
  lol a = x * y;
  return (a / gcd(x, y));
}

signed main(void){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  int a, b;
  cin >> a >> b;
  if(b % a == 0){
    cout << a + b << '\n';
  } else {
    cout << b - a << '\n';
  }
  return 0;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
	char c=getchar();bool f=0;x=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;return x;
}
template<class t> inline void write(t x){
	if(x<0) putchar('-'),write(-x);
	else{if(x>9) write(x/10);putchar('0'+x%10);}
}


#define int long long

const int N=2e5+5;
int n,a[N],cnt[N],ans;




signed main(){
	read(n);
	for(int i=1;i<=n;i++){
		read(a[i]);
		ans+=cnt[a[i]];
		cnt[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		write(ans-cnt[a[i]]+1);
		puts("");
	}
}

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

int main() {
    int N;
    int a[110];  // 最大 100 個ですが余裕をもたせます
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> a[i];

    sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート
    int Alice = 0;
    int Bob = 0;
    for (int i = 0; i < N; ++i) {
        if (i % 2 == 0) { // Alice のターン
            Alice += a[i];
        }
        else { // Bob のターン
            Bob += a[i];
        }
    }
    cout << Alice - Bob << endl;
}

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

int main()
{
    long long X, K, D;
    int Y = 0;
    cin >> X >> K >> D;
    if (X == 0)
    {
        if (K % 2 == 0)
        {
            cout << '0' << endl;
        }
        else
        {
            cout << D << endl;
        }
    }
    else if (X < 0)
    {
        rep(i, K)
        {
            X += D;
            if (X >= 0)
            {
                Y = K - i;
                break;
            }
        }
        if (Y % 2 == 0)
        {
            if (X >= 0)
            {
                cout << X << endl;
            }
            else
            {
                cout << -X << endl;
            }
        }
        else
        {
            cout << X - D << endl;
        }
    }
    else if (X > 0)
    {
        rep(i, K)
        {
            X -= D;
            if (X <= 0)
            {
                Y = K - i;
                break;
            }
        }
        if (Y % 2 == 0)
        {
            if (X < 0)
            {
                cout << -X << endl;
            }
            else
            {
                cout << X << endl;
            }
        }
        else
        {
            cout << X + D << endl;
        }
    }
}*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep2(i, x, n) for(int i = x; i < (n); ++i)
 
int main()
{
    ll x, k, d;
    cin >> x >> k >> d;
    x = abs(x);
    if (x/d >= k) {
        x -= k*d;
    } else {
        k -= x/d;
        x -= (x/d)*d;
        if (k%2==1) x = abs(x-d);
    }
    cout << x << endl;
    return 0;
}

Measured memory_bytes: 3624