akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int i,j,n,m;
int wall[200][3],tx,ty,sx,sy;

int crosscheck(int tx,int ty,int sx,int sy,int wx,int wy,int rr){

	int abx=sx-tx,aby=sy-ty;
	int awx=wx-tx,awy=wy-ty;
	int bwx=wx-sx,bwy=wy-sy;

	int rr2=rr*rr;
	int aw2=awx*awx+awy*awy;
	int bw2=bwx*bwx+bwy*bwy;
	int ab2=abx*abx+aby*aby;

	int tim=abx*awy-aby*awx;
	int abw=abx*awx+aby*awy;

	if(aw2<rr2 && bw2<rr2)return 0;
	if(aw2<rr2 || bw2<rr2)return 1;
	if(abw<0)return 0;
	if(abw>ab2)return 0;
	if( tim*tim/ab2 <= (double)rr2)return 1;

	return 0;
}

int main(){
	while(scanf("%d",&n)*n){

		for(i=0;i<n;i++)scanf("%d %d %d",&wall[i][0],&wall[i][1],&wall[i][2]);

		for(scanf("%d",&m);m>0;m--){
			scanf("%d %d %d %d",&tx,&ty,&sx,&sy);
			int sss=0;
			for(i=0;i<n;i++){
				int wx=wall[i][0],wy=wall[i][1],rr=wall[i][2];
				if(crosscheck(tx,ty,sx,sy,wx,wy,rr))break;
			}
			if(i<n)printf("Safe\n"); else printf("Danger\n");
		}
	}
	return 0;
}

Measured memory_bytes: 584
import std.stdio, std.string, std.array, std.conv, std.algorithm, std.typecons, std.range, std.container, std.math, std.algorithm.searching, std.functional,std.mathspecial;

void main(){
    auto N=readln.chomp.to!int;
    if(N==1){
        writeln(1);
        return;
    }

    long[int] divs;

    auto primes=get_primes(N);

    foreach(p;primes){
        divs[p]=0;
    }

    foreach(n;2..N+1){
        foreach(p;primes){
            while(n%p==0){
                n/=p;
                divs[p]++;
            }
            if(n==1)break;
        }
    }

    auto res=1L;
    foreach(d;divs.values){
        res=res*(d+1)%1000000007;
    }

    writeln(res);
}

int[] get_primes(int max){
    int[] ps;
    foreach(n;2..max+1){
        if(isPrime(n,ps))ps~=n;
    }
    return ps;
}

bool isPrime(int n, int[] prims){
    foreach(p;prims){
        if(n%p==0)return false;
    }
    return true;
}

Measured memory_bytes: 256
n=int(input())
s=set()
for i in range(n):
    a,b=map(int,input().split())
    if a==0:
        s.add(b)
        print(len(s))
    elif a==1:
        if b in s:
            print(1)
        else:
            print(0)
    else:
        if b in s:
            s.remove(b)
        


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


 
 
long int knapSack(int W,  long int wt[],  long int val[], int n) 
{ 
   int i, w; 
  long int K[n+1][W+1]; 
  
   // Build table K[][] in bottom up manner 
   for (i = 0; i <= n; i++) 
   { 
       for (w = 0; w <= W; w++) 
       { 
           if (i==0 || w==0) 
               K[i][w] = 0; 
           else if (wt[i-1] <= w) 
                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]); 
           else
                 K[i][w] = K[i-1][w]; 
       } 
   } 
  
   return K[n][W]; 
} 
  
 
 
int main()
{ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
   
    int n, W;
    cin >> n;
      cin >> W;
     long int val[n], wt[n];
    for (int i = 0; i < n; i++)
    {
     
        cin >> wt[i];
         cin >> val[i];
    }
 

    cout << knapSack(W,wt, val,n);
 
      return 0;}

Measured memory_bytes: 79232
N = int(input())
W = list(map(int,input().split()))

import math

cnt = sum(W)
for i in range(1,N):
  if abs(sum(W[:i])-sum(W[i:])) <= cnt:
    cnt = abs((sum(W[:i])-sum(W[i:])))
  #print(abs(sum(W[:i])-sum(W[i:])))
print(cnt)

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

int main(void){
    string s; cin >> s;

    int ans = 0;
    if(s[0] == 'R' && s[1] == 'R' && s[2] == 'R'){
        ans = 3;
    }
    else if(s[0] == 'R' && s[1] == 'R'){
        ans = 2;
    }
    else if(s[1] == 'R' && s[2] == 'R'){
        ans = 2;
    }
    else if(s[0] == 'S' && s[1] == 'S' && s[2] == 'S'){
        ans = 0;
    }
    else{
        ans = 1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    string S;
    cin >> S;
    S.insert(0, "_");
    vector<vector<long long>> dp(4, vector<long long>(S.size(), 0));
    long long mod = 1000000007;
 
    dp[0][0] = 1;
    for (int i = 0; i <= 3; i++)
    {
        for (int j = i; j < S.size(); j++)
        {
            if (i == 0)
            {
                if (j > 0)
                {
                    switch (S[j])
                    {
                    case '?':
                        dp[i][j] = (3 * dp[i][j - 1]) % mod;
                        break;
                    default:
                        dp[i][j] = dp[i][j - 1];
                        break;
                    }
                }
            }
            else if (i == 1)
            {
                switch (S[j])
                {
                case 'A':
                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1]) % mod;
                    break;
                case '?':
                    dp[i][j] = (3 * dp[i][j - 1] + dp[i - 1][j - 1]) % mod;
                    break;
                default:
                    dp[i][j] = dp[i][j - 1];
                    break;
                }
            }
            else if (i == 2)
            {
                switch (S[j])
                {
                case 'B':
                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1]) % mod;
                    break;
                case '?':
                    dp[i][j] = (3 * dp[i][j - 1] + dp[i - 1][j - 1]) % mod;
                    break;
                default:
                    dp[i][j] = dp[i][j - 1];
                    break;
                }
            }
            else
            {
                switch (S[j])
                {
                case 'C':
                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1]) % mod;
                    break;
                case '?':
                    dp[i][j] = (3 * dp[i][j - 1] + dp[i - 1][j - 1]) % mod;
                    break;
                default:
                    dp[i][j] = dp[i][j - 1];
                    break;
                }
            }
        }
    }
 
    cout << dp[3][S.size() - 1] << endl;
}


