akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

inline bool diff(char &a,char &b){
    return a!='?'&&b!='?'&&a!=b;
}

int la,lb,lc,ans=0x3f3f3f3f;
char a[2000],b[2000],c[2000];
bool ab[20000],ac[20000],bc[20000];

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>a;la=strlen(a);
    cin>>b;lb=strlen(b);
    cin>>c;lc=strlen(c);
    memset(ab,1,sizeof(ab));
    memset(ac,1,sizeof(ac));
    memset(bc,1,sizeof(bc));
    for(int i=0;i<la;i++)for(int j=0;j<lb;j++)if(diff(a[i],b[j]))ab[i-j+10000]=0;
    for(int i=0;i<la;i++)for(int j=0;j<lc;j++)if(diff(a[i],c[j]))ac[i-j+10000]=0;
    for(int i=0;i<lb;i++)for(int j=0;j<lc;j++)if(diff(b[i],c[j]))bc[i-j+10000]=0;
    for(int pa=-4000;pa<=4000;pa++){
        for(int pb=-4000;pb<=4000;pb++){
            if(ab[pb-pa+10000]&&ac[-pa+10000]&&bc[-pb+10000]){
                ans=min(ans,max(la+pa,max(lb+pb,lc))-min(0,min(pa,pb)));
            }
        }
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 384
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] A = new int[N];
    for (int i = 0; i < N; i++) {
      A[i] = sc.nextInt();
    }
    int[] line = new int[N];
    for (int i = N - 1; i > 0; i -= 2) {
      line[i]++;
      line[i]++;
    }
    if (N % 2 == 1) {
      line[0]++;
    }
    int[] line2 = new int[N];
    for (int i = 0; i < N; i++) {
      line2[A[i]]++;
    }
    for (int i = 0; i < N; i++) {
      if (line[i] != line2[i]) {
        System.out.println(0);
        return;
      }
    }
    long ans = 1;
    for (int i = 0; i < N / 2; i++) {
      ans *= 2;
      ans %= 1000000007;
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 50864
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <map>
#include <time.h>

using namespace std;

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

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

string g[1001];

signed main() {
  int h, w;
  cin >> h >> w;

  queue<P> q;

  rep(i, 0, h) {
    cin >> g[i];
    rep(j, 0, w) {
      if(g[i][j] == '#') q.push(P(i, j));
    }
  }
  if(q.size() == h * w) {
    cout << 0 << endl;
    return 0;
  }
  int ans = 0;
  while(!q.empty()) {
    queue<P> kq;
    while(!q.empty()) {
      P p = q.front();q.pop();
      int i = p.first, j = p.second;
      if(i > 0 && g[i - 1][j] == '.') g[i - 1][j] = '#', kq.push(P(i - 1, j));
      if(i < h - 1 && g[i + 1][j] == '.') g[i + 1][j] = '#', kq.push(P(i + 1, j));
      if(j > 0 && g[i][j - 1] == '.') g[i][j - 1] = '#', kq.push(P(i, j - 1));
      if(j < w - 1 && g[i][j + 1] == '.') g[i][j + 1] = '#', kq.push(P(i, j + 1));
    }
    q = kq;
    if(kq.size()) ans++;
  }

  cout << ans << endl;
}


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

const int INF = 1000000000;

int main() {
  int n,k;
  cin >> n >> k;
  vector<int> h(n+k+1,0);
  rep(i,0,n) cin >> h[i];
  vector<int> dp(n + k + 10,INF);
  dp[0] = 0;
  rep(i,0,n) rep(j,1,k+1) {
    dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]));
  }
  cout << dp[n-1] << endl;
  return 0;
}


Measured memory_bytes: 3988
import static java.lang.Math.abs;
import static java.lang.Math.min;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Locale;
import java.util.Scanner;

public class Main {

	final static int INF = Integer.MAX_VALUE;

	public static void main(String[] args) {
		Locale.setDefault(Locale.ENGLISH);
		Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		solve(in, System.out);
		in.close();
	}

	protected static void solve(Scanner in, PrintStream out) {
		int n = in.nextInt();
		int k = in.nextInt();
		int[] a = new int[n];
		for (int j = 0; j < n; j++) {
			a[j] = in.nextInt();
		}
		int ret = solveLine(n, k, a);
		out.printf(Locale.ENGLISH, "%s%n", ret);
	}

	private static int solveLine(int n, int k, int[] ar) {
		int[] dp = new int[n + 2];
		Arrays.fill(dp, INF);
		dp[0] = 0;
		for (int i = 0; i < n - 1; i++) {
			for (int j = 1; j <= k && i + j < n; j++) {
				dp[i + j] = min(dp[i + j], dp[i] + abs(ar[i] - ar[i + j]));
			}
		}
		return dp[n - 1];
	}

}

Measured memory_bytes: 50784
from random import randint
import sys
input = sys.stdin.readline
INF = 9223372036854775808


def calc_score(D, C, S, T):
    """
    開催日程Tを受け取ってそこまでのスコアを返す
    コンテストi 0-indexed
    d 0-indexed
    """
    score = 0
    last = [0]*26  # コンテストiを前回開催した日
    for d, t in enumerate(T):
        last[t] = d + 1
        for i in range(26):
            score -= (d + 1 - last[i]) * C[i]
        score += S[d][t]
    return score


def update_score(D, C, S, T, score, ct, ci):
    """
    ct日目のコンテストをコンテストciに変更する
    スコアを差分更新する

    ct: change t 変更日 0-indexed
    ci: change i 変更コンテスト 0-indexed
    """
    last = [0]*26  # コンテストiを前回開催した日
    for d in range(ct):
        last[T[d]] = d + 1
    prei = T[ct]  # 変更前に開催する予定だったコンテストi
    score -= S[ct][prei]
    score += S[ct][ci]
    for d in range(ct, D):
        if d != ct and T[d] == prei:
            break
        score += C[prei]*(d + 1 - ct - 1)
        score -= C[prei]*(d + 1 - last[prei])
    for d in range(ct, D):
        if d != ct and T[d] == ci:
            break
        score += C[ci]*(d + 1 - last[ci])
        score -= C[ci]*(d + 1 - ct - 1)
    T[ct] = ci
    return score, T


