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

 using namespace std;

 int main() {
   int i, j, k, A, B, C, X, ans;

   cin >> A >> B >> C >> X;

   ans = 0;
   for (i = 0; i <= A; i++) {
     for (j = 0; j <= B; j++) {
       for (k = 0; k <= C; k++) {
         if (500 * i + 100 * j + 50 * k == X) ans++;
       }
     }
   }

   cout << ans << endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef unsigned long ulong;
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

int main()
{
	ulong w, h, x, y;
	cin >> w >> h >> x >> y;
	if (x == w / 2.0 && y == h / 2.0) {
		cout << (w * h / 2.0);
		cout << " ";
		cout << 1;
	}
	else {
		cout << (w * h / 2.0);
		cout << " ";
		cout << 0;
	}
}


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



using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	map<long long int, long long int> m;
	long long int n;cin>>n;
	long long int c=0;
	vector<long long int>a(n+1);
	for(long long int i=1;i<=n;i++){
		cin>>a[i];
	}
	a[0]=0;
	for(long long int i=1;i<=n;i++){
		if(m.count(i-a[i])>0){
			c+=m[i-a[i]];
		}
		m[i+a[i]]++;
		
	}
	cout<<c;
	return 0;
}

Measured memory_bytes: 17056
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define REP(i, n) for(i=0; i<n; i++)
#define REPR(i, n) for(i=n; i>=0; i--)
#define FOR(i, m, n) for(i=m; i<n; i++)
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define INF 10000000000
#define MOD 1000000007LL
#define MAX 100005
#define NIL -1
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> doup;

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