Measured memory_bytes: 4352
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <string>
#include <tuple>
#include <fstream>
#include <cmath>
#include <chrono>
#include <thread>
#include <stack>
#include <memory.h>
#include <numeric>
#include <iostream>
#include<climits>

//  vector<vector<int>> b(row_size, vector<int>(col_size,n));   //  n->initialized value

#define MOD 1000000007LL
#define ff first
#define fs second
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vll vector<long long>
#define vvi vector< vector <int> >
#define vpii vector< pair<int, int> >
#define pii pair<int,int>
#define mii map<int, int>
#define mp make_pair
#define tc                int T;cin>>T;while(T--)
#define fast_io            ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ll long long int

using namespace std;
int length[100001];
vector<int> neighbours[100001];

int findl(int node) {
    if (neighbours[node].size() == 0)return 0;
    if (length[node] != -1)return length[node];
    int ans = -1;
    for (int& n : neighbours[node]) {
        ans = max(ans, 1 + findl(n));
    }
    return length[node]=ans;
}
int main() {
    fast_io;
    int nodes, edges;
    memset(length, -1, sizeof length);
    //memset(neighbours, -1, sizeof neighbours);
   cin >> nodes >> edges;
   int a, b;
    for (int i = 0; i < edges; ++i) {
        cin >> a >> b;
        neighbours[a].push_back(b);
    }
    int ma = 0;
    for (int i = 1; i <= nodes; ++i) {
        length[i] = findl(i);
        ma = max(ma, length[i]);
    }
    cout << ma;
    return 0;

}


Measured memory_bytes: 8192
// Input macro
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! stdin {
    () => {{
        use std::io::Read;
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }};
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

// Test Code
macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => {
        #[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input), $output);
            )*
        }
    };
}

test! {
    "4 8 2" => "3",
    "0 5 1" => "6",
    "9 9 2" => "0",
    "1 1000000000000000000 3" => "333333333333333333"
}

fn main() {
    println!("{}", solve(&stdin!()));
}

fn solve(src: &str) -> String {
    input! {
        source = src,
        a: usize,
        b: usize,
        x: usize
    }

    let num_a = if a == 0 { 0 } else { (a - 1) / x + 1}; 
    let num_b = b / x + 1;

    (num_b - num_a).to_string()
}

Measured memory_bytes: 4352
#include <iostream>
using namespace std;
void pRec(int h, int w) {
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      cout << "#";
    }
    cout << "\n";
  }
  cout << "\n";
}
int main(void) {
  int h, w;
  for(;;) {
    cin >> h >> w;
    if (h == 0 && w == 0)
      return 0;
    pRec(h, w);
  }
}



Measured memory_bytes: 3008
use proconio::input;
use std::collections::HashMap;

fn main() {
    input! {
        n: i64,
    }

    let mut n = n;
    let mut factors = HashMap::new();

    let sqrt = (n as f64).sqrt() as i64;

    for i in 2..(sqrt + 1) {
        while n % i == 0 {
            let count = factors.entry(i).or_insert(0);
            *count += 1;
            n /= i;
        }
    }
    if n > 1 {
        factors.insert(n, 1);
    }

    // for e in factors.values().copied() {
    //     dbg!(e);
    // }

    let mut ans = 0i64;
    for (_, e) in factors {
        let mut sum = 0;
        let mut i = 0;
        let k = loop {
            if sum + (i + 1) > e {
                break i
            }

            sum += i + 1;
            i += 1;
        };

        ans += k;
    }

    println!("{}", ans);
}


Measured memory_bytes: 2172
#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; }



struct UnionFind {
    vector<int> par, con;
    
    UnionFind(int n) : par(n, -1), con(n, 1) { }

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        con[x] += con[y];
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

using pint = pair<int,int>;
int main () {
    int N, M, K;
    cin >> N >> M >> K;
    vector<set<int> > dame(N);
    UnionFind uf(N);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        dame[a].insert(b);
        dame[b].insert(a);
        uf.merge(a, b);
    }
    for (int i = 0; i < K; ++i) {
        int c, d; cin >> c >> d; --c, --d;
        if (!uf.issame(c, d)) continue;
        dame[c].insert(d);
        dame[d].insert(c);
    }

    for (int i = 0; i < N; ++i) {
        int mem = uf.con[uf.root(i)] - 1; // 同じ連結成分の「自分以外」の人数
        mem -= dame[i].size(); // その中ですでに友達かブロック関係の人数
        cout << mem << " ";
    }
    cout << endl;
}


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