def local_search(D, C, S, T, today_score, d):
    pass


def evaluate(D, C, S, T, k):
    """
    d日目終了時点での満足度を計算し，
    d + k日目終了時点での満足度の減少も考慮する
    """
    score = 0
    last = [0]*26
    for d, t in enumerate(T):
        last[t] = d + 1
        for i in range(26):
            score -= (d + 1 - last[i]) * C[i]
        score += S[d][t]

    for d in range(len(T), min(len(T) + k, D)):
        for i in range(26):
            score -= (d + 1 - last[i]) * C[i]
    return score


def greedy(D, C, S):
    Ts = []
    for k in range(5, 15):
        T = []  # 0-indexed
        for d in range(D):
            # d+k日目終了時点で満足度が一番高くなるようなコンテストiを開催する
            max_score = -INF
            best_i = 0
            for i in range(26):
                T.append(i)
                score = evaluate(D, C, S, T, k)
                if max_score < score:
                    max_score = score
                    best_i = i
                T.pop()
            T.append(best_i)
        Ts.append((max_score, T))
    return max(Ts, key=lambda pair: pair[0])[1]


if __name__ == '__main__':
    D = int(input())
    C = [int(i) for i in input().split()]
    S = [[int(i) for i in input().split()] for j in range(D)]
    T = greedy(D, C, S)
    for t in T:
        print(t+1)


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

#define rep(i,j,n) for(i=j;i<n;i++)
#define repi(i,j,n) for(i=j;i>n;i--)
#define inf 100001
#define M 1000000007
#define ll long long
#define vll vector<long long>
#define vi vector<int>
#define pll pair<long long,long long>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define vpll vector<pair<long long,long long> >
#define pb push_back
#define pf pop_front
#define mp make_pair
#define F first
#define S second


ll power(ll a,ll m,ll mod){
	ll ans=1;
	while(m){
		if(m%2){
			ans*=a;
			ans%=(mod);
		}
		a=(a*a)%(mod);
		m>>=1;
	}
	return ans;
}


void init(long long* a,long long n,long long val){
	for(long long i=0;i<n;i++)
		a[i]=val;
}



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);	
	ll t=1,i,j;
	ll n;
	ll a,b;
	cin>>a>>b;
	n=__gcd(a,b);
	cout<<a*b/n;
	return 0;
}

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

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
//typedef long long ll;
typedef long long ll;
//typedef pair<int, int> P;
//typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = 10e15;
const ll MINF = -10e10;
//const int INF = INT_MAX / 100;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)


//ifstream myfile("~/Downloads/02.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

//typedef priority_queue<P, vector<P>, greater<P> > PQ_ASK;
const int mod = 1000000007;
const double PI = 3.14159265358979323846;

typedef pair<string, int> P;


string to_upper(string str) {
    int diff = 'a' - 'A';
    for (int i = 0; i < str.size(); i++) {
        char c = str[i];
        if ('A' <= c && c <= 'Z') {
            c += diff;
            str[i] = c;
        }
    }
    return str;
}


int main() {
    vector<ll> fibonacci(50, 0);
    fibonacci[0] = 1;
    fibonacci[1] = 1;
    for (int i = 2; i < 50; i++) {
        fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
    }

    int n;
    cin >> n;
    cout << fibonacci[n] << endl;

}



Measured memory_bytes: 3120
import sys
sys.setrecursionlimit(2*10**5)

N, M = map(int, input().split())
p = [0] + list(map(int, input().split()))
x, y = zip(*(map(int, input().split()) for _ in range(M)))
E = [[] for _ in range(N + 1)]
for a, b in zip(x, y):
    E[a].append(b)
    E[b].append(a)
v = [True for _ in range(N + 1)]


def f(i, P, Q):
    v[i] = False
    P.add(i)
    Q.add(p[i])
    for a in E[i]:
        if v[a]:
            f(a, P, Q)


ans = 0
for i in range(1, N + 1):
    if v[i]:
        P = set()
        Q = set()
        f(i, P, Q)
        ans += len(P & Q)
print(ans)