int main(void) {
    ll n, a;
    cin >> n >> a;
    if(n%500<=a) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int mat[4][N],val[N],n,num[2],v[N];
void add(int x,int val) {
  for ( ; x <= n ; x += ((x) & (-(x))))
    v[x] += val;
}
int query(int x) {
  int ret = 0;
  for ( ; x ; x -=  ((x) & (-(x))))
    ret += v[x];
  return ret;
}
void fail() {
  puts("No");
  exit(0);
}
int main() {
  scanf("%d",&n);
  for (int i = 1 ; i <= 3 ; ++ i)
    for (int j = 1 ; j <= n ; ++ j)
      scanf("%d",&mat[i][j]);
  for (int i = 1 ; i <= n ; ++ i) {
    if (mat[1][i] % 3 == 0) {
      if (mat[2][i] == mat[1][i] - 1 && mat[3][i] == mat[1][i] - 2)
    val[i] = - mat[1][i] / 3;
      else fail();
    } else if (mat[3][i] % 3 == 0) {
      if (mat[2][i] == mat[3][i] - 1 && mat[1][i] == mat[3][i] - 2)
    val[i] = mat[3][i] / 3;
      else fail();
    } else fail();
  }
  for (int i = 1 ; i <= n ; i += 2) {
    if (val[i] < 0) num[1] ^= 1, val[i] = -val[i];
    if (val[i] % 2 == 0) fail();
  }
  for (int i = 2 ; i <= n ; i += 2) {
    if (val[i] < 0) num[0] ^= 1, val[i] = -val[i];
    if (val[i]&1) fail();
  }
  for (int i = 1 ; i <= n ; i += 2) {
    if ((query(n) - query(val[i]))&1) num[0] ^= 1;
    add(val[i],1);
  }
  memset(v,0,sizeof v);
  for (int i = 2 ; i <= n ; i += 2) {
    if ((query(n) - query(val[i]))&1) num[1] ^= 1;
    add(val[i],1);
  }
  if ((!num[0]) && (!num[1]))
    puts("Yes");
  else puts("No");
  return 0;
}

Measured memory_bytes: 2176
N, _ = input().split()
N = int(N)
dislike = list(map(int, input().split()))
like = []
f = True
l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
x = N
for i in l:
    if i not in dislike:
        like.append(i)
like = list(str(like))
dislike = list(str(dislike))
while f:
    x = list(str(x))
    for i in x:
        if i not in dislike:
            f = False
        else:
            f = True
            break
    x = int("".join(x)) + 1

if x != 0:
    x -= 1
print(x)

Measured memory_bytes: 9084
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<map>
#include<queue>
#include<set>
#include<bitset>
#include<stdio.h>
#include<deque>
#include<iomanip>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
typedef long long ll;

int main()
{
    int a, b, ans = 0;;
    cin >> a >> b;
    for(int i = 0; i <= a; i++){
        for(int j = 0; j <= a; j++){
            int c = b -(i+j);
            if(c <= a && c >= 0){
                ans++;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#define Mod 998244353
#define Maxn 300000
int b[5];
char s[Maxn+5];
int f(char c){
	if(c=='R'){
		return 0;
	}
	if(c=='G'){
		return 1;
	}
	return 2;
}
int main(){
	int n;
	scanf("%d",&n);
	scanf("%s",s+1);
	int ans=1;
	int t0,t1,t2;
	for(int i=1;i<=3*n;i++){
		t0=f(s[i]);
		t1=(t0+1)%3;
		t2=(t1+1)%3;
		if(b[t0]>=b[t1]&&b[t0]>=b[t2]){
			b[t0]++;
			continue;
		}
		else if(b[t0]<b[t1]&&b[t0]>=b[t2]){
			ans=1ll*ans*(b[t1]-b[t0])%Mod;
		}
		else if(b[t0]<b[t2]&&b[t0]>=b[t1]){
			ans=1ll*ans*(b[t2]-b[t0])%Mod;
		}
		else if(b[t1]<b[t2]){
			ans=1ll*ans*(b[t1]-b[t0])%Mod;
		}
		else{
			ans=1ll*ans*(b[t2]-b[t0])%Mod;
		}
		b[t0]++;
	}
	for(int i=1;i<=n;i++){
		ans=1ll*i*ans%Mod;
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

int main(){

	deque<int> DEQ;

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

	int command,A,B;

	for(int loop = 0; loop < num_query; loop++){
		scanf("%d",&command);

		switch(command){
		case 0:

			scanf("%d %d",&A,&B);
			if(A == 0){
				DEQ.push_front(B);
			}else{
				DEQ.push_back(B);
			}
			break;
		case 1:

			scanf("%d",&A);
			printf("%d\n",DEQ[A]);

			break;
		case 2:
			scanf("%d",&A);
			if(A == 0){
				DEQ.pop_front();
			}else{
				DEQ.pop_back();
			}
			break;
		}
	}

	return 0;
}




Measured memory_bytes: 4716
#include <bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
using ll = long long;
const char newl = '\n';
#define var auto

string a, b;

vector<int> getCore(int begin, int end, string& str){
    vector<int> res{};
    int depth = 0;
    for (int i = begin; i <= end; i++){
        if (str[i] == '(') depth++;
        if (str[i] == ')') depth--;
        if ((str[i] == '[' || str[i] == ']') && depth == 0) res.push_back(i);
    }
    return res;
}

string dfs(int abegin, int aend, int bbegin, int bend){
    var coreAPos = getCore(abegin, aend, a);
    var coreBPos = getCore(bbegin, bend, b);
    if (coreAPos.size() == 0 || coreBPos.size() == 0) {
        return "";
    }
    var coreA = atoi(a.substr(coreAPos[0] + 1, coreAPos[1] - coreAPos[0] - 1).c_str());
    var coreB = atoi(b.substr(coreBPos[0] + 1, coreBPos[1] - coreBPos[0] - 1).c_str());
    var core = coreA + coreB;

    var l = dfs(abegin + 1, coreAPos[0] - 2, bbegin + 1, coreBPos[0] - 2);
    var r =  dfs(coreAPos[1] + 2, aend - 1, coreBPos[1] + 2, bend - 1);
    return '(' + l + ')' + '[' + to_string(core) + ']' + '(' + r + ')';
}


signed main(){
    cin >> a >> b;
    cout << dfs(0, a.size() - 1, 0, b.size() - 1) << endl;
}



Measured memory_bytes: 3284
import java.io.*;
import java.util.*;

public class Main {
    public static void main (String[] args) {
        MyScanner sc = new MyScanner();

        char[] s = sc.next().toCharArray();

        if (s[0] == 'S')
            System.out.println("Cloudy");
        else if (s[0] == 'C')
            System.out.println("Rainy");
        else
            System.out.println("Sunny");
    }

    static class MyScanner {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 1 << 15);
        StringTokenizer tokenizer;

        String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
            } catch (IOException ignored) {
            }
            return tokenizer.nextToken();
        }

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

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

Measured memory_bytes: 20820
a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
 
b = int(input())
r = ''
while b > 0:
  b -= 1
  c = b % len(a)
  r = a[c] + r
  b = int(b / len(a))
print(r)

Measured memory_bytes: 9108
import java.util.Scanner;
class Main{
 
    public void solve(){
		Scanner sc = new Scanner(System.in);
       int a, b;
	   a = sc.nextInt();
	   b = sc.nextInt();
	   
	   if(a < b){
	   	System.out.print("a < b");
	   }else if(a > b){
	   	System.out.print("a > b");
	   }else if(a == b){
	   	System.out.print("a == b");
	   }
	  
	   System.out.println();
	   
    }
		   
	   
    public static void main(String[] args){
        Main obj = new Main();
        obj.solve();
    }
}

Measured memory_bytes: 17160
def swap(A, x, y):
    i = A[x]
    A[x] = A[y]
    A[y] = i

def left(i):
    return i * 2

def right(i):
    return i * 2 + 1

def  maxHeapify(A, i, H):
    l = left(i)
    r = right(i)
    #  ????????????????????????????????§???????????§????????????????????¶
    if l <= H and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r <= H and A[r] > A[largest]:
        largest = r

    if largest != i: #// i ???????????????????????§????????´???
        swap(A, i, largest) # ??????
        maxHeapify(A, largest, H) # ?????°??????????????????

def buildMaxHeap(A, H):
    for i in range(int(H/2),0,-1):
        maxHeapify(A, i, H)

def main():

    """ ????????? """
    H = int(input().strip())
    A = [""]
    A.extend(list(map(int,input().split())))
    buildMaxHeap(A, H)
    print(" {}".format(" ".join(map(str,A[1:]))))

if __name__ == '__main__':
    main()

Measured memory_bytes: 66284
#include <cassert>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <csignal>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cinttypes>
#include <cstdint>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <chrono>
#include <forward_list>
#include <initializer_list>
#include <random>
#include <regex>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;

using Field = vector<vector<ll>>;
using Graph = vector<vector<ll>>;
using VI = vector<int>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VC = vector<char>;
using PI = pair<int, int>;

#define FOR(i, s, n) for (int i = s; i < (n); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) x.begin(), x.end()

const long long INF = 1LL<<60;
const int mod = 1000000007;

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; }

double A, B, H, M;

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

    cin >> A >> B >> H >> M;

    double m = 6 * M;
    double h = 30 * H + 0.5 * M;
    double kakudo = abs(m - h);

    double cosi = cos(M_PI * kakudo / 180);

    double c = sqrt(pow(B, 2) + pow(A, 2) - 2 * B * A * cosi);

    cout << setprecision(20) << c << endl;

    return 0;
}

Measured memory_bytes: 4240
n, m = gets.split(" ").map(&:to_i)
brokens = []
m.times do
  brokens.push(gets.to_i)
end

memo = []
memo.push(1) #0マス先
memo.push(1) #1マス先
n.times do |index| #2マス先以降
  memo.push(memo[index] + memo[index + 1])
end

now = 0
multipliers = []
brokens.each do |broken|
  if now == broken
    puts 0
    exit
  end
  multipliers.push(memo[(broken - 1) - now])
  now = broken + 1
end

multipliers.push(memo[n - now])

answer = 1
multipliers.each do |multiplier|
  answer *= multiplier
end

puts answer % 1_000_000_007

Measured memory_bytes: 453556
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
#define int long long
#define INF 1e9
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;

signed main(){
   int n;
   string s;
   cin>>n>>s;
   int x=n/2;
   if(n%2!=0) {
       cout<<"No"<<endl;
       return 0;
   }
   for (int i = 0; i < x; i++)
   {
       if(s[i]!=s[i+x]){
           cout<<"No"<<endl;
           return 0;
       }
   }
   
   cout<<"Yes"<<endl;

   
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

int f[26];

int main() {
    char ch = fgetc(stdin);
    while (ch != '\n') {
        f[ch - 'a']++;
        ch = fgetc(stdin);
    }
    int p = 0;
    char rez;
    for (int i = 0; i <= 25 && p == 0; i++) {
        if (f[i] == 0) {
            p = 1;
            rez = 'a' + i;
        }
    }
    if (p == 1)
        printf("%c", rez);
    else
        printf("None");
    return 0;
}


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

typedef long long ll;

ll N;
vector<ll> fac;

int main() {
	scanf("%lld", &N);

	for (ll i = 1; i * i <= N; ++i) {
		if (N % i) continue;
		fac.push_back(i);
		if (i * i < N) fac.push_back(N / i);
	}

	ll tot = 0;

	for (ll f : fac) {
		if (f > 1 && (N % (f-1)) * f == N) tot += f - 1;
	}

	printf("%lld\n", tot);
}


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

int main() {
  cin >> s;
  int dp[2] = {0, 1 << 30};
  for(int i = 0; i < (int)s.size(); ++i) {
    int x = s[i] - '0';
    int y = min(dp[0] + x, dp[1] + x);
    int z = min(dp[0] + 11 - x, dp[1] + 9 - x);
    dp[0] = y;
    dp[1] = z;
  }
  cout << min(dp[0], dp[1]);
  return 0;
}

Measured memory_bytes: 1412
a,b = map(int,input().split())

#最大公約数
def gcb(a,b):
    while b!=0:
        a,b=b,a%b
    return a
#最小公倍数
def lcm(a,b):
    return a * b // gcb(a, b)
    
print(lcm(a,b))

Measured memory_bytes: 2940
#include <stdio.h>

int solve(int, int);

int A[20], n;

int main()
{
  int i;
  int q, m;
  
  scanf("%d",&n);
  for(i=0; i<n; i++){
    scanf("%d",&A[i]);
  }
  
  scanf("%d",&q);
  for(i=0; i<q; i++){
    scanf("%d",&m);
    if(solve(0, m)==1) printf("yes\n");
    else printf("no\n");
  }
  
  return 0;
}

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

Measured memory_bytes: 580
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)


template<typename T> class segtree{
private:
    int n,sz;
    vector<T> node;
public:
    segtree(vector<T>& v) : sz((int)v.size()){
        n = 1;
        while(n < sz){
            n *= 2;
        }
        node.resize(2*n-1, numeric_limits<T>::min());
        for(int i = 0; i < sz; i++){
            node[i+n-1] = v[i];
        }
        for(int i=n-2; i>=0; i--){
            node[i] = max(node[i*2+1], node[i*2+2]);
        }
    }
    void update(int k,T a){
    	k += n-1;
    	node[k] = a;
    	while(k>0){
            k = (k-1)/2;
            node[k] = max(node[2*k+1],node[2*k+2]);
    	}
    }
    T query(int a,int b,int k=0,int l=0,int r=-1){
        if(r < 0) r = n;
    	if(r <= a || b <= l){
            return numeric_limits<T>::min();
    	}
    	if(a <= l && r <= b){
            return node[k];
    	}else{
            T vl = query(a,b,2*k+1,l,(l+r)/2);
            T vr = query(a,b,2*k+2,(l+r)/2,r);
            return max(vl,vr);
    	}
    }
    void print(){
        for(int i = 0; i < sz; i++){
            cout<<query(i,i+1)<< " ";
        }
        cout<<endl;
    }
};


int main(){
    int n;
    cin >> n;
    vector<int> h(n),q(n+1);
    rep(i,n){
        cin >> h[i];
        q[h[i]] = i;
    }
    vector<ll> a(n);
    rep(i,n)cin >> a[i];
    vector<ll> f(n);
    segtree<ll> sg(f);
    rep(i,n){
        int ind = q[i+1];
        //cerr << ind << endl;
        ll p = sg.query(0,ind+1);
        sg.update(ind,p+a[ind]);
    }
    cout << sg.query(0,n) << endl;
    return 0;
}

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

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

    ll sum = 0;
    for (size_t i = 1; i <= N; i++)
    {
        if (i % 3 == 0 || i % 5 == 0)
        {
            continue;
        }
        sum += i;
    }
    cout << sum << endl;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll LINF = 1e18;
const int INF = 1e9;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){
    int N,H; cin>>N>>H;
    int a[N],b[N];
    rep(i,N)cin>>a[i]>>b[i];
    sort(a,a+N);
    sort(b,b+N);
    int cnt=0;
    rep(i,N){
        if(a[N-1]<=b[i])cnt++;
    }
    int ans=0;
    int i=1;
    do{
        H-=b[N-i];
        i++;
        ans++;
    }while(H>0&&i<=cnt);
    if(H<=0){
        cout<<ans<<endl;
        return 0;
    }
    else{
        int c=H/a[N-1];
        if(H%a[N-1]==0)ans+=c;
        else ans+=(c+1);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4392
function Main(input){
	input1 = input.split(' ');
    input2 = input1.map(input1=>parseInt(input1,10));
    a = input2[0] + input2[1];
    b = input2[0] - input2[1];
    c = input2[0] * input2[1];

    console.log(Math.max(a, b, c)+0);
}
 
Main(require("fs").readFileSync("/dev/stdin","utf8"));

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

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

    int a[M], odd = 0;
    for (int i = 0; i < M; ++i) {
        cin >> a[i];
        odd += a[i] % 2;
    }

    if (M == 1) {
        cout << a[0] << endl;
        if (a[0] == 1) {
            cout << 1 << endl;
            cout << a[0] << endl;
        } else {
            cout << 2 << endl;
            cout << a[0] - 1 << " " << 1 << endl;
        }
        return 0;
    }

    // 可能性判定
    if (odd > 2) {
        cout << "Impossible" << endl;
        return 0;
    }

    // 奇数要素を両端に持っていく
    odd = 0;
    for (int i = 0; i < M; ++i) {
        if (a[i] % 2 == 1) {
            ++odd;
            if (odd == 1) {
                swap(a[i], a[0]);
            } else if (odd == 2) {
                swap(a[i], a[M - 1]);
            }
        }
    }

    // 数列aを出力
    for (int i = 0; i < M; ++i) {
        if (a[i] > 0) {
            cout << a[i] << " ";
        }
    }
    cout << endl;

    // 数列bを構築
    vector<int> b;

    --a[0];
    ++a[M - 1];
    for (int i = 0; i < M; ++i) {
        // 0を出力してはいけないことに注意
        if (a[i] > 0) b.push_back(a[i]);
    }

    // 数列bを出力
    cout << b.size() << endl;
    for (int c : b) {
        cout << c << " ";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s << endl; }



template <class Abel> struct BIT {
    const Abel UNITY_SUM = 0;                       // to be set
    vector<Abel> dat;
    
    /* [1, n] */
    BIT(int n) : dat(n + 1, UNITY_SUM) { }
    void init(int n) { dat.assign(n + 1, UNITY_SUM); }
    
    /* a is 1-indexed */
    inline void add(int a, Abel x) {
        for (int i = a; i < (int)dat.size(); i += i & -i)
            dat[i] = dat[i] + x;
    }
    
    /* [1, a], a is 1-indexed */
    inline Abel sum(int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i)
            res = res + dat[i];
        return res;
    }
    
    /* [a, b), a and b are 1-indexed */
    inline Abel sum(int a, int b) {
        return sum(b - 1) - sum(a - 1);
    }
    
    /* debug */
    void print() {
        for (int i = 1; i < (int)dat.size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

int main() {
    int N;
    long long K;
    cin >> N >> K;
    vector<long long> S(N+1, 0);
    for (int i = 0; i < N; ++i) {
        long long a;
        cin >> a;
        S[i+1] = S[i] + (a - K);
    }
    vector<long long> SS = S;
    sort(SS.begin(), SS.end());
    SS.erase(unique(SS.begin(), SS.end()), SS.end());
    long long res = 0;
    BIT<long long> bit(N+10);
    for (int i = 0; i <= N; ++i) {
        int id = lower_bound(SS.begin(), SS.end(), S[i]) - SS.begin();
        res += bit.sum(id+1);
        bit.add(id+1, 1);

        //cout << S[i] << ": " << id << endl; bit.print();
    }
    cout << res << endl;
}



Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
typedef long long ll;
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
template <class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p){os<<"("<<p.first<<","<< p.second<<")";return os;}
template <class T> ostream &operator<<(ostream &os, const vector<T> &v){os<<"{";REP(i,(int)v.size()){if(i)os<<",";os<<v[i];}os<<"}";return os;}
template <typename T, size_t S> void printArray(const T (&array)[S]){for(auto val : array)std::cout << val << ", ";std::cout << "\n";}
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}
const double PI=acos(-1);
const ll MOD = 1000000007;
using Graph = vector<vector<int>>;
template<class T>inline bool chmax(T& a, T b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T& a, T b){if(a > b){a = b; return 1;}return 0;}
const ll INF = 1LL<<60;
//const int dx[4] = {1, 0, -1, 0};
//const int dy[4] = {0, 1, 0, -1};
//const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
//const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

void solve(){
    ll h, w; cin >> h >> w;
    vector<string> vs;
    REP(i, h){
        string s; cin >> s;
        vs.pb(s);
    }
    REP(i, h){
        cout << vs[i] << endl;
        cout << vs[i] << endl;
    }
}

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

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

int main() {
  int x[10]={0};
  std::string a;
  cin >> a;
  for(int i=0;i<10;i++){
      if(a[i]=='A'||a[i]=='G'||a[i]=='C'||a[i]=='T')x[i]=1;
  }
  int res=0,temp;
  for(int i=0;i<10;i++){
    for(int j=0;j<10-i;j++){
      temp=1;
      for(int k=0;k<i+1;k++){
        temp*=x[k+j];
      }
      if(temp!=0)res=i+1;
    }
  }
  cout << res << endl;
}


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

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int a[3], b[3], c[3][3], t;
	
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			cin >> c[i][j];
			
	for(int i = 0; i < 3; i++)
	{
		for(int j = i + 1; j < 3; j++)
		{
			if(c[0][i] - c[0][j] != c[1][i] - c[1][j] || c[0][i] - c[0][j] != c[2][i] - c[2][j] || c[1][i] - c[1][j] != c[2][i] - c[2][j] || c[i][0] - c[j][0] != c[i][1] - c[j][1] || c[i][0] - c[j][0] != c[i][2] - c[j][2] || c[i][1] - c[j][1] != c[i][2] - c[j][2])
			{
				cout << "No";
				return 0;
			}//if
		}//for j
	}//for i
	
	cout << "Yes";
	
	return 0;
}//main


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

int main() {
  int n;
  while(cin >> n && n!=-1) {
    int k=262144;
    string s="";
    while(1) {
      char a='0';
      if(n>=k) {
	a=(char)(n/k+48);
      }
      s+=a;
      if(k==1) break;
      n%=k;
      k/=4;
    }
    stringstream ss;
    ss << s;
    long long m;
    ss >> m;
    stringstream ss2;
    ss2 << m;
    ss2 >> s;
    cout << s << endl;
  }
  return 0;
}


Measured memory_bytes: 1236
#include <iostream>
#include <algorithm>
using namespace std;
long long h,w,ans=1e9,a,b,c;
int main(){
    cin>>h>>w;
    for(int i=0;i<2;i++){
        if(i){
            long long t=h;
            h=w;
            w=t;
        }
        for(int i=1;i<h;i++){
            a=i*w;
            b=max((h-i)*(w/2),((h-i)/2)*w);
            c=h*w-a-b;
            ans=min(max(a,max(b,c))-min(a,min(b,c)),ans);
        }
    }
    cout<<ans;
}


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

bool myless(tuple<string, int, int> lhs, tuple<string, int, int> rhs) {
  if (get<0>(lhs) != get<0>(rhs)) {
    return (get<0>(lhs) < get<0>(rhs));
  } else {
    return (get<1>(lhs) > get<1>(rhs));
  }
}

int main() {
  int N = 0;
  cin >> N;
  
  vector<tuple<string, int, int>> sp(N);
  string s_tmp = "";
  int p_tmp = 0;
  for (int i = 0; i < N; ++i) {
    cin >> s_tmp >> p_tmp;
    sp[i] = make_tuple(s_tmp, p_tmp, i + 1);
  }
  
  sort(sp.begin(), sp.end(), myless);
  
  for (int i = 0; i < N; ++i) {
    cout << get<2>(sp[i]) << endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
while(1):
    n = int(input())
    if n==0: break
    table = [0 for i in range(24*60*60)]
    for i in range(n):
        s,g=input().split()
        s=list(map(int,s.split(':')))
        x=(s[0]*60+s[1])*60+s[2]
        g=list(map(int,g.split(':')))
        y=(g[0]*60+g[1])*60+g[2]
        table[x]+=1
        table[y]-=1
    ret=table[0]
    for i in range(1,24*60*60):
        table[i]+=table[i-1]
        ret=max(ret,table[i])
    print(ret)



Measured memory_bytes: 9608
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
 
public class Main {
    public static void main(String[] arg)throws IOException{
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		int a ,b;
		String str = br.readLine();
		String strARY[] = str.split(" ");
		a= Integer.parseInt(strARY[0]);
		b = Integer.parseInt(strARY[1]);
		
		if(a>b){
			System.out.println("a > b");
		}else if(a<b){
			System.out.println("a < b");
		}else{
			System.out.println("a == b");
		}
    }
}

Measured memory_bytes: 17084
// AOJ 0272: The Lonely Girl's Lie
// 2017.10.14 bal4u@uu
// 2017.11.1 retry

#include <stdio.h>
#include <stdlib.h>

int a[40003], b[40003];

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

char buf[280100], *p;
int getint()
{
	int n = 0;
	while (*p >= '0') n = (n<<3) + (n<<1) + (*p++ & 0xf);
	return n;
}

int main()
{
	int n, i, k, ans;

	while (fgets(p=buf, 10, stdin) && *buf != '0') {
		n = getint();
		fgets(p=buf, 280100, stdin);
		for (i = 0; i < n; i++) a[i] = getint(), p++;
		fgets(p=buf, 280100, stdin);
		for (i = 0; i < n; i++) b[i] = getint(), p++;
		
		qsort(a, n, sizeof(int), cmp);
		qsort(b, n, sizeof(int), cmp);

		for (ans = n, i = k = 0; k < n; i++, k += 2) {
			if (a[k] > b[i]) { ans = k + 1; break; }
		}
		if (ans == n) puts("NA");
		else printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 2404
def bfs(n,e,fordfs):
    #点の数、スタートの点、有向グラフ
    W = [-1]*n
    #各点の状態量、最短距離とか,見たかどうかとか
    W[e] = 0
    que = deque()
    que.append(e)
    len = [float("inf")]*n
    len[e] = 0
    while que:
        now = que.popleft()
        nowv = W[now]
        nowlen = len[now]
        for ne in fordfs[now]:
            if nowlen==2:
                #ループが嫌な時
                return len
            elif W[ne] == -1:
                W[ne] = (nowv+1) % 2
                len[ne] = nowlen+1
                que.append(ne)
    return len


def examC():
    N, M = LI()
    v = [[] for _ in range(N)]
    for i in range(M):
        a, b = LI()
        v[a-1].append(b-1)
        v[b-1].append(a-1)
    judge = bfs(N,0,v)
    if judge[-1]>2:
        ans = "IMPOSSIBLE"
    else:
        ans = "POSSIBLE"
    print(ans)

import sys
import copy
import bisect
import heapq
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()


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

int main(){
    int N;  cin >> N;
    double ans = 0;
    for(int i=0; i<N; i++){
        double x;  string u;
        cin >> x >> u;
        if(u=="JPY"){
            ans += x;
        }else{
            ans += x*380000;
        }
    }
    cout << setprecision(10) << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <list>
using namespace std;
 
int main()
{
    list<int> a;
    list<int>::iterator c = a.end();
    int q;
 
    cin >> q;
 
    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
 
        if (t == 0) {
            int x;
            cin >> x;
 
            c = a.insert(c, x);
        }
        else if (t == 1) {
            int d;
            cin >> d;
 
            if (d > 0) {
                for (int j = 0; j < d; j++)
                    c++;
            }
            else {
                for (int j = 0; j < -d; j++)
                    c--;
            }           
        }
        else if (t == 2) {
            c = a.erase(c);
        }
    }
 
    for (list<int>::iterator itr = a.begin(); itr != a.end(); itr++)
        cout << *itr << endl;
 
    return 0;
}


Measured memory_bytes: 18660
import sys
input = sys.stdin.readline
N = int(input())
P = list(map(int, input().split()))

P_ = sorted(P)

cnt = 0
for i in range(N):
    if P[i] != P_[i]:
        cnt += 1
if cnt <= 2:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 38256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
	
	static long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a%b);
	}
	
	public static void main(String[] args) throws IOException {
		MyScanner sc = new MyScanner();
		PrintWriter out = new PrintWriter(System.out);
		long a = sc.nextInt();
		long b = sc.nextInt();
		long gcd = gcd(a, b);
		char[] aVals = sc.next().toCharArray();
		char[] bVals = sc.next().toCharArray();
		long len = a * b / gcd;
		boolean can = true;
		long first = len / a;
		long second = len / b;
		long ff = 0, ss = 0;
		int fi = 0, si = 0;
		while (ff < len && ss < len && can) {
			if (ff == ss) {
				if (aVals[fi] != bVals[si]) can = false;
				ff += first;
				ss += second;
				fi++;
				si++;
			} else if (ff < ss) {
				ff += first;
				fi++;
			} else {
				ss += second;
				si++;
			}
		}
		out.println(can ? len : -1);
		
		out.flush();
	}
	
	static class MyScanner {
		private BufferedReader br;
		private StringTokenizer tokenizer;
		
		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
	}
}


Measured memory_bytes: 25172
def II(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

N,M=MI()
H=LI()
ans=0
Michi=[[] for i in range(N)]
Ten=[1] *N
for i in range(M):
  a,b=MI()
  a-=1
  b-=1
  Michi[a].append(b)
  Michi[b].append(a)
for j in range(N):  
  for k in Michi[j]:
    if H[k]>=H[j]:
      Ten[j]=0
      break
ans=sum(Ten)
print(ans)

Measured memory_bytes: 30240
c = 0
s = 0
num = 0
while True:
    try:
        p, n = [int(x) for x in input().split(",")]
        s += p * n
        c += n
        num += 1
    except:
        break
print(s)
av = c // num
if c%num >= num//2:
    av +=1
print(av)



Measured memory_bytes: 5596
#include<iostream>
using namespace std;
int main() {
  int N;
  cin >> N;
  long long a,b,c;
  a = b = c = 1;
  int i;
  for(i=0;i<N;i++) {
    a = (a*10)%1000000007;
    b = (b*9)%1000000007;
    c = (c*8)%1000000007;
  }
  cout << ((a - 2*b + c)%1000000007+1000000007)%1000000007 << endl;
}

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

int gojo(int a)
{
    int ans;
    ans = a*a*a*a*a;
    return ans;
}
int main(){
    int x, i, j;
    cin >> x;
    for(i=-118;i<120;i++){
        for(j=-119;j<119;j++){
            if(gojo(i)-gojo(j) == x){
                cout << i << " " << j << endl;
                return 0;
            }
        } 
    }
    return 0;
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
static const int64_t mod=1000000007;
int main(){
int N,M;
  cin>>N>>M;
  vector<int64_t>x(N);
  for(int i=0;i<N;i++)
    cin>>x.at(i);
  vector<int64_t>y(M);
  for(int i=0;i<M;i++)
    cin>>y.at(i);
  int64_t X=0;
  for(int i=0;i<N;i++){
  int64_t k=(mod+2*i-N+1)%mod;
    k=(k*x.at(i))%mod;
    X=(X+k)%mod;
  } int64_t Y=0;
  for(int i=0;i<M;i++){
  int64_t k=(mod+2*i-M+1)%mod;
    k=(k*y.at(i))%mod;
    Y=(Y+k)%mod;
  }int64_t ans=(X*Y)%mod;
  ans=(ans+mod)%mod;
  cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<iomanip>
using namespace std;

int main() {

	int A;
	int B;
	cin >> A >> B;

	int ans = max(A + B, max(A + A - 1, B + B - 1));

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define all(v) begin(v), end(v)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 2000000000
#define int long long int

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};
int const MOD = 1000000007;
ll mod_pow(ll x, ll n) {return (!n)?1:(mod_pow((x*x)%MOD,n/2)*((n&1)?x:1))%MOD;}
int madd(int a, int b) {return (a + b) % MOD;}
int msub(int a, int b) {return (a - b + MOD) % MOD;}
int mmul(int a, int b) {return (a * b) % MOD;}
int minv(int a) {return mod_pow(a, MOD-2);}
int mdiv(int a, int b) {return mmul(a, minv(b));}

namespace std {
    bool operator<(const P& a, const P& b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

signed main() {
    int n; cin >> n;
    vector<int> a(3*n);
    rep(i,0,3*n) cin >> a[i];
    sort(a.begin(), a.end(), greater<int>());

    int ans = 0, cnt = 0;
    for(int i=1; cnt<n; i+=2) {
        ans += a[i];
        cnt++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2560
#include"bits/stdc++.h"
using namespace std;



int main(void) {

	int P, Q, R, ans;
	priority_queue<int> q;
	cin >> P >> Q >> R;

	q.push(P);
	q.push(Q);
	q.push(R);

	ans = P + Q + R;
	
	cout << ans - q.top() << endl;

	return 0;
}

Measured memory_bytes: 256
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
  string S, T;
  cin >> S >> T;
  unsigned int ans = S.length();
  for (unsigned int i = 0; i <= S.length() - T.length(); i++) {
    unsigned int chgcnt = 0;
    for (unsigned int j = 0; j < T.length(); j++) {
      if (S[i+j]!=T[j]) {
        chgcnt++;
      }
    }
    ans = min(ans, chgcnt);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3636
#include <stdio.h>
 
int main(void){
	int a[3];
    scanf("%d %d %d",&a[0],&a[1],&a[2]);
    if((a[0]==a[1])&&(a[1]==a[2])){
        printf("Yes");
    }else{
		printf("No");
    }
	return 0;
}


Measured memory_bytes: 128
from collections import deque
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


class ModInt(int):
    
    MOD = 7

    def __new__(cls, x, *args, **kwargs):
        return super().__new__(cls, x % ModInt.MOD)

    def __add__(self, other):
        return ModInt(super().__add__(other) % ModInt.MOD)
    
    def __radd__(self, other):
        return ModInt(super().__radd__(other) % ModInt.MOD)
    
    def __mul__(self, other):
        return ModInt(super().__mul__(other) % ModInt.MOD)
    
    def __rmul__(self, other):
        return ModInt(super().__rmul__(other) % ModInt.MOD)
    
    def __pow__(self, other, *args):
        return ModInt(super().__pow__(other, ModInt.MOD))

    def __rpow__(self, other, *args):
        raise NotImplementedError()
    
    def __truediv__(self, other):
        return ModInt(super().__mul__(pow(other, ModInt.MOD-2, ModInt.MOD)))
    
    def __floordiv__(self, other):
        return self.__truediv__(other)
    
    def __rtruediv__(self, other):
        return ModInt(self.__pow__(ModInt.MOD-2).__mul__(other))
    
    def __rfloordiv__(self, other):
        return self.__rtruediv__(other)


def read():
    ModInt.MOD = 10**9+7
    H, W = map(int, input().strip().split())
    M = []
    for i in range(H):
        M.append(input().strip())
    return H, W, M


def solve(H, W, M):
    dp = [ModInt(0) for i in range(W+1)]
    dp[1] = 1
    for i in range(1, H+1):
        for j in range(1, W+1):
            dp[j] = (dp[j] + dp[j-1]) if M[i-1][j-1]=='.' else 0
    return dp[W]


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))


Measured memory_bytes: 4464
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <vector>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <deque>
#include <string>
#include <list>
#include <iterator>
#include <algorithm>
#include <unordered_map>
#define int                long long
#define pb                 push_back
#define pi                 pair<int,int>
#define vi                 vector<int>
#define all(v)             v.begin(),v.end()
#define MOD                1000000007
#define F                  first
#define S                  second
#define FOR(i,r)           for(int i=0;i<r;i++)
#define REP(i,l,r)         for(int i=l;i<r;i++)
#define RER(i,l,r)         for(int i=l;i>=r;i--)
#define print(v)           for(auto i : v)cout << i << ' ';
#define FASTIO             ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mem(arr,k)         memset(arr,k,sizeof(arr));
#define pii                acos(-1.0)
#define PI                 3.1415926535897932385
#define Sin(a)             sin((pi*a)/180)
#define remax(a,b)         a=max(a,b)
#define remin(a,b)         a=min(a,b)
#define bitcount(x)        __builtin_popcountll(x)
#define iceil(n,x)         (((n)-1)/(x)+1)
#define flush              fflush(stdout)
#define pf                 push_front()
#define pob                pop_back()
#define ins                insert
#define mii                map<int,int> 
#define show(x)            for(auto zz:x)cout<<zz<<" ";cout<<"\n";
#define show2(x)           for(auto zz:x)cout<<zz.F<<" "<<zz.S<<"\n";
#define test()             int x;cin >> x;while(x--){solve();}
#define test2()            int x;cin >> x;for(int i=1;i<=x;i++){cout << "Case #" << i << " : ";solve();}
#define watch(x)           cout << (#x) << " is " << (x) << endl
using namespace std;


/* Mathematical Functions */
int power(int x,int y);
bool isPrime(int n);
int modInv(int a,int b);
int gcdExtended(int a,int b,int *x,int* y);
int mpower(int a,int b,int p);

const int inf = (int)1e17;
const int N = (int)3e5+5;

int32_t main(){

	
	FASTIO;
	int n,x = 0;
	cin >> n;
	vi v(n);
	REP(i,0,n){
		cin >> v[i];
		x ^= v[i];
	}
	REP(i,0,n){
		cout << (v[i]^x) << ' ';
	}
    return 0;

}
int modInv(int a, int m)
{
int x, y;
int g = gcdExtended(a, m, &x, &y);
int res = (x%m + m) % m;
return res;
}
 
int gcdExtended(int a, int b, int *x, int *y)
{
if (a == 0){
    *x = 0, *y = 1;
    return b;
  }
  int x1, y1;
  int gcd = gcdExtended(b%a, a, &x1, &y1);
  *x = y1 - (b/a) * x1;
  *y = x1;
  return gcd;
}
 
int mpower(int x, int y, int p)
{
int res = 1;
x = x % p;
while(y > 0){
    if(y & 1) res = (res*x) % p;
      y = y>>1;
      x = (x*x) % p;
    }
    return res;
}
int power(int x, int y)
{
int res = 1;
while (y > 0){
    if (y & 1) res = res*x;
      y = y>>1;
      x = x*x;
    }
    return res;
}
 
bool isPrime(int n)
{
if (n <= 1)  return false;
  if (n <= 3)  return true;
    if (n%2 == 0 || n%3 == 0) return false;
      int p=sqrt(n);
      for(int i=5;i<=p;i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
          return false;
      return true;
}

Measured memory_bytes: 4328
#include <bits/stdc++.h>
 
using namespace std;
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
 
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> P;
 
const ll INF = 1ll<<30;
const ll MOD = 1000000007;
const double EPS  = 1e-10;
 
int n, a, b, c, d;
ll dp[1001][1001];
 
vector<ll> fact, inv;
 
ll mod_pow(ll x, ll n, ll mod) {
	if (n == 0) return 1;
	ll res = mod_pow(x * x % mod, n / 2, mod);
	if (n & 1) res = res * x % mod;
	return res;
}
 
void fact_inv(int n, ll mod) {
	fact.resize(n + 1);
	inv.resize(n + 1);
	
	fact[0] = 1;
	FOR(i, 1, n + 1) fact[i] = fact[i - 1] * i % mod;
	inv[n] = mod_pow(fact[n], mod - 2, mod);
	for (int i = n; i > 0; i--) inv[i - 1] = inv[i] * i % mod;
}
 
ll nCr(ll n, ll r) {
	if (n < r || r < 0 || n < 0) return 0;
	return fact[n] * inv[r] % MOD * inv[n - r] % MOD;
}
 
ll dfs(int rem, int mi) {
	if (rem == 0) return 1;
	if (mi > b || rem < mi) return 0;
	
	if (~dp[rem][mi]) return dp[rem][mi];
	
	ll res = dfs(rem, mi + 1);
	
	ll p = 1;
	FOR(i, 1, c) p = p * nCr(rem - mi * (i - 1), mi) % MOD;
	
	FOR(i, c, d + 1) {
		if (rem < mi * i) break;
		p = p * nCr(rem - mi * (i - 1), mi) % MOD;
		
		res += p * dfs(rem - mi * i, mi + 1) % MOD * inv[i] % MOD;
	}
		
	return dp[rem][mi] = res % MOD;
}
 
int main() {
	cin >> n >> a >> b >> c >> d;
	fact_inv(n, MOD);
	
	fill(dp[0], dp[n + 1], -1);
	cout << dfs(n, a) << endl;
	
	return 0;
}

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

int main() {
    int n; cin >> n;
    int t[n];
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }
    int m; cin >> m;
    for (int i = 0; i < m; i++) {
        int p, x, sum = 0;
        cin >> p >> x;
        int temp = t[p-1];
        t[p-1] = x;
        for (int i = 0; i < n; i++) {
            sum += t[i];
        }
        cout << sum << endl;
        t[p-1] = temp;
    }
    return 0;
}

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



typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<ll> vint;
typedef vector< vector<ll> > vvint;
typedef pair<ll, ll> pint;


#define rep(i,n) for(ll i=0;i<n;i++)



void print(const vint& v)
{
  for(int i=0; i+1<v.size(); ++i){
    std::cout << v[i] << " ";
  }
  cout<<v.back()<<endl;
}


ll insertionSort(vint &a, ll g){
  ll cnt = 0;
  ll n = a.size();
  for(ll i=g; i<n; ++i){
    ll v = a[i];
    ll j = i - g;
    while(j >= 0 && a[j] > v){
      a[j+g] = a[j];
      j -= g;
      cnt++;
    }
    a[j+g] = v;
  }

  return cnt;
}

ll shellSort(vint &a){
  ll n = a.size();
  ll cnt = 0;

  // ll m = ceil(sqrt(n));
  // ll m = ceil(pow(n, 1.0/4.0));
  vint G;
  // for(ll i=m; i>=1; --i) G.push_back(i);

  ll m = 1;
  ll num = 2;
  G.push_back(1);
  while(num < n){
    G.push_back(num);
    // num = 3*num + 1;
    num <<= 1;
    m++;
  }

  reverse(G.begin(), G.end());

  cout<<m<<endl;
  print(G);

  rep(i,m){
    cnt += insertionSort(a, G[i]);
  }

  return cnt;
}

int main() {


  cout<<fixed<<setprecision(10);

  ll n; cin>>n;
  vint a(n); rep(i,n) cin>>a[i];

  cout << shellSort(a) <<endl;

  rep(i,n) cout<<a[i]<<endl;


}





//




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

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()
    a = LI()

    s = 0
    for c in a:
        s ^= c

    rr = []
    for c in a:
        rr.append(s ^ c)


    return JA(rr, ' ')


print(main())




Measured memory_bytes: 43304