int main(){
  int a,b;
  cin >> a >> b;
  if(a==2 || b==2) cout << "No" << endl;
  else if((a==4 || a==6) || (a==9 || a==11)){
    if((b==4 || b==6) || (b==9 || b==11)) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
  else if((b==4 || b==6) || (b==9 || b==11)){
    if((a==4 || a==6) || (a==9 || a==11)) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
  else cout << "Yes" << endl;
}

Measured memory_bytes: 256
def main():
    s = input()
    i = "AC" in s
    if i:
        print("Yes")
    else:
        print("No")
    # print(123)
    # b = [int(a) for a in input().split(" ")]
    # print(b)
    # [input() for a in range(3)]


if __name__ == "__main__":
    main()


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

int main() {
  string s;
  cin >> s;
  string ans = "";
  for (int i = 0; i < (int)s.size(); ++i) {
    if (s[i] == 'B') {
      ans = ans.substr(0, ans.size() - 1);
    } else {
      ans = ans + s[i];
    }
  }

  cout << ans << endl;

  return 0;
}


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

int main() {
    int n; cin >> n;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int c; cin >> c;
        if (c != i+1) cnt++;
    }
    if (cnt == 0 || cnt == 2) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

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

int main() {
    int N;
    cin >> N;
    string s, t;
    cin >> s >> t;
    string ns, nt;
    rep(i, s.size()) {
        ns = s.substr(i);
        nt = t.substr(0, s.size() - i);
        if (ns == nt)
            break;
    }

    int res;
    if (ns != nt)
        res = N * 2;
    else
        res = N * 2 - ns.size();
    cout << res << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <math.h>
#include <cmath>
#include <vector>
using namespace std;

typedef struct NODE {
    int key;
    struct NODE *right;
    struct NODE *left;
    struct NODE *parent;
} Node;

int m;
Node *root;

Node *newNode(int key) {
    Node *n = new Node;
    n->key = key;
    n->right = NULL;
    n->left = NULL;
    n->parent = NULL;
    return n;
}

void insert(int key) {
    Node *r = root;
    Node *n;

    while (r) {
        if (key < r->key) {
            if (r->left) {
                r = r->left;
            } else {
                n = newNode(key);
                r->left = n;
                n->parent = r;
                return;
            }
        } else {
            if (r->right) {
                r = r->right;
            } else {
                n = newNode(key);
                r->right = n;
                n->parent = r;
                return;
            }
        }
    }
}

void walkInOrder(Node *n) {
    if (n != NULL) {
        if (n->left != NULL) {
            walkInOrder(n->left);
        }
        cout << " " << n->key;
        if (n->right != NULL) {
            walkInOrder(n->right);
        }
    }
}

void printInOrder() {
    walkInOrder(root);
    cout << endl;
}

void walkPreOrder(Node *n) {
    if (n != NULL) {
        cout << " " << n->key;
        if (n->left != NULL) {
            walkPreOrder(n->left);
        }
        if (n->right != NULL) {
            walkPreOrder(n->right);
        }
    }
}

void printPreOrder() {
    walkPreOrder(root);
    cout << endl;
}

void printBinarySearchTree() {
    printInOrder();
    printPreOrder();
}

void makeRoot(string inst, int key) {
    if (inst != "insert") {
        cout << "error" << endl;
        return;
    }
    root = newNode(key);
}

void readInst() {
    int key;
    string inst;
    cin >> inst >> key;
    makeRoot(inst, key);

    for (int i = 1; i < m; i++) {
        cin >> inst;
        if (inst == "insert") {
            cin >> key;
            insert(key);
        } else if (inst == "print") {
            printBinarySearchTree();
        } else {
            cout << "invalid instruction" << endl;
            return;
        }
    }
}

int main() {
    cin >> m;
    readInst();

    return 0;
}


Measured memory_bytes: 26616
s = input()
a = s[0] + s[1]
b = s[2] + s[3]
p = 0
q = 0
if a == "01" or a == "02" or a == "03" or a == "04" or a == "05" or a == "06" or a == "07" or a == "08" or a == "09" or a == "10" or a == "11" or a == "12":
    p = 1
if b == "01" or b == "02" or b == "03" or b == "04" or b == "05" or b == "06" or b == "07" or b == "08" or b == "09" or b == "10" or b == "11" or b == "12":
    q = 1  
if p == 1 and q == 1:
    print("AMBIGUOUS")
elif p == 1 and q == 0:
    print("MMYY")
elif p == 0 and q == 1:
    print("YYMM")
else:
    print("NA")

Measured memory_bytes: 9088
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using lint = long long;
using namespace std;

const int MOD = 1000000007;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    vector<int> B(A);

    lint s = 0;
    int c= 0;
    int minv = 1000000001;

    rep(i, N) {
        s += abs(A[i]);
        minv = min(minv, abs(A[i]));
        if (A[i] < 0) {
            c++;
        }
    }

    if (c % 2 == 0) std::cout << s << endl;
    else std::cout << (s - 2 * minv) << endl;

    return 0;
}


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

int solve(int*,int,int,int);

int main(){
  int i,n,q,*A,*m;

  scanf("%d",&n);
  if(n > 20)exit(1);
  A = malloc((n+1) * sizeof(int));
  for(i=0;i < n;i++){
    scanf("%d",&A[i]);
  }
  scanf("%d",&q);
  if(q > 200)exit(3);
  m = malloc(q * sizeof(int));
  for(i=0;i < q;i++){
    scanf("%d",&m[i]);
  }
  for(i=0;i < q;i++){
    if(solve(A,n,0,m[i]))printf("yes\n");
    else printf("no\n");
  }
  
  return 0;  
}

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



Measured memory_bytes: 2104
import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), y = sc.nextInt() / 1000;
        int ans1 = -1, ans2 = -1, ans3 = -1;
        for(int i = 0; i <= n; i++)
            for(int j = 0;  j <= n - i; j++)
                if(9 * i + 4 * j + n == y){
                    ans1 = i;
                    ans2 = j; 
                    ans3 = n - i - j;
                }
        System.out.println(ans1 + " " + ans2 + " " + ans3);
    }
}