Measured memory_bytes: 92908
#pragma GCC optimize("Ofast")
#include<stdio.h>
#include<vector>
#include<utility> 
#include<queue> 
#include<algorithm>
using namespace std;
long long a[1005],b[1005],c[1005],d[1005],e[1005],f[1005];
bool used[3005][3005]={0},up[3005][3005]={0},down[3005][3005]={0},left[3005][3005]={0},right[3005][3005]={0}; 
vector<long long> x,y;
queue<pair<long long,long long>> que;
long long id_x(long long v){
	return lower_bound(x.begin(),x.end(),v)-x.begin();
}
long long id_y(long long v){
	return lower_bound(y.begin(),y.end(),v)-y.begin();
}
int dir[][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int main(){
	x.emplace_back(100000000000000000);
	x.emplace_back(-100000000000000000);
	y.emplace_back(100000000000000000);
	y.emplace_back(-100000000000000000);
	long long i,j,n,m;
	scanf("%lld%lld",&n,&m);
	for(i=0;i<n;i++){
		scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
		x.emplace_back(a[i]);
		x.emplace_back(b[i]);
		y.emplace_back(c[i]);
	}
	for(i=0;i<m;i++){
		scanf("%lld%lld%lld",&d[i],&e[i],&f[i]);	
		x.emplace_back(d[i]);
		y.emplace_back(e[i]);
		y.emplace_back(f[i]);
	}
	sort(x.begin(),x.end());
	sort(y.begin(),y.end());
	x.erase(unique(x.begin(),x.end()),x.end());
	y.erase(unique(y.begin(),y.end()),y.end());
	//printf("%d %d\n",id_x(0),id_y(0));
//	printf("%d %d\n",x.size(),y.size());
	for(i=0;i<n;i++){
		a[i]=id_x(a[i]);
		b[i]=id_x(b[i]);
		c[i]=id_y(c[i]);
		for(j=a[i];j<b[i];j++){
			up[j][c[i]-1]=1;
			down[j][c[i]]=1;
		}
	}
	for(i=0;i<m;i++){
		d[i]=id_x(d[i]);
		e[i]=id_y(e[i]);
		f[i]=id_y(f[i]);
		for(j=e[i];j<f[i];j++){
			right[d[i]-1][j]=1;
			left[d[i]][j]=1;
		}
	}
	que.push({id_x(0)-1,id_y(0)-1});
	used[id_x(0)-1][id_y(0)-1]=1;
	while(que.size()){
		auto z=que.front();
		que.pop();
	//	printf("**%lld %lld\n",z.first,z.second);
		for(i=0;i<4;i++){
			if(i == 0 && up[z.first][z.second]) continue;
			if(i == 1 && down[z.first][z.second]) continue;
			if(i == 2 && right[z.first][z.second]) continue;
			if(i == 3 && left[z.first][z.second]) continue;
			long long r=z.first+dir[i][0],c=z.second+dir[i][1];
		//	printf("%lld %lld %lld %lld %lld\n",r,c,x.size(),y.size(),used[r][c]);
			if(r<0||c<0||r>=(int)x.size()-1||c>=(int)y.size()-1||used[r][c])
				continue;
		//	printf("%d %d\n",r,c);
			used[r][c]=1;
			que.push({r,c});
		} 
	}
	for(i=0;i<(int)x.size();i++){
		if(used[i][0]||used[i][y.size()-1]){
			puts("INF");
			return 0;
		}
	}
	for(i=0;i<(int)y.size();i++){
		if(used[0][i]||used[x.size()-1][i]){
			puts("INF");
		}
	}
	long long ans=0;
	for(i=0;i<(int)x.size()-1;i++){
		for(j=0;j<(int)y.size()-1;j++){
		//	printf("%d %d %d\n",i,j,used[i][j]);
			//	printf("%lld %lld %lld %lld\n",x[i],x[i+1],y[j],y[j+1]);
		//	printf("%d")
			if(used[i][j]){
				ans+=(x[i+1]-x[i])*(y[j+1]-y[j]);
		//		printf("%lld\n",(x[i+1]-x[i])*(y[j+1]-y[j]));
				//printf("%lld %lld\n",i,j);
			}			
		}
	}
	printf("%lld\n",ans);
}


Measured memory_bytes: 40644
#include <bits/stdc++.h>
//#pragma GCC optimize "-O3"
typedef unsigned long long ull;
typedef unsigned int ui;
typedef unsigned short us;
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll infll=(1ull<<63)-1;
const int inf=(1ull<<31)-1;
int n,a[100000];

int main()
{
	//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false); cin.tie(0);cout.precision(18);
	cin>>n;
	for (int i=0;i<n;i++)
		cin>>a[i];
	int b=0;
	for (int i=0;i<n;i++)
		b+=(i&1)?-a[i]:a[i];
	for (int i=0;i<n;i++){
		cout<<b<<" ";
		b=(a[i]<<1)-b;
	}
	return 0;
}

Measured memory_bytes: 1792
x,y=map(int,input().split())
a=[1,3,5,7,8,10,12]
b=[4,6,9,11]
c=[2]
if (x in a) and (y in a):
    print('Yes')
    exit()
if (x in b) and (y in b):
    print('Yes')
    exit()
if (x in c) and (y in c):
    print('Yes')
    exit()
else:
    print('No')
    exit()

Measured memory_bytes: 3064
s = input()


ans = "Yes"
for i in range(len(s)):
  if i % 2 != 0:
    if s[i] == "L" or s[i] == "U" or s[i] == "D":
      n = 1
    else:
      ans = "No"
  if i % 2 == 0:
    if s[i] == "R" or s[i] == "U" or s[i] == "D":
      n = 1
    else:
      ans ="No"
      
print(ans)

Measured memory_bytes: 3188
#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--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i,m,n) for(int i = m - 1; i >= n; i--)
#define ALL(v) v.begin(), v.end()
#define CMAX(m, x)  m = max(m,x)
#define CMIN(m, x)  m = min(m,x)
#define itn int
#define Yes() cout << "Yes" << endl
#define No() cout << "No" << endl
#define YES() cout << "YES" << endl
#define NO() cout << "NO" << endl
typedef long long lint;
typedef long double ldouble;
const int INF = 1e9;
const lint LINF = 1e18;
int main(){
    string s,t;
    cin >> s >> t;
    bool flag = true;
    REP(i,s.size()){
        if(s[i] != t[i])
            flag = false;
    }
    if(s.size() + 1 != t.size())
        flag = false;
    if(flag)
        Yes();
    else
    {
        No();
    }
    
    return 0;
}

Measured memory_bytes: 3548
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>

using namespace std;

map<string,int>mp;

int main(){

	string S,T;

	cin>>S;
	cin>>T;

	string cmp=S;

	int ans=0;

	while(1){
	
		if(cmp==T){
			ans=1;
			break;
		}
		if(mp[cmp]==1){break;}

		mp[cmp]=1;

		char last=cmp[cmp.size()-1];
		cmp.pop_back();
		cmp=last+cmp;
	}

	if(ans==1){
	printf("Yes\n");
	}
	else{
	printf("No\n");
	}

	return 0;
}

Measured memory_bytes: 256
use proconio::input;

// use std::cmp::*;
// use std::collections::*;
// use proconio::marker::Chars;

fn main() {
    input! {
        a:i32,
        b:i32,
        // n: isize
    }
    let ans = (a+b)%24;
    println!("{}", ans)

}


Measured memory_bytes: 2096
#include <stdio.h>
#define N 100000
int A[N];
int partition(int,int);

int main(){
  int i,n,ans;
  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  ans = partition(0,n - 1);

    for(i=0;i<n;i++){
      if(i!=0) printf(" ");
      if(i == ans) printf("[");
      printf("%d",A[i]);
      if(i == ans) printf("]");
    }
  printf("\n");
    
  return 0;
}

int partition(int p,int r){
  int i,j,x,temp;
  x = A[r];
  i = p-1;
  for(j=p;j<r;j++){
    if(A[j] <= x){
      i++;
      temp = A[i];
      A[i] = A[j];
      A[j] = temp;
    }
  }
  temp = A[i+1];
  A[i+1] = A[r];
  A[r] = temp;
  return i+1;
}



Measured memory_bytes: 2116
#!/usr/bin/env python3
import sys, math, fractions, itertools


def solve(N: int, Y: int):
    a, b, c = -1, -1, -1
    for i in range(N+1):
        for j in range(N-i+1):
            k = N - i - j
            if 10000 * i + 5000 * j + 1000 * k == Y:
                a, b, c = i, j, k
                break
    print(a, b, c)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(N, Y)

if __name__ == '__main__':
    main()


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

int main() {
    int64_t n,sum=0; cin >> n;
    vector<int> a(3*n);
    rep(i,3*n) cin >> a[i];
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    rep(i,n) sum+=a[2*i+1];
    cout << sum << endl;
}

Measured memory_bytes: 1408
/*  بسم الله الرحمن الرحیم  */

/*  شهید حاج قاسم سلیمانی
    انتقام سخت نزدیک است
*/

#include <bits/stdc++.h>
using namespace std ;

//#define int ll

#define all(x) x.begin() , x.end()

#define PB push_back
#define F first
#define S second
#define _sz(x) (int)x.size()

#define debug(x) cerr << #x << " = " << x << endl

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

const int MAX_N = 2010 , MAX_X = 2010 * 2 , MAX_Y = 2010 * 4 , MAX_M = 200 * 1000 + 19 ;
const int inf = 2e9 + 19 ;
const int MOD = 1e9 + 7 ;

int a[MAX_M] , b[MAX_M] , n ;
int dp[MAX_X][MAX_X] , C[MAX_Y][MAX_X] ;
ll ans = 0 ;

ll mul(ll x , ll y) {
        return 1LL * x * y % MOD ;
}

ll sum(ll x , ll y) {
        x += y;
        if (x < 0)
                x += MOD;
        else if (x >= MOD)
                x -= MOD;
        return x;
}

int main() {
        ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) ;
        cin >> n ;
        for (int i = 1 ; i <= n ; i ++) {
                cin >> a[i] >> b[i] ;
                dp[MAX_N - a[i]][MAX_N - b[i]] ++ ;
        }
        for (int i = 1 ; i < MAX_X ; i ++)
                for (int j = 1 ; j < MAX_X ; j ++)
                        dp[i][j] = sum(sum(dp[i][j] , dp[i - 1][j]) , dp[i][j - 1]) ;
        for (int i = 0 ; i < MAX_Y ; i ++) {
		C[i][0] = C[i][i] = 1 ;
		for (int j = 1 ; j < min(i , MAX_X) ; j ++) {
                        C[i][j] = sum(C[i - 1][j] , C[i - 1][j - 1]) ;
                        //if (i == 8038)
                        //        debug(j) ;
                }
	}
        for (int i = 1 ; i <= n ; i ++)
                ans = sum(ans , dp[MAX_N + a[i]][MAX_N + b[i]]) ,  ans = sum(ans, -C[a[i] * 2 + b[i] * 2][a[i] * 2]);
        ans = mul(ans , (MOD + 1) / 2) ;
        if (ans < 0)
                ans += MOD ;
        cout << ans ;
        return (0) ;
}



Measured memory_bytes: 189696
#include<stdio.h>
#define AMOUNT 100000
#define NUM 1000000000
#define SENTINEL 2000000000

struct Card{
    char suit;
    int value;
};

struct Card L[AMOUNT / 2 + 2], R[AMOUNT / 2 + 2];

void merge(struct Card B[],int n,int left,int mid,int right){
    int i,j,k;
    int n1 = mid - left;
    int n2 = right - mid;
    for(i=0;i<n1;i++){
        L[i] = B[left + i];
    }
    for(i=0;i<n2;i++){
        R[i] = B[mid + i];
    }
    L[n1].value = R[n2].value = SENTINEL;
    i = j = 0;
    for(k = left;k<right;k++){
        if(L[i].value<=R[j].value){
            B[k] = L[i++];
        }else{
            B[k] = R[j++];
        }
    }
}

void mergeSort(struct Card B[],int n,int left,int right){
    int mid;
    if(left + 1<right){
        mid=(left+right)/2;
        mergeSort(B,n,left,mid);
        mergeSort(B,n,mid,right);
        merge(B,n,left,mid,right);
    }
}

int partition(struct Card A[],int first,int last){//pivotを条件として大小に分けかつ処理後のpivotの位置を返す。
    int underPivotLast = first-1;
    struct Card pivot,temp;
    pivot = A[last];
    for(int i=first;i<last;i++){
        if(A[i].value <= pivot.value){
            underPivotLast++;
            temp = A[underPivotLast];
            A[underPivotLast] = A[i];
            A[i] = temp;
        }
    }
    temp = A[underPivotLast+1];
    A[underPivotLast+1] = A[last];
    A[last] = temp;
    return underPivotLast+1;
}

void quickSort(struct Card A[],int first,int last){
    int pivot;
    if(first < last){
        pivot = partition(A,first,last);
        quickSort(A,first,pivot-1);
        quickSort(A,pivot+1,last);
    }
}

int main(){
    int elementNum, value;
    int stable = 1;
    char suit[10];
    struct Card A[AMOUNT],B[AMOUNT];

    scanf("%d",&elementNum);
    for(int i=0;i<elementNum;i++){
        scanf("%s %d",suit,&value);
        A[i].suit = B[i].suit = suit[0];
        A[i].value = B[i].value = value;
    }
    mergeSort(B,elementNum,0,elementNum);
    quickSort(A,0,elementNum-1);

    for(int i=0;i<elementNum;i++){
        if(A[i].suit!=B[i].suit){
            stable = 0;
            break;
        }
    }
    if(stable==1){
        printf("Stable\n");
    }
    else{
        printf("Not stable\n");
    }
    for(int i=0;i<elementNum;i++){
        printf("%c %d\n",A[i].suit,A[i].value);
    }
    return 0;
}