Measured memory_bytes: 23252
use std::io;
use std::io::prelude::*;
use std::io::BufReader;
use std::str::FromStr;

fn read_vec<T: FromStr>(s: String) -> Result<Vec<T>, T::Err> {
    s.split(' ').map(|x| x.parse()).collect()
}

fn main() {
    const M: i64 = 1000_000_000 + 7;
    let mut lines = BufReader::new(io::stdin()).lines().map(|l| l.unwrap());
    let nk: Vec<usize> = read_vec(lines.next().unwrap()).unwrap();
    let k = nk[1];
    let mut v: Vec<i64> = read_vec(lines.next().unwrap()).unwrap();
    let mut P: Vec<_> = v.iter().filter(|&&x| x > 0).collect();
    let mut N: Vec<_> = v.iter().filter(|&&x| x < 0).collect();
    P.sort_unstable();
    N.sort_unstable();
    // 正の数にできるか否か
    let can_positive = if P.len() >= k {
        true // Pが十分あればok
    } else if P.len() == 0 {
        k & 1 == 0 && k <= N.len() // Pがゼロ個なら、kが偶数で、Nはkより多い必要がある
    } else {
        // Pが1つ以上あって、kより少ない時
        (k - P.len() + 1) & !1 <= N.len() // Pが一つ以上あれば、k-Pを2の倍数に切り上げた数より、Nが多い必要がある
    };
    if !can_positive {
        if v.contains(&0) {
            // ゼロにできる時
            println!("0");
        } else {
            // 負の数になる時
            v.sort_unstable_by_key(|x| {
                let y = x >> 31;
                (x ^ y) - y
            });
            let ans = v
                .iter()
                .take(k) // 小さい方から集めて
                .fold(1, |acc, x| acc * (x % M) % M);
            println!("{}", (ans + M) % M);
        }
        return;
    }
    let mut ans = 1;
    let mut k = k;
    if k & 1 == 1 {
        ans *= P.pop().unwrap();
        k -= 1;
    }
    let mut P = P.rchunks_exact(2).map(|x| x[0] * x[1]).peekable();
    let mut N = N.chunks_exact(2).map(|x| x[0] * x[1]).peekable();
    while k > 0 {
        // pnどっちからとるか。 両方空っぽはありえない
        let pn = match P.peek() {
            Some(p) => match N.peek() {
                Some(n) => p > n,
                _ => true,
            },
            _ => false,
        };
        ans *= if pn { P.next() } else { N.next() }.unwrap() % M;
        ans %= M;
        k -= 2;
    }
    println!("{}", (ans + M) % M);
}