Measured memory_bytes: 4052
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T> &p){ cout << "[" << p.first << ", " << p.second << "]"; return os; }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)

// constexpr int MOD = 1e9+7;

int main(void){
    Cin(int, n);
    for(int i = (int)(n/1.08 -10); i < n/1.08 + 10; i ++){
        if(floor(i * 1.08) == n){
            Cout(i);
            return 0;
        }
    }
    Cout(":(");
}




Measured memory_bytes: 256
#include <iostream>
#include <cassert>
#include <limits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <array>
#include <map>
#include <set>
#include <deque>
#include <list>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cstring>
#include <bitset>
#include <stack>
#include <queue>

using namespace std;

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

    int n;
    scanf("%d", &n);

    vector<int> dp(3);

    for (int i = 0; i < n; ++i) {
        vector<int> c(3);
        for (int j = 0; j < 3; ++j) scanf("%d", &c[j]);

        vector<int> new_dp(3);
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                if (k != j) {
                    new_dp[k] = max({new_dp[k], dp[j] + c[k]});
                }
            }
        }
        dp = new_dp;
    }

    printf("%d", max({dp[0], dp[1], dp[2]}));
}


Measured memory_bytes: 256
N = int(input())
S = input()
ans = 0

for i in range(N):
    if S[i] == "E":
        ans += 1
min_ans = ans

for reader in range(1, N):
    minus = 0
    if S[reader] == "E":
        minus = 1
    if S[reader - 1] == "W":
        ans += 1
    elif S[reader - 1] == "E":
        ans -= 1
    if ans - minus < min_ans:
        min_ans = ans - minus
        count = reader

print(min_ans)

Measured memory_bytes: 3700
#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define _USE_MATH_DEFINES
# define M_PI 3.14159265358979323846
# define MOD 1000000007
#define ll long long int
#define pii pair<ll, ll>
#define pb push_back
#define MIN -9,223,372,036,854,775
#define N 100005


void solve(){
    ll i,j,k,n,x,y,f,c=0,d;
    cin>>n>>k>>d;
  	n = abs(n);
    x = n/d;
    if( k<=x ){
        cout<<abs(n-k*d);
        return;
    }
    ll r = k-x;
    ll m1 = n-x*d;
    ll m2 = abs( m1-d );
    if(r%2){
        cout<<m2;
    }
    else{
        cout<<m1;
    }
}

int main() {
    ll t;
	//cin>>t;
	t=1;
	while( t-- ){
	    solve();
	    cout<<"\n";
	}

	return 0;
}

Measured memory_bytes: 3196
#include<bits/stdc++.h>
using namespace std;
int main(){
  while(1){
    string str;
    cin>>str;
    if(str=="0"){
      break;
    }
    int sum=0;
    for(int i=0;i<(int)str.size();i++){
      sum+=str[i]-'0';
    }
    cout<<sum<<endl;
  }
}


Measured memory_bytes: 3164
from collections import defaultdict

import sys
sys.setrecursionlimit(10**6)
ii = lambda: int(input())
mis = lambda: map(int,input().split())
lmis = lambda: list(mis())
INF = float('inf')

def main():
    N,M=mis()
    nlis=[-1]*N
    num=defaultdict(set)
    for _ in range(M):
        a,b=mis()
        num[a].add(b)
    for i in range(1,N+1):
        if len(num[i])>1: no()
        elif num[i]: nlis[i-1]=num[i].pop()
    if nlis[N-1]<0: nlis[N-1]=0
    if N>1:
        if nlis[0]==0: no()
        if nlis[0]<0: nlis[0]=1
        if N==3 and nlis[1]<0:
            nlis[1]=0
    
    print((''.join([str(n) for n in nlis])))
    

def no():
    print(-1)
    exit()


if __name__ == "__main__":
    main()

Measured memory_bytes: 3316
H, W = map(int,input().split())
S = [list(input()) for i in range(H)]
ansm = [[""]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        cnt = 0
        if S[i][j]=="#":
            ansm[i][j]="#"
        else:
            if i>0 and j>0:
                if S[i-1][j-1]=="#":
                    cnt +=1
            if i>0:
                if S[i-1][j]=="#":
                    cnt+=1
            if i>0 and j<(W-1):
                if S[i-1][j+1]=="#":
                    cnt+=1
            if j>0:
                if S[i][j-1]=="#":
                    cnt+=1
            if j<W-1:
                if S[i][j+1]=="#":
                    cnt+=1
            if i<H-1 and j>0:
                if S[i+1][j-1]=="#":
                    cnt+=1
            if i<H-1:
                if S[i+1][j]=="#":
                    cnt+=1
            if i<H-1 and j<(W-1):
                if S[i+1][j+1]=="#":
                    cnt+=1
            ansm[i][j]=str(cnt)
ans = [""]*H
for i in range(H):
    for j in range(W):
        ans[i]=ans[i]+ansm[i][j]
for i in range(H):
    print(ans[i])

Measured memory_bytes: 3188
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val H = sc.nextInt()
    val N = sc.nextInt()
    val sum = (1..N).map { sc.nextInt() }.sum()
    if (sum >= H) {
        println("Yes")
    } else {
        println("No")
    }
}


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

int main() {
  int a, b;
  cin>>a>>b;
  int cnt = 0;
  for (int i=a; i<=b; i++) {
    string s = to_string(i);
    bool ok = true;
    for (int j=0; j < s.length(); j++) {
      if (s[j] != s[s.length()-1-j]) {
        ok = false;
        break;
      }
    }
    if (ok) {
      ++cnt;
    }
  }
  cout<<cnt<<endl;
}

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

#define FI(i,a,b) for(int i=(a);i<=(b);i++)
#define FD(i,a,b) for(int i=(a);i>=(b);i--)

#define LL long long
#define Ldouble long double
#define PI 3.1415926535897932384626

#define PII pair<int,int>
#define PLL pair<LL,LL>
#define mp make_pair
#define fi first
#define se second

using namespace std;

#define M 300003

int n, ans;
vector<int> v[M];
int lab[M];