Measured memory_bytes: 6188
#include <bits/stdc++.h>
using namespace std;
int n,z[100004];
void z_function(string go){
    int l=0,r=0;
    for (int i=1;i<go.size();i++){
        if (i>r){
            l=i,r=i;
            while (r<go.size() && go[r-l]==go[r]) r++;
            z[i]=r-l,r--;
    	}else{
            int k=i-l;
            if (z[k]<r-i+1) z[i]=z[k];
            else{
                l=i;
                while (r<go.size() && go[r-l]==go[r]) r++;
                z[i]=r-l,r--;
            }
        }
    }
}
int ans=0;
string s;
int main(){
	cin>>n>>s;
	for (int i=0;i<s.size();i++){
		string go=s.substr(i)+"$"+s.substr(0,i);
		z_function(go);
		int maxn=0;
		for (int j=s.size()-i+1;j<go.size();j++)
			maxn=max(maxn,z[j]);
		ans=max(ans,maxn);
	}
	cout<<ans;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <ios>
#include <iostream>
#include <vector>

#define ll long long

using namespace std;

string s[3];

int main()
{
    for (int i=0; i<3; i++) {
        cin >> s[i];
    }
    cout << 'A' << s[1][0] << 'C' << endl;
    return 0;
}

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

using namespace std;

#define ll long long
#define ld long double
#define pll pair <ll , ll>

#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mp make_pair

#define X first
#define Y second

#define LB(x) ((x) & -(x))
#define BIT(a , b) (((a)>>(b)) & 1)

const ll MAXN=1e2+10;
const ll Mod=1e9+7;
const ll INF=1e9+10;

ll a[MAXN];

ll pw(ll x , ll n)
{
    if (n==0)
    {
        return 1;
    }

    ll w=pw(x , n/2);
    w*=w;
    w%=Mod;

    if (n&1)
    {
        w*=x;
        w%=Mod;
    }

    return w;
}

pll solve(ll l , ll r)
{
    if (l>r)
    {
        return mp(1 , 1);
    }

    ll res=0 , t=1 , w=1 , d=0 , e=INF;

    for(ll i=l;i<=r;i++)
    {
        e=min(e , a[i]);
    }

    ll z=l;

    for(ll i=l;i<=r;i++)
    {
        a[i]-=e;

        if (a[i]==0)
        {
            pll f=solve(z , i-1);

            t*=f.Y;
            t%=Mod;

            w*=f.X;
            w%=Mod;

            d++;
            z=i+1;
        }
    }

    pll f=solve(z , r);

    t*=f.Y;
    t%=Mod;

    w*=f.X;
    w%=Mod;

    res+=(pw(2 , d)*w)%Mod;
    res%=Mod;

    res+=(pw(2 , e)*t)%Mod;
    res%=Mod;

    res+=(t*((pw(2 , e)-2+Mod)%Mod))%Mod;
    res%=Mod;

    return mp(res , (pw(2 , e)*t)%Mod);
}

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

	ll n;
	cin>>n;

	for(ll i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    pll res=solve(1 , n);

    cout<<(res.X-res.Y+Mod)%Mod;
}


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

namespace atcoder096_D
{
    class Program
    {
        static void Main(string[] args)
        {
            //入力を受け取る
            int N = int.Parse(Console.ReadLine());

            //下一桁が1になる素数を55個作る
            int[] sosu = new int[55];
            bool sosujdg = true;
            sosu[0] = 11;
            int cnt = 1;
            for (int i = 21; i < 55555; i = i + 10)
            {
                for (int j = 2; j < i; j++)
                {
                    if (i % j == 0)
                    {
                        sosujdg = false;
                        break;
                    }
                }
                if (sosujdg == true)
                {
                    sosu[cnt] = i;
                    cnt++;
                }
                sosujdg = true;
                if (cnt >= 55) break;
            }

            
            //出力
            for(int i =0;i<N;i++)
            {
                Console.Write(sosu[i]);

                if (i == N - 1) break;
                Console.Write(" ");
            }
            Console.WriteLine();
            
        }
    }
}



Measured memory_bytes: 13140
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;
//#include "atcoder/all"

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

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

    vector<string> ss(n);
    rep(i, n) cin >> ss[i];

    {
        int now = 0;
        for (string &s: ss) {
            for (char c : s) {
                if (c == '(') now++;
                else now--;
            }
        }
        if (now != 0) {
            cout << "No" << endl;
            ret();
        }
    }

    vector<string> up, down;

    auto is_up = [&](string &s) -> bool {
        int now = 0;
        for (char c : s) {
            if (c == '(') now++;
            else now--;
        }
        return now >= 0;
    };

    for (string &s:ss) if (is_up(s)) up.push_back(s); else down.push_back(s);

    struct Index {
        int index, low;
    };

    auto calc_up_low = [&](string &s) -> int {
        int now = 0;
        int mi = 0;

        for (char c : s) {
            if (c == '(') now++;
            else now--;
            cmin(mi, now);
        }
        return mi;
    };

    auto calc_down_low = [&](string &s) -> int {
        int now = 0;
        int mi = 0;

        for (int i = s.size() - 1; i >= 0; i--) {
            char c = s[i];
            if (c == ')') now++;
            else now--;
            cmin(mi, now);
        }
        return mi;
    };

    vector<Index> up_indexes, down_indexes;
    rep(i, up.size()) up_indexes.push_back({i, calc_up_low(up[i])});
    rep(i, down.size()) down_indexes.push_back({i, calc_down_low(down[i])});

    sort(up_indexes.begin(), up_indexes.end(), [](Index i1, Index i2) { return i1.low > i2.low; });
    sort(down_indexes.begin(), down_indexes.end(), [](Index i1, Index i2) { return i1.low < i2.low; });

    vector<string> tmp;
    for (Index i: up_indexes) tmp.push_back(up[i.index]);
    for (Index i: down_indexes)tmp.push_back(down[i.index]);

    auto check = [](vector<string> &v) -> bool {
        int now = 0;
        int mi = 0;
        for (string &s: v) {
            for (char c : s) {
                if (c == '(') now++;
                else now--;
                cmin(mi, now);
            }
        }
        return mi >= 0;
    };

    bool ok = check(tmp);
    cout << (ok ? "Yes" : "No") << endl;

}


Measured memory_bytes: 122548
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

struct P{
  int h,w;
  P(int h,int w):h(h),w(w){}
};

bool operator <(const P& a,const P& b){
  return a.h*a.w < b.h*b.w;
}
  
vector<P> cut(vector<P> c,int p,int s){
  P tar = c[p];
  int d = s%(tar.h+tar.w);
  vector<P> ret;

  for(int i=0;i<c.size();++i)
    if(i!=p) ret.push_back(c[i]);
  if(d<tar.w){ //cut vertical
    P c1 = P(tar.h, d);
    P c2 = P(tar.h, tar.w-d);
    if(c2 < c1) swap(c1,c2);
    ret.push_back(c1);
    ret.push_back(c2);
  }
  else{ //cut horizontal
    d-=tar.w;
    P c1 = P(d, tar.w);
    P c2 = P(tar.h-d, tar.w);
    if(c2 < c1) swap(c1,c2);
    ret.push_back(c1);
    ret.push_back(c2);
  }
  return ret;
}

int main(){
  int n,W,H;
  while(cin>>n>>W>>H,n||W||H){
    vector<P> S;
    S.push_back(P(H,W));
    for(int i=0;i<n;++i){
      int p,s;
      cin >> p >> s;
      p--;
      S = cut(S,p,s);
    }
    sort(S.begin(),S.end());
    for(int i=0;i<S.size()-1;++i)
      cout << S[i].h*S[i].w << " ";
    cout << S[n].h*S[n].w<<endl;
  }
  return 0;
}