void dfs(int id, int pv){
	int bitcnt[19];
	memset(bitcnt, 0, sizeof(bitcnt));
	for(auto to: v[id]) if(to != pv){
		dfs(to, id);
		FI(j, 0, 18) if(lab[to] & (1 << j)) bitcnt[j]++;
	}
	FD(i, 18, 0) if(bitcnt[i] > 1){
		FD(j, i, 0) bitcnt[j] = 1;
		break;
	}
	FI(i, 0, 18) lab[id] += bitcnt[i] * (1 << i);
	lab[id]++;
//	printf("%d: %d\n", id, lab[id]);
}

int main(){
	scanf("%d", &n);
	FI(i, 2, n){
		int a, b;
		scanf("%d %d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1, 0);
	int ans = 0;
	while(lab[1]){
		ans++;
		lab[1] >>= 1;
	}
	printf("%d\n", ans - 1);
	return 0;
}

Measured memory_bytes: 22144
MOD = 1000000007
n = int(input())
aas = list(map(int, input().split()))
KET = 60
arr_0 = [0]*KET
arr_1 = [0]*KET
for i in aas:
    bits = format(i,'060b')
    for j in reversed(range(KET)):
        if bits[j] == '0':
            arr_0[KET-j-1] += 1
        else:
            arr_1[KET-j-1] += 1
res = 0
for i in range(KET):
    res += (arr_0[i]%MOD * arr_1[i]%MOD)%MOD * pow(2,i,MOD)
    res %= MOD
print(res)

Measured memory_bytes: 124456
//Bismillahir rahmanir rahim
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<int>g[100005];
int dp[100005];
int solve(int n)
{
    int &ret=dp[n];
    if(ret!=-1) return ret;
    ret=0;
    for(int i=0;i<g[n].size();i++){
        int v=g[n][i];
        ret=max(ret,solve(v)+1);
    }
    return ret;
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        g[u].push_back(v);
    }
    int ans=0;
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++) ans=max(ans,solve(i));
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 8192
EXP = [1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144, 169, 196, 216, 225, 243, 256, 289, 324, 343, 361, 400, 441, 484, 512, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1000, 1001]
X = int(input())
for i, e in enumerate(EXP):
    if e > X:
        print(EXP[i - 1])
        break


Measured memory_bytes: 3060
from collections import deque

N, Q = map(int, input().split())
graph = {i:[] for i in range(N)}

for i in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    
nums = [0 for _ in range(N)]
for i in range(Q):
    p, x = map(int, input().split())
    nums[p-1] += x

queue = deque([0])
visited = [0]*N
while queue:
    v = queue.pop()
    if(visited[v]):
        continue
    visited[v] = 1
    for value in graph[v]:
        if(visited[value]):
            continue
        nums[value] += nums[v]
        queue.append(value)
print(*nums)

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

typedef long long int lli;

using namespace std;

const int MAX_VALUE = (1 << 30) + (1 << 30 - 1);



int main() {
	// your code goes here
	//cout << MAX_VALUE << endl;
	int max_value = 100000;
	int  n, W, i, j, k;
	cin >> n >> W;
	lli ans[n+1][max_value+1];
	lli w[n], v[n];
	for (i = 0; i < n+1; i++)
	{
		ans[i][0] = 0;
		for (j = 1; j < max_value+1; j++)
		{
			ans[i][j] = W+1;
		}
	}
	for (i = 0; i < n; i++)
	{
		cin >> w[i];
		cin >> v[i];
	}
	
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < max_value + 1; j++)
		{
			if (ans[i][j] == W + 1)
			{
				continue;
			}
			if (ans[i+1][j] > ans[i][j])
			{
				ans[i+1][j] = ans[i][j];
			}
			if ((ans[i][j]+w[i] <= W) && ((ans[i+1][j+v[i]]) > (ans[i][j] + w[i])))
			{
				ans[i+1][j+v[i]] = ans[i][j] + w[i];
			}
		}
		
	}
	lli max = 0;
	for (i = 1; i <= max_value; i++)
	{
		if (ans[n][i] <= W)
		{
			max = i;
		}
	}
	cout << max;
	return 0;
}

Measured memory_bytes: 79232
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <numeric>
#include <cmath>
#include <climits>
#include <limits>
#include <cfloat>
#include <fstream>
using namespace std;

int main()
{
	vector <int> W;
//	cut here before submit 
//	freopen("testcase.w", "r", stdin);
	string str = "";
	int i;
	for (i = 1; i <= 512; i *= 2){
		W.push_back(i);
	} // end for

	sort (W.begin(), W.end(), greater<int>() );
	int size = W.size();

	while (getline (cin, str ) ){
		vector <int> res;
		int wight = 0;
		stringstream ss(str);
		ss >> wight;
	
		for (i = 0; i < size; ++i){
			if (wight < W[i]){
				continue;
			}else if (wight == W[i]){
				res.push_back(W[i]);
				break;
			}else{	// if (wight > W[i])
				res.push_back(W[i]);
				wight -= W[i];
			} // end if
		} // end for

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

		for (i = 0; i < res.size(); ++i){
			cout << res[i];
			if (i != res.size() - 1){
				cout << ' ';
			} // end if
		} // end for
		cout << endl;
	} // end while

		
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(int i = a;i < b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(int i = b-1;i >= a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;

const ll INF=(1LL<<50);

template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}
ll gcd(ll a,ll b){
  if(a%b==0)return b;
  return gcd(b,a%b);
}
ll cnt_div(ll MAX,ll a,ll b){
  return MAX-MAX/a-MAX/b+MAX/(a*b/gcd(a,b));
}

void solve(long long A, long long B, long long C, long long D){
  cout<<cnt_div(B,C,D)-cnt_div(A-1,C,D)<<endl;
}

int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    long long D;
    scanf("%lld",&D);
    solve(A, B, C, D);
    return 0;
}


Measured memory_bytes: 256
a,b,m=map(int,input().split())
al=list(map(int,input().split()))
bl=list(map(int,input().split()))

tmp=99999999

for i in range(m):
    x,y,c=[int(i) for i in input().split()]
    cost = al[x-1] + bl[y-1] - c
    #各割引券を使った時の金額
    tmp=min(tmp,cost)

k=(min(al)+min(bl))
#割引券を使わなかった時の最小値
print(min(k,tmp))

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

using namespace std;

int main(void){
  int N;
  cin >> N;
  long long A[200000];
  long long c[200000] = {0};
  for(int i = 0; i < N; i++){
    cin >> A[i];
    c[A[i]]++;
  }
  long long total = 0;
  for(int i = 0; i < 200000; i++){
    total += c[i] * (c[i] - 1) / 2;
  }
  for(int i = 0; i < N; i++){
    cout << total - c[A[i]] + 1 << '\n';
  }
  cout << flush;
  return 0;
}


Measured memory_bytes: 5760
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const ll P=1e9+7;
const int maxn=2e5+5;
ll fac[maxn],inv[maxn];

ll q_pow(ll a,ll b){return b?q_pow(a*a%P,b/2)*(b%2?a:1)%P:1;}
ll c(ll n,ll k){
	ll x=1,y=1;
	for(int i=1;i<=k;i++){
		x=x*(n-i+1)%P;
		y=y*i%P;
	}
	return x*q_pow(y,P-2)%P;
} 
int main(){
	ll n,a,b;
	cin>>n>>a>>b;
	ll ans=q_pow(2,n);
	ans--;
	ans-=c(n,a);
	ans-=c(n,b);
	ans%=P;
	ans+=P;
	ans%=P;
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
/*
time:
wa:
反省:
考察:
*/
int main() {
    string S;
    cin >> S;
    int n = 0;
    int w = 0;
    int s = 0;
    int e = 0;
    for(int i = 0; i < S.size(); i++){
        if(S[i] == 'N') n++;
        else if(S[i] == 'W') w++;
        else if(S[i] == 'S') s++;
        else e++;
    }
    if(n != 0){
        if(s == 0) {
            cout << "No" << endl;
            return 0;
        }
    }
    if(w != 0){
        if(e == 0) {
            cout << "No" << endl;
            return 0;
        }
    }
    if(s != 0){
        if(n == 0) {
            cout << "No" << endl;
            return 0;
        }
    }
    if(e != 0){
        if(w == 0) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

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

    vector<i64> A(M),B(M);
    rep(i,0,M - 1){
        cin >> A[i] >> B[i];
    }
    using P = pair<i64,i64>;
    vector<P> vec;
    rep(i,0,M - 1){
        vec.push_back({B[i],A[i]});
    }

    sort(vec.begin(),vec.end());
    i64 right = 0;
    int ans = 0;
    rep(i,0,M - 1){
        i64 b = vec[i].first;
        i64 a = vec[i].second;
        if(!(a < right)){
            right = b;
            ans++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3956
import sys
r=sys.stdin.readline
for e in iter(r,'0 0\n'):
 N,M=map(int,e.split())
 k,p=1,0
 S=[int(r()) for _ in[0]*N]
 for d in[int(r())for _ in[0]*M]:
  p+=d if N<=p+d else d+S[p+d]
  if N<=p+1:break
  k+=1
 print(k)


Measured memory_bytes: 5652
#include<bits/stdc++.h>
using namespace std;
int N,X,Y;
int dp[1001][1001];
int G[14][14];
int DP[(1<<14)][14];
int mem[(1<<14)][1001];

int main(){
  scanf("%d %d %d",&N,&X,&Y);
  for(int id=0;id<N;id++){
    for(int i=0;i<=Y;i++)dp[id][i]=-1e9;
    dp[id][0]=0;
    int K;
    scanf("%d",&K);
    for(int i=0;i<K;i++){
      int a,b,c;
      scanf("%d %d %d",&a,&b,&c);
      for(int j=0;j<10;j++){
        int na=a*(1<<j);
        int nb=b*(1<<j);
        if(c-(1<<j)<0){
          na=a*c;
          nb=b*c;
          c=0;
        }else{
          c-=(1<<j);
        }
        for(int k=Y;k>=na;k--){
          if(dp[id][k]<dp[id][k-na]+nb){
            dp[id][k]=dp[id][k-na]+nb;
          }
        }
        if(c==0){
          break;
        }
      }
    }

    for(int i=1;i<=Y;i++){
      if(dp[id][i]<dp[id][i-1]){
        dp[id][i]=dp[id][i-1];
      }
    }
  }

  
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      scanf("%d",&G[i][j]);
    }
  }
  for(int k=0;k<N;k++){
    for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
        if(G[i][k]+G[k][j]<G[i][j]){
          G[i][j]=G[i][k]+G[k][j];
        }
      }
    }
  }
  
  for(int i=0;i<(1<<N);i++){
    for(int j=0;j<N;j++){
      DP[i][j]=100000000;
    }
  }

  DP[0][0]=0;
  for(int bit=0;bit<(1<<N);bit++){
    for(int pos=0;pos<N;pos++){
      for(int to=0;to<N;to++){
        int nbit=bit|(1<<to);
        int ncost=DP[bit][pos]+G[pos][to];
        if(DP[nbit][to]>ncost){
          DP[nbit][to]=ncost;
        }
      }
    }
  }

  

  mem[0][0]=0;
  for(int i=0;i<=Y;i++)mem[0][i]=-1e9;
  
  int ans=0;
  int tmp[1001];
  
  for(int bit=1;bit<(1<<N);bit++){
    int ny=min(Y,X-DP[bit][0]);

    int dit=bit- (bit&-bit);
    for(int i=0;i<=Y;i++) tmp[i]=mem[dit][i];
    tmp[0]=0;
    
    for(int i=0;i<N;i++){
      if( (bit>>i&1) ){
        for(int j=Y;j>=0;j--){
          int cc;
          cc=0;
          for(int k=0;k<=j;k++){
            cc++;
            if(cc>=100000/Y)break;
            if(tmp[j]<tmp[j-k]+dp[i][k]){
              tmp[j]=tmp[j-k]+dp[i][k];
            }
          }
          cc=0;
          for(int k=j;k>=0;k--){
            cc++;
            if(cc>=20000/Y)break;
            if(tmp[j]<tmp[j-k]+dp[i][k]){
              tmp[j]=tmp[j-k]+dp[i][k];
            }
          }
        }
        break;
      }
    }
    if(ny>=0 && ans<tmp[ny]){
      ans=tmp[ny];
    }
    for(int i=0;i<=Y;i++) mem[bit][i]=tmp[i];
  }
  
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 68144
#include <iostream>
#include <algorithm>
#include <functional>
#include<vector>
#include<math.h>
#include<bitset>
#include<string>
#include<queue>
using namespace std;

int main() {
	string S, T, C;
	cin >> S >> T;

	long long int Z = 0;
	for (int i = S.size()-1; i >=T.size()-1; i--) {
		C = S;
		
		if (S[i] == T[T.size()-1] || S[i] == '?') {
			C[i] = T[T.size()-1];
			int R = i;
			for (int k = T.size()-2; k >=0&&R>=0; k--) {
				R--;
				if (S[R] == T[k] || S[R] == '?') {
					C[R] = T[k];
				}
				else {
					goto go;
				}
			}
			Z++;
			goto re;

		}
	go:;
	}
re:;
	for (int i = 0; i < S.size(); i++) {
		if (C[i] == '?')C[i] = 'a';
	}

	if (Z == 0) {
		cout << "UNRESTORABLE" << endl;
	}
	else {
		cout << C << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

int main() {
	IO
	int n;
	cin >> n;
	int arr[n][3], dp[n][3] = {};
	int ans = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < 3; j++){
			cin >> arr[i][j];
			if (!i)
				dp[i][j] = arr[i][j], ans = max(ans, arr[i][j]);
		}
	}
	for (int i = 1; i < n; i++){
		for (int j = 0; j < 3; j++){
			dp[i][j] = arr[i][j] + max(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]);
			if (i == n - 1)
				ans = max(ans, dp[i][j]);
		}
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <algorithm>

using namespace std;

void solve() {
    long long a, b, x;
    cin >> a >> b >> x;
    long long ans;
    long long ar, bl;
    ar = a + (x - a % x) % x;
    bl = b - b % x;
    if (ar > b || bl < a) {
        cout << 0;
        return;
    }
    ans = (bl - ar) / x + 1;
    cout << ans;
}

int main() {

    solve();
    return 0;
}


Measured memory_bytes: 3152
import itertools
import math
n=int(input())
l=[list(map(int,input().split())) for _ in range(n)]
distance=[]
f=list(itertools.permutations(list(range(1,n+1))))
for i in range(len(f)):
    length=0
    for j in range(1,n):
        length+=math.sqrt((l[f[i][j]-1][0]-l[f[i][j-1]-1][0])**2+(l[f[i][j]-1][1]-l[f[i][j-1]-1][1])**2)
    distance.append(length)
print(sum(distance)/len(distance))

Measured memory_bytes: 15496
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

template<class T>
struct lca {
    int n, root, l;
    vector<vector<int> > to, par;
    vector<vector<T> > co;
    vector<int> dep;
    vector<T> costs;
    lca(int n):n(n), to(n), co(n), dep(n), costs(n) {
        l = 0;
        while((1<<l) < n) ++l;
        par = vector<vector<int> >(n+1, vector<int>(l, n));
    }
    void add(int a, int b, T c=0) {
        to[a].push_back(b); co[a].push_back(c);
        to[b].push_back(a); co[b].push_back(c);
    }
    void dfs(int v, int d=0, T c=0, int p=-1) {
        if(p != -1) par[v][0] = p;
        dep[v] = d;
        costs[v] = c;
        for(int i = 0; i < to[v].size(); ++i) {
            int u = to[v][i];
            if(u == p) continue;
            dfs(u, d+1, c+co[v][i], v);
        }
    }
    void init(int _root=0) {
        root = _root;
        dfs(root);
        for(int i = 0; i < l-1; ++i) {
            for(int v = 0; v < n; ++v) {
                par[v][i+1] = par[par[v][i]][i];
            }
        }
    }
    int lca_(int a, int b) {
        if(dep[a] > dep[b]) swap(a, b);
        int gap = dep[b]-dep[a];
        for(int i = l-1; i >= 0; --i) {
            int len = 1<<i;
            if(gap >= len) {
                gap -= len;
                b = par[b][i];
            }
        }
        if(a == b) return a;
        for(int i = l-1; i >= 0; --i) {
            int na = par[a][i];
            int nb = par[b][i];
            if(na != nb) {
                a = na;
                b = nb;
            }
        }
        return par[a][0];
    }
    int length(int a, int b) {
        int c = lca_(a, b);
        return dep[a]+dep[b]-dep[c]*2;
    }
    T dist(int a, int b) {
        int c = lca_(a, b);
        return costs[a]+costs[b]-costs[c]*2;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    lca<int> C(n);
    rep(i, n) {
        int k;
        cin >> k;
        rep(j, k) {
            int c;
            cin >> c;
            C.add(i, c);
        }
    }
    C.init();

    int q;
    cin >> q;
    while(q--) {
        int u, v;
        cin >> u >> v;
        cout << C.lca_(u, v) << '\n';
    }
}


Measured memory_bytes: 27972
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int h,w,k;
  cin>>h>>w>>k;
  int ways=0;
  string ch[h];
  for(int i=0;i
      <h;i++)
    cin>>ch[i];
  int poe[7];
  poe[0]=1;
  for(int i=1;i<=6;i++) poe[i]=2*poe[i-1];
  for(int i=0;i<poe[h];i++)
  {
    for(int j=0;j<poe[w];j++)
    {int bl=0;
      for(int ii=0;ii<h;ii++)
      {
        for(int jj=0;jj<w;jj++)
        {
          if(ch[ii].at(jj)=='#' && (i & (1 << ii))==0 && (j & (1 << jj))==0)
            bl++;
        }
      }
      if(bl==k) ways++;
    }
  }
  cout<<ways<<endl;
  return 0;
}        

Measured memory_bytes: 3568