Measured memory_bytes: 1204
use std::io::{Read, stdin};
use std::str::FromStr;

fn main() {
    let n: usize = read();
    let mut t: Vec<i64> = Vec::new();
    let mut sum_t: i64 = 0;
    for i in 0..n {
        t.push(read());
        sum_t += t[i];
    }

    let m: usize = read();
    let mut p: Vec<i64> = Vec::new();
    let mut x: Vec<i64> = Vec::new();
    for _i in 0..m {
        p.push(read());
        x.push(read());
    }
    for i in 0..m {
        println!("{}", sum_t - t[(p[i] - 1) as usize] + x[i]);
    }
}


fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

int inf = 1e9;
int dp[200010];
vector<int> from[200010];
int fromc[200010];
set<int> st[26];
bool ok[200010];
int main(){
	string s;
	cin>>s;
	int N = s.size();
	rep1(i,N+1) fromc[i] = 26;

	rep(i,N){
		st[s[i]-'a'].insert(i);
	}
	rep(i,26) st[i].insert(N);

	rep1(i,N+1) dp[i] = inf;
	rep(i,N+1){
		rep(c,26){
			int nxt = *st[c].lower_bound(i);
			int j = nxt+1;
			if(dp[j]>dp[i]+1){
				dp[j] = dp[i]+1;
				from[j] = {i};
			}else if(dp[j] == dp[i]+1){
				from[j].pb(i);
			}
		}
	}

	ok[N+1] = 1;
	for(int i = N;i>=0; i--){
		rep(c,26){
			int nxt = *st[c].lower_bound(i);
			int j = nxt+1;
			if(dp[j] == dp[i]+1 && ok[j]) ok[i] = 1;
		}
	}

	string ans;

	for(int i=0;i!=N+1;){
		rep(c,26){
			int nxt = *st[c].lower_bound(i);
			int j = nxt+1;
			if(dp[j] == dp[i]+1 && ok[j]){
				i = j;
				ans += 'a'+c;
				break;
			}
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 34308
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub
from fractions import gcd

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


# @mt
def slv(N, M, A):
    b = []
    for a in A:
        c = 0
        while a % 2 == 0:
            c += 1
            a //= 2
        b.append(c)
    if not all(map(lambda x: x==b[0], b)):
        return 0

    d = reduce(lambda x, y: x * y//gcd(x, y), A)
    ans = 0
    if M - d//2 >= 0:
        ans = (M-d//2) // d
    if d // 2 <= M:
        ans += 1

    return ans

def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M, A))

if __name__ == '__main__':
    main()


Measured memory_bytes: 16628
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main() {
    int n, T; cin >> n >> T;
    vector<pair<int, int> > A;
    vector<int> B;
    while (n--) {
        int x, y; cin >> x >> y;
        if (x > 0) A.push_back({x, y});
        else B.push_back(y+1);
    }
    sort(A.begin(), A.end(), [](pair<int, int> lhs, pair<int, int> rhs) {
            return (long long)rhs.first * (lhs.second + 1)
                < (long long)lhs.first * (rhs.second + 1);
        });
    sort(B.begin(), B.end());
    const int K = 35;
    vector<int> dp(K, T+1);
    dp[0] = 0;
    for (auto [a, b] : A) {
        for (int k = K-2; k >= 0; k--) {
            if (dp[k] > T) continue;
            long long arr = dp[k] + 1, wait = a * arr + b;
            if (arr + wait < dp[k+1]) dp[k+1] = arr + wait;
        }
    }
    for (int j = 1; j < int(B.size()); j++)
        B[j] = min(T+1, B[j-1] + B[j]);
    int j = B.size() - 1, ans = 0;
    for (int k = 0; k < K; k++) {
        if (dp[k] > T) break;
        while (j >= 0 && B[j] + dp[k] > T) j--;
        ans = max(ans, j + 1 + k);
    }
    cout << ans << endl;
}


Measured memory_bytes: 4880
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
typedef long long ll;

int main(){
    int n,k; cin>>n>>k;
    int ans = 0;
    while(n>0){
        n /= k;
        ans++;
    }
    cout << ans <<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstddef>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <set>
#define L64 long long
#define UL64 unsigned long long
#define MOD (1000000007LL)

using namespace std;

const string g_male = "Male";
const string g_female = "Female";
const string g_vacant = "Vacant";

int main(void)
{
    int n;
    cin >> n;
    cout << 0 << endl;
    string a;
    cin >> a;
    if (a == g_vacant) {
        return 0;
    }
    int mid = n / 2;
    cout << mid << endl;
    string b;
    cin >> b;
    if (b == g_vacant) {
        return 0;
    }
    int left = 0;
    int right = n;
    bool left_is_male = true;

    if (mid % 2 == 0) {
        if (a == b) {
            left = mid;
            left_is_male = b == g_male;
        }
        else {
            right = mid;
            left_is_male = a == g_male;
        }
    }
    else {
        if (a == b) {
            right = mid;
            left_is_male = a == g_male;
        }
        else {
            left = mid;
            left_is_male = b == g_male;
        }
    }
    while (true) {
        mid = (left + right) / 2;
        cout << mid << endl;
        string c;
        cin >> c;
        if (c == g_vacant) {
            return 0;
        }
        bool mid_is_male = c == g_male;
        if ((mid - left) % 2 == 0) {
            if (left_is_male == mid_is_male) {
                left = mid;
            }
            else {
                right = mid;
            }
        }
        else {
            if (left_is_male == mid_is_male) {
                right = mid;
            }
            else {
                left = mid;
                left_is_male = mid_is_male;
            }
        }
    }

    return 0;
}


Measured memory_bytes: 852
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5, mod = 1e9 + 7;
int main()
{
    string s;
    cin >> s;
    int cnt = 0;
    for (int i = 0; i < s.size(); ++i){
        if (s[i] == 'o') ++cnt;
    }
    if (cnt + (15 - s.size()) >= 8) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main()
{
    char arr[105];
    scanf("%s", arr);
    for(int i = 0; arr[i] != '\0'; i++)
    {
        if(arr[i] == ',')
        {
            printf(" ");
        }
        else
        {
            printf("%c", arr[i]);
        }
    }
    puts("");
    return 0;
}

Measured memory_bytes: 1652
#include<stdio.h>
#include<math.h>
#define MAX 200000

int main(){
  int R[MAX],n,i;
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d",&R[i]);

  int maxv=-INFINITY;
  int minv=R[0];

  for(i=1;i<n;i++){
    if(maxv<R[i]-minv)maxv=R[i]-minv;

    if(minv>R[i])minv=R[i];
  }
  printf("%d\n",maxv);
  return 0;
}


Measured memory_bytes: 2580
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <map>
#include <set>

using namespace std;

int a, b, c;

inline void ok(int & x)
{
    if (x < a + c || x > b - c) cout << x << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> a >> b >> c;
    for (int i = a; i <= b; i++)
        ok(i);
}


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


int main() {
  int n,m; cin >> n >> m;
  int ans =0;
  ans += n*(n-1)/2;
  ans += m*(m-1)/2;
  cout << ans << endl;
  return 0;

}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int TopIndex = 1;
const int DummySize = 1;

void Exchange(vector<int>& Heap, int InsertIndex)
{
	int ParentIndex = InsertIndex / 2;
	while(InsertIndex > TopIndex && Heap[InsertIndex] > Heap[ParentIndex]){
		swap(Heap[InsertIndex], Heap[ParentIndex]);
		InsertIndex = ParentIndex;
		ParentIndex = InsertIndex / 2;
	}
}

void Insert(vector<int>& Heap, int k)
{
	Heap.push_back(k);
	int InsertIndex = Heap.size() - 1;
	Exchange(Heap, InsertIndex);
}

void maxHeapify(vector<int>& A, int i)
{
	int H = A.size() - 1;
	int l = 2 * i;
	int r = 2 * i + 1;
	//????????????????????????????????§???????????§????????????????????¶
	int largest;
	if(l <= H && A[l] > A[i]){
		largest = l;
	}else{
		largest = i;
	}
	if(r <= H && A[r] > A[largest]){
		largest = r;
	}
	//i???????????????????????§????????´???
	if(largest != i){
		swap(A[i], A[largest]);
		//?????°??????????????????
		maxHeapify(A, largest);
	}
}

void ExtractMax(vector<int>& Heap)
{
	int TailIndex = Heap.size() - 1;
	cout << Heap[TopIndex] << endl;
	swap(Heap[TailIndex], Heap[TopIndex]);
	Heap.pop_back();
	maxHeapify(Heap, TopIndex);
}

int main()
{
	vector<int> Heap(DummySize);
	while(true){
		string Command;
		cin >> Command;
		if(Command == "insert"){
			int k;
			cin >> k;
			Insert(Heap, k);
		}else if(Command == "extract"){
			ExtractMax(Heap);
		}else{
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 7040
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) { a = b; return true;}
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) { a = b; return true;}
    return false;
}
int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;cin>>n;
    ll gsb[2][3];
    bool flg[3] = {};
    rep(i,2) {
        rep(j,3) {
            cin>>gsb[i][j];
        }
    }
    rep(i,3) {
        flg[i] = gsb[0][i] < gsb[1][i];
    }
    ll res = 0;
    if (flg[0]==flg[1]&&flg[1]==flg[2]) {
        int from = flg[0] ? 0 : 1;
        int to = 1-from;
        rep(i,n+1) {
            rep(j,n-i+1) {
                ll tmp = 0;
                tmp += i % gsb[from][0] + i / gsb[from][0] * gsb[to][0];
                tmp += j % gsb[from][1] + j / gsb[from][1] * gsb[to][1];
                tmp += (n-i-j) % gsb[from][2] + (n-j-i) / gsb[from][2] * gsb[to][2];
                chmax(res, tmp);
            }
        }
    } else {
        vector<int> ab, ba;
        rep(i,3) {
            if(flg[i]) ab.push_back(i);
            else ba.push_back(i);
        }
        ll tmp = 0;
        if (ab.size()==2) {
            DEBUG{
                cout << "pattern2" << endl;
            }
            rep(i,n+1) {
                ll tmp2 = 0;
                tmp2 += i % gsb[0][ab[0]] + i / gsb[0][ab[0]] * gsb[1][ab[0]];
                tmp2 += (n-i) % gsb[0][ab[1]] +  (n-i) / gsb[0][ab[1]] * gsb[1][ab[1]];
                chmax(tmp, tmp2);
            }
            res = tmp % gsb[1][ba[0]] + tmp / gsb[1][ba[0]] * gsb[0][ba[0]];
        } else {
            DEBUG{
                cout << "pattern3" << endl;
            }
            tmp = n % gsb[0][ab[0]] + n / gsb[0][ab[0]] * gsb[1][ab[0]];
            rep(i,tmp+1) {
                ll tmp2 = 0;
                tmp2 += i % gsb[1][ba[0]] + i / gsb[1][ba[0]] * gsb[0][ba[0]];
                tmp2 += (tmp-i) % gsb[1][ba[1]] +  (tmp-i) / gsb[1][ba[1]] * gsb[0][ba[1]];
                chmax(res, tmp2);
            }
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N;
int A[1000005];
int ans[1000005];

int main() {
  ios_base::sync_with_stdio(false);
  cin >> N;
  for(int i = 1; i <= N; i++)
    cin >> A[i];
  long long s = 0;
  for(int i = 1; i <= N; i++)
    s += A[i] * (i % 2 ? 1 : -1);
  ans[1] = s;
  for(int i = 2; i <= N; i++) {
    ans[i] = (A[i - 1] - ans[i - 1] / 2) * 2;
  }
  for(int i = 1; i <= N; i++)
    cout << ans[i] << " ";
}


Measured memory_bytes: 5888
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sca = new Scanner(System.in);
		int n = sca.nextInt();
		String s = sca.next();
		int[] r = new int[4001];
		int r_index = 1;
		int[] g = new int[4001];;
		int g_index = 1;
		int[] b = new int[4001];;
		int b_index = 1;
		for(int i = 0; i < s.length(); i++) {
			if(s.charAt(i) == 'R') {
				r[r_index] = i+1;
				r_index++;
			}
			else if(s.charAt(i) == 'G') {
				g[g_index] = i+1;
				g_index++;
			}
			else {
				b[b_index] = i+1;
				b_index++;
			}
		}
		int[] h = new int[3];
		long max = (long)((r_index - 1))*(g_index - 1)*(b_index - 1);
		for(int i = 1; i < r_index; i++) {
			for(int j = 1; j < g_index; j++) {
				int big;
				int small;
				if(r[i] > g[j]) {
					big = r[i];
					small = g[j];
				}
				else {
					big = g[j];
					small = r[i];
				}
				if(big - small + big <= s.length()) {
					if(s.charAt(big - small + big - 1) == 'B') {
						max--;
					}
				}
				if((small + big) % 2 == 0 && s.charAt((small + big)/2 - 1) == 'B') {
					max--;
				}
				if(small - (big - small) > 0) {
					if(s.charAt(small - (big - small) - 1) == 'B') {
						max--;
					}
				}
			}
		}

		System.out.println(max);

		// 後始末
		sca.close();
	}
}

Measured memory_bytes: 37644
#include<bits/stdc++.h>
using namespace std;
int n,ans;
int sg(int x,int y){
	int u=x/y;x=u*y+(x+y)%(u+1);
	if(x==u*y)return u;else return sg(x-u-1,y);
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){int x,y;cin>>x>>y;ans^=sg(x,y);}
	cout<<(ans?"Takahashi\n":"Aoki\n");
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;


int main(){
  ll n;  cin >> n;
  string s; cin >> s;

  map<char, ll> key;
  for(ll i=0; i<n; i++){
    key[s[i]] += 1;
  }
  ll sum = 1;
  for(auto x: key){
    sum *= (x.second+1);
    sum %= MOD;
  }
  cout << sum-1<< endl;
}


Measured memory_bytes: 512
//In the name of He
#include <bits/stdc++.h>
#define pb push_back
#define X first
#define Y second
const bool DEBUG = false;
#define cerr if(DEBUG)cerr
#define bit(num,i) ((num>>i)&1)

using namespace std;

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

const long long maxn = 3e5 + 5 + 1;
const long long INF = 4e18 ;
const long long M = 1e9 + 7;
const int lg = 21;

#pragma GCC Optimize("Ofast")

string n;
int ans;

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    ans = (n.size()-1)*9;
    ans += (n[0]-='0');
    for(int i=1;i<n.size();i++){
        if(n[i]!='9') {
            ans--;
            break;
        }
    }
    cout << ans;
	return 0;
}


Measured memory_bytes: 256
MOD=10**9+7
def facinv(N):
    fac,finv,inv=[0]*(N+1),[0]*(N+1),[0]*(N+1)
    fac[0]=1;fac[1]=1;finv[0]=1;finv[1]=1;inv[1]=1
    for i in range(2,N+1):
        fac[i]=fac[i-1]*i%MOD
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        finv[i]=finv[i-1]*inv[i]%MOD
    return fac,finv,inv

def COM(n,r):
    if n<r or r<0:
        return 0
    else:
        return ((fac[n]*finv[r])%MOD*finv[n-r])%MOD
        
r1,c1,r2,c2=map(int,input().split())

fac,finv,inv=facinv(r2+c2+1)

ans=0

for i in range(r1,r2+1):
    ans=(ans+COM(c2+i+1,i+1)-COM(c1+i,i+1)+MOD)%MOD
print(ans)

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

int main(void){
     int A,B;
     cin>>A>>B;
    
     if(A<=5){
         cout<<0<<endl;
     }else if(A<=12){
         cout<<B/2<<endl;
     }else{
         cout<<B<<endl;
     }


    return 0;
}

Measured memory_bytes: 256
from itertools import accumulate
N,K = [int(x) for x in input().split()]
p =[0]+[int(x) for x in input().split()]
pa = list(accumulate(p))
an = 0
ans = 0
for i in range(N-K+1):
  if an<pa[i+K]-pa[i]:
    an = max(an,pa[i+K]-pa[i])
    ans = 0
    for l in range(K):
      ans += (p[l+i+1]+1)/2
print(ans)

Measured memory_bytes: 77704