akhauriyash/Code-Regression huggingface dataset:
n, m = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(m)]
N = [None] * n
for s, c in L:
    if N[s - 1] is None:
        N[s - 1] = c
    elif N[s - 1] == c:
        continue
    else:
        print(-1)
        exit()

if n == 1:
    if N[0] is None:
        N[0] = 0
    print(*N)
    exit()
elif N[0] == 0:
    print(-1)
    exit()

for i in range(n):
    if i == 0 and N[0] is None:
        N[0] = 1
    elif N[i] is None:
        N[i] = 0
print(*N, sep='')



Measured memory_bytes: 3064
n,a,b = map(int, input().split())
MOD = 10**9+7
 
def cmb(n,r):
    a,b = 1,1
    for i in range(r):
        a = a * (n-i) % MOD
        b = b * (i+1) % MOD
    return a * pow(b, MOD-2, MOD)%MOD
 
print((pow(2,n,MOD) - cmb(n,a) - cmb(n,b) - 1)%MOD)

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

int main() {
  string S, T;
  cin >> S >> T;
  for (int i = S.size() - T.size(); 0 <= i; i--) {
    string S2 = S;
    bool matched = true;
    for (int j = 0; j < T.size(); j++) {
      if (S[i+j] != '?' && S[i+j] != T[j]) {
        matched = false;
        break;
      }
      else S2[i+j] = T[j];
    }
    if (matched) {
      for (char c : S2) cout << (c == '?' ? 'a' : c);
      cout << endl;
      return 0;
    }
  }
  cout << "UNRESTORABLE" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>//
#define ll long long
using namespace std;
int main()
{
    ll n,m;
    cin>>m>>n;
    if(m>=n){
        for(ll i=1;i<=m;i++)
        cout<<n;
    }
    else{
        for(ll i=1;i<=n;i++)
        cout<<m;

    }
        cout<<endl;


    return 0;
}







Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))

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

llint n, a[3];
string s[100005];
string ans;
bool dp[100005][3][3][3];
int pre[100005][3][3][3];

llint get(string s)
{
	if(s == "AB") return 0;
	if(s == "BC") return 1;
	if(s == "AC") return 2;
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	llint sum = 0;
	for(int i = 0; i < 3; i++) cin >> a[i], sum += a[i];
	for(int i = 1; i <= n; i++) cin >> s[i];
	
	if(sum == 2){
		dp[0][a[0]][a[1]][a[2]] = true;
		for(int i = 0; i < n; i++){
			llint x = get(s[i+1]), y = (x+1)%3;
			for(int j = 0; j < 3; j++){
				for(int k = 0; k < 3; k++){
					for(int l = 0; l < 3; l++){
						if(!dp[i][j][k][l]) continue;
						llint b[] = {j, k, l};
						if(b[x] > 0){
							b[x]--, b[y]++;
							dp[i+1][b[0]][b[1]][b[2]] = true;
							pre[i+1][b[0]][b[1]][b[2]] = y;
							b[x]++, b[y]--;
						}
						if(b[y] > 0){
							b[y]--, b[x]++;
							dp[i+1][b[0]][b[1]][b[2]] = true;
							pre[i+1][b[0]][b[1]][b[2]] = x;
							b[y]++, b[x]--;
						}
					}
				}
			}
		}
		
		for(int j = 0; j < 3; j++){
			for(int k = 0; k < 3; k++){
				for(int l = 0; l < 3; l++){
					if(dp[n][j][k][l]){
						a[0] = j, a[1] = k, a[2] = l;
						goto end;
					}
				}
			}
		}
		cout << "No" << endl;
		return 0;
		end:;
		
		for(int i = n; i >= 1; i--){
			llint x = get(s[i]),  y = (x+1)%3, p = pre[i][a[0]][a[1]][a[2]], q;
			q = x;
			if(p == x) q = y;
			ans += "ABC"[p];
			a[p]--, a[q]++;
		}
		reverse(ans.begin(), ans.end());
	}
	else{
		for(int i = 1; i <= n; i++){
			llint x = get(s[i]), y = (x+1)%3, p, q;
			if(a[x] >= 2) p = x;
			else if(a[y] >= 2) p = y;
			else if(a[x] == 1) p = x;
			else if(a[y] == 1) p = y;
			else{
				cout << "No" << endl;
				return 0;
			}
			q = x;
			if(p == x) q = y;
			
			a[p]--, a[q]++;
			ans += "ABC"[q];
		}
	}
	
	cout << "Yes" << endl;
	for(int i = 0; i < ans.size(); i++) cout << ans[i] << endl;
	
	return 0;
}

Measured memory_bytes: 20096
#include <queue>
#include <cstdio>
#include <iostream>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <time.h>
#include <functional>

//#include "All.h"

using namespace std;
typedef long long int ll;

#define EPS (1e-9)
#define INF (1e9)
#define PI (acos(-1))
#define REP(i,n) for(int i=0;i<n;i++)

int gcd(int a, int b) {
    if (a < b) swap(a, b);
    if (b == 0) return a;
    return gcd(b, a % b);
}

ll beki(ll a, ll b) {
    ll tmp = 1;
    REP(i, b) tmp *= a;
    return tmp;
}

int K, A, B;

int main() {
    cin >> K >> A >> B;
    REP(i, B - A + 1) {
        if ((A + i) % K == 0) {
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;
}


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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){
while(x->left!=NIL)
x=x->left;
return x;
}

Node treeMaximum(Node x){
while(x->right!=NIL)
x=x->right;
return x;

}

Node treeSearch(Node u, int k){
while (u != NIL && k != u->key)
if (k < u->key)
u = u->left;
else
u= u->right;
return u;

}

Node treeSuccessor(Node x){
	Node y;
if (x->right != NIL)
return treeMinimum(x->right); // case 1
y = x->parent;
while (y != NIL && x == y->right) {
x = y;
y = y->parent;
}
return y; // case 2

}


void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL) {
  	y=x;
  	if(z->key < x->key) x = x->left;
  	else x = x->right;
  }
  	z->parent = y;
  	
  if (y == NIL) root =z;
  
  else if (z->key < y->key) y->left = z;

else y->right = z;



}

void inorder(Node u){
if(u==NIL) return;
inorder(u->left);
printf(" %d",u->key);
inorder(u->right);

}
void preorder(Node u){
if(u==NIL) return;
printf(" %d",u->key);
preorder(u->left);
preorder(u->right);

}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } 
  }

  return 0;
}



Measured memory_bytes: 25156
// -----------------------------------------------
// Framework <https://github.com/vain0x/procon>
//
// See the bottom of file for solution.
// -----------------------------------------------

#![allow(unused_imports)]
#![allow(non_snake_case)]

use std::cell::RefCell;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Display, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), stderr());
            writeln!(err, "\x1B[33m{}\x1B[0m = {:?}", e, $e).unwrap()
        })*
    };
}

#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

#[allow(dead_code)]
fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.trim_right().to_owned()
}

// -----------------------------------------------
// Solution
// -----------------------------------------------

fn main() {
    let mut X = read![[i64]];
    X.sort();
    println!("{}", X[0] * X[1] / 2)
}


Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <algorithm> 
#include <cstdlib>
#include <vector>
using namespace std;
int main(){
    string s;
    cin >> s;
    long long k,count=0;
    cin >> k;
    for(int i=0;i<s.size();i++){
        if(s[i]=='1'){
            count++;
        }else{
            if(k<=count){
                cout << 1 << endl;
                return 0;
            }else{
                cout << s[count] << endl;
                return 0;
            }
        }
    }
    cout << 1 << endl;
}


Measured memory_bytes: 384
def stdinput():
    from sys import stdin
    return stdin.readline().strip()

def main():
    from itertools import combinations
    n = int(stdinput())
    *A, = map(int, stdinput().split(' '))
    q = int(stdinput())
    *M, = map(int, stdinput().split(' '))

    all_canditee = set([sum(c) for i in range(1, n+1) for c in combinations(A, i)])

    # print(A)
    # print(all_canditee)

    for m in M:
        if m in all_canditee:
            print('yes')
        else:
            print('no')

# can not pass 9/10
def check(m, a, A):
    for i, next_a in enumerate(A):
        this_a = a + next_a
        if this_a == m:
            return True
        elif this_a < m:
            if check(m, this_a, A[i+1:]):
                return True
    return False

if __name__ == '__main__':
    main()
    # import cProfile
    # cProfile.run('main()')


Measured memory_bytes: 43048
#include <bits/stdc++.h>
using namespace std;
    
int main() {
    int N;
    cin>>N;
    vector<int> a(N);
    for (int i=0;i<N;i++) cin>>a.at(i);
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    
    int Alice = 0;
    int Bob = 0;
    for (int i=0;i<N;i++) {
        if (i%2==0) Alice += a.at(i);
        else Bob += a.at(i);
    }
    
    cout << Alice - Bob << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	try {
    		final String S = sc.next();
    		StringBuilder sb = new StringBuilder(S);
    		final String SR = sb.reverse().toString();

    		int count = 0;
    		for (int i=0; i<S.length()/2; i++) {
    			if (S.charAt(i) != SR.charAt(i)) {
    				count++;
    			}
    		}

    		System.out.println(count);

    	} finally {
    		sc.close();
    	}
    }
}


Measured memory_bytes: 24276
def calcs(x,y,ax,ay,bx,by) ((ax-x)*(by-y)-(bx-x)*(ay-y))/2.0 end
def inpf() a=gets.chomp.split(" ").map(&:to_f)end
def inps() a=gets.chomp.split(" ")end  
def copy(a) Marshal.load(Marshal.dump(a)) end
def factorial(n)(n < 2)? 1 : (2..n).inject(:*) end
def scount(a) b=na(a.max+1);a.each{|n|b[n]+=1};return b end
def na(n,d=0) Array.new(n,d)end
def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end
def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end
def bit(n) n.to_s(2).split("").map(&:to_i) end
def inp() a=gets.chomp.split(" ").map(&:to_i)end
n = inp[0]
a = []
tab = na(5)
n.times do 
  s = gets
  case s[0]
    when "M" then
      tab[0] += 1
    when "A" then
      tab[1] += 1
    when "R" then
      tab[2] += 1
    when "C" then
      tab[3] += 1
    when "H" then
      tab[4] += 1
  end
end
ans = 0
c = 0
i = 0
5.times do |i|
   ((i+1)...5).each do |j| 
    ((j+1)...5).each do |k|
      ans += tab[i]*tab[k]*tab[j]
    end
  end
end
p ans

Measured memory_bytes: 4092
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    vector<bool> chk(n,false);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    int cnt=0;
    int nx=0;
    int nw=0;
    int ans;
    while(cnt <= n+1){
        nw = nx;
        if(nw==1) break;
        nx = a[nw]-1;
        if(chk[nw]==true){
            ans = -1;
            break;
        }else{
            chk[nw] = true;
        }
        cnt++;
        ans = cnt;
        //cout << "nw " << nw << " nx " << nx << endl;
    }
    cout << ans << endl;


}



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

using namespace std;

int main() {
    int X, Y, Z, K; cin >> X >> Y >> Z >> K;
    vector<long long> A(X), B(Y), C(Z);
    for(int i = 0; i < X; i++) {
        cin >> A[i];
    }
    for(int i = 0; i < Y; i++) {
        cin >> B[i];
    }
    for(int i = 0; i < Z; i++) {
        cin >> C[i];
    }

    vector<long long> D(X*Y);   
    for(int i = 0; i < X; i++) {
        for(int j = 0; j < Y; j++) {
            D.push_back(A[i]+B[j]);
        }
    }
    sort(D.begin(), D.end(), greater<long long>());

    vector<long long> E(Z); 
    for(int i = 0; i < K; i++) {
        for(int j = 0; j < Z; j++) {
            E.push_back(D[i]+C[j]);
        }
    }
    sort(E.begin(), E.end(), greater<long long>());

    for(int i = 0; i < K; i++) {
        cout << E[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 57908
def main():
    N = int(input())
    c = [[int(i) for i in input().split()] for j in range(N)]
    edges = []
    for i in range(N):
        for j in range(i+1, N):
            if c[i][j] != -1:
                edges.append((c[i][j], (i, j)))
    edges.sort()

    par = [i for i in range(N)]
    rank = [0 for i in range(N)]

    def find_root(x):
        if par[x] == x:
            return x
        else:
            par[x] = find_root(par[x])
            return par[x]

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    ans = 0
    for c, e in edges:
        if find_root(e[0]) != find_root(e[1]):
            unite(e[0], e[1])
            ans += c
    print(ans)


if __name__ == '__main__':
    main()



Measured memory_bytes: 6404
import java.util.Scanner;

public class Main {
  public static void main (String[] args){
  
   int N,reverse=0,remaind,tmp;
  
   Scanner sc = new Scanner (System.in);
   N=sc.nextInt();
   tmp=N;
   while(tmp!=0)
   {
     remaind = tmp%10; //一桁ずつ取り出す
     reverse = reverse *10 + remaind; //数値反転
     tmp/=10; //次の桁へシフト
   }
   if(reverse==N){
     System.out.println("Yes");
   }
   else{
     System.out.println("No");
   }
  }
}

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

using namespace std;

int main() {
  int n;
  scanf("%d", &n);
  vector<bool> p(60000);
  for (int i = 2; i <= 55555; i++) {
    p[i] = true;
  }
  for (int i = 2; i * i <= 55555; i++) {
    if (!p[i]) {
      continue;
    }
    for (int j = i * i; j <= 55555; j += i) {
      p[j] = false;
    }
  }
  int cc = 0;
  for (int i = 2; cc < n; i++) {
    if (p[i] && i % 5 == 1) {
      printf("%d%c", i, " \n"[cc == n - 1]);
      cc++;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
using ll = long long;
int main(){
  ll n,k;
  cin >> n >> k;

  if(n >= k){
    n = n-k*(n/k);
  }

  ll prev = n;
  n = abs(k-n);

  ll ans = min(prev,n);

  cout << ans << endl;
}


Measured memory_bytes: 256
import java.io.*;
public class Main {
    public static void main(String args[]){
        BufferedReader reader = new BufferedReader (new InputStreamReader(System.in));
        String line;
        int x;

        try {
            line = reader.readLine();
            x = Integer.parseInt(line);
            System.out.println(x*x*x);
        } catch (NumberFormatException e) {
            System.out.println(e);
        } catch (IOException e) {
            System.out.println(e);
        }
    }
}


Measured memory_bytes: 24172
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define INF 10000000001
#define DIM 200001
#define mod 1000000007
#define PI 3.1415926535897932384626433
#define se second
#define fi first
#define pb push_back
#define T true
#define F false
#define endl "\n"
typedef char ch;
typedef bool boll;
typedef string st;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef set < string > sst;
typedef set < long long > sl;
typedef queue < long long > que;
typedef vector < long long > vec;
typedef map < long long, long long > mll;
typedef pair < long long, long long > pll;
typedef vector < pair < long long, long long > > vpl;
typedef pair < long long, unsigned long long > pul;
ll t,n,z,x,s;
sl ss;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x,ss.insert(x);
    if(ss.size()==n)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;

}


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

int main() {

int N;cin>>N;
  vector<int> a(N);
	for(int i=0; i<N; i++){
      cin>>a.at(i);}
  
  sort(a.begin(),a.end());
  cout<<a.at(N-1)-a.at(0)<<endl;
}



Measured memory_bytes: 256
#include <iostream>

#define int long long

using namespace std;

const int N = 2e5 + 10;

int32_t main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    
    int x;
    cin >> x;
    cout << x + x * x + x * x * x;
    return 0;
}

Measured memory_bytes: 3636
#include<stdio.h>
int main(){
    char S[3], b[]="ABC", i=0;
    scanf("%s", S);
    for(i=0; i<3; i++)
    {
        if(S[i]!=b[i])
            break;
    }
    if(i==3)
        printf("ARC");
    else
        printf("ABC");
    return 0;
}

Measured memory_bytes: 1704
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
typedef boost::multiprecision::cpp_int ll;
int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        if (A[i] == 0) {
            puts("0");
            return 0;
        }
    }
    ll x = 1;
    ll y = 1'000'000'000'000'000'000LL;
    for (int i = 0; i < N; i++) {
        x *= A[i];
        if (x > y) {
            puts("-1");
            return 0;
        }
    }
    cout << x << endl;
}

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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

ll N, M, Q;
struct Data {
    ll a, b, c, d;
};

Data D[55];

ll t = 0;

ll dfs(vector<ll> v) {
    t++;
    if (v.size() == N) {
        ll score = 0;
        REP(i, Q) {
            if (v[D[i].b] - v[D[i].a] == D[i].c)
                score += D[i].d;
        }
        return score;
    }
    ll m = 1;
    if (v.size() > 0)
        m = v[v.size() - 1];

    ll ret = 0;
    FOR(n, M + 1, m) {
        v.push_back(n);
        ret = std::max(ret, dfs(v));
        v.pop_back();
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M >> Q;
    REP(i, Q) {
        cin >> D[i].a >> D[i].b >> D[i].c >> D[i].d;
        D[i].a--;
        D[i].b--;
    }

    vector<ll> v;
    ll ans = dfs(v);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3620
import java.io.*;
import java.util.*;
import java.util.function.*;

final class Solver {
	static final Solver INSTANCE = new Solver();

	void solve(Supplier<String> sc) {
		int K = Integer.parseInt(sc.get());
		String S = sc.get();
		var sub = S.substring(0, Math.min(K, S.length()));
		System.out.println(sub.equals(S) ? S : sub + "...");
	}
}

class Main {
	public static void main(String... args) {
		System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		var reader = new BufferedReader(new InputStreamReader(System.in));
		Solver.INSTANCE.solve(new Supplier<>() {
			StringTokenizer line;

			public String get() {
				while (line == null || !line.hasMoreTokens()) try {
					line = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
				return line.nextToken();
			}
		});
		System.out.flush();
	}
}

Measured memory_bytes: 36364
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace B
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var N = int.Parse(Console.ReadLine());
            var A = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
            var min = 1001;
            var max = 0;
            for (var i = 0; i < A.Length; i++)
            {
                max = Math.Max(max, A[i]);
                min = Math.Min(min, A[i]);
            }
            Console.WriteLine(max - min);
        }
    }
}


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

#define max(a, b) a > b ? a : b
#define min(a, b) a < b ? a:b

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

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

    for (j = 1; j < n; j++){
    maxv = max(maxv, R[j]-minv);
    minv = min(minv, R[j]);
    }

    printf("%d\n", maxv);

    return 0;
}


Measured memory_bytes: 2576
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int a;
    string s;
    cin>>s;
    string t[7]={"SUN","MON","TUE","WED","THU","FRI","SAT"};
    for(int i=0;i<7;i++){
        if(t[i]==s){a=i;break;}
    }
    cout<<7-a;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(void)
{
  int n,i,point_Taro=0,point_Hana=0;
  char Taro[100],Hana[100];
  scanf("%d",&n);
  for(i=0;i<n;i++)
  {
    scanf("%s %s",Taro,Hana);
    if ( strcmp(Taro,Hana) == 0 )
    {
      point_Taro++; point_Hana++;
    }
    else if ( strcmp(Taro,Hana) > 0 ) point_Taro+=3;
    else point_Hana+=3;
  }
  printf("%d %d\n",point_Taro,point_Hana);
  return 0;
}



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

struct tr{
	char f;
	char t;
};

int main(){
	vector<tr> trs;
	tr t;
	int n,m,l,f;
	while(cin>>n,n){
		while(n--){
			cin >> t.f >> t.t;
			trs.push_back(t);
		}
		cin>>m;
		while(m--){
			f=0;
			cin >> t.f;
			for(l=0;l<trs.size();l++){
				if(t.f==trs[l].f){
					cout<<trs[l].t;
					f=1;
					break;
				}
			}
			if(!f)cout << t.f;
		}
		cout << endl;
		trs.clear();
	}
	return 0;
}

Measured memory_bytes: 3008
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);    
    
	 long long n,i,j,k,sum=0,count=0,ans=0,x,y,l,r,m;
     string s;
     cin>>s;
     n=s.length();
      if(s=="ABC")
      cout<<"ARC";else
      cout<<"ABC";
}

Measured memory_bytes: 3620
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)

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


Measured memory_bytes: 3856
function Main(stdin){
stdin = stdin.trim().split("\n").reverse();
stdout = [];
function input(){return stdin.pop()};
function print(x){stdout.push(x)};


var n = parseInt(input());
var v = input().split(" ").map(n=>parseInt(n));
var c = input().split(" ").map(n=>parseInt(n));
var ans = 0;
for (i=0; i < n; i++){
    ans += Math.max(0, v[i]-c[i])
}
print(ans);


stdout = stdout.join("\n");
console.log(stdout);
return stdout
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"))

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

#define FOR(s, i, n) for(int i = s; i n; i++)
typedef long long ll;
const ll INF = 1e18;
struct Edge{
	int to;
	ll fee; ll time;
};
struct PT{
	int u;
	ll coin;
	ll time;
};
bool operator<(PT a, PT b){
	vector<ll> at = {a.time, a.coin, a.u};
	vector<ll> bt = {b.time, b.coin, b.u};
	return at < bt;
}
const int MAXC = 3000;
int main(){
	// ios::sync_with_stdio(false);
	// cin.tie(NULL);
	
	int n, m;
	int sCoin;
	cin>>n>>m>>sCoin;
	sCoin = min(sCoin, MAXC-1);
	vector<vector<Edge>> adj(n, vector<Edge>());
	vector<int> coin(n);
	vector<int> time(n);
	for(int i = 0; i < m; i++){
		int u, v, a, b;
		cin>>u>>v>>a>>b; u--; v--;
		adj[u].push_back({v, a, b});
		adj[v].push_back({u, a, b});
	}
	for(int i = 0; i < n; i++){
		cin>>coin[i]>>time[i];
	}
	set<PT> s;
	s.insert({0, sCoin, 0});
	vector<vector<ll>> dist(n, vector<ll>(MAXC, -1));
	while(!s.empty()){
		PT pt = *s.begin();
		s.erase(s.begin());	
		// printf("u: %d coin:%lld time:%lld ;\n", pt.u+1, pt.coin, pt.time);
		if(dist[pt.u][pt.coin] == -1){
			dist[pt.u][pt.coin] = pt.time;
			for(auto e: adj[pt.u]){
				if(e.fee <= pt.coin){
					s.insert({e.to, pt.coin-e.fee, pt.time+e.time});
				}
			}
			if(pt.coin+coin[pt.u]<MAXC){
				s.insert({pt.u, pt.coin+coin[pt.u], pt.time + time[pt.u]});
			}
			// cout<<'\t';
			// for(auto it: s){
			// 	cout<<it.u+1<<';'<<it.coin<<';'<<it.time<<"  ";
			// }
			// cout<<'\n';
		}
	}
	vector<ll> ans(n, INF);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < MAXC; j++){
			// cout<<dist[i][j]<<' ';
			ans[i] = min(ans[i], dist[i][j]);
		}
		// cout<<'\n';
	}
	for(int i = 1; i < n; i++)
		cout<<ans[i]<<'\n';
	return 0;
}

Measured memory_bytes: 24228
//by Himanshu Shukla
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long
#define v32 vector<int>
#define v64 vector<ll>
#define s32 set<int>
#define s64 set<ll>
#define graph vector<s32>
#define p32 pair<int,int>
#define p64 pair<ll,ll>
#define fi first
#define se second
#define ln '\n'
#define debug(x) cout << (#x) << ": " << (x) << ln
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline ll add(ll a, ll b, ll m) { return (((a % m + b % m) % m + m) % m); }
inline ll mul(ll a, ll b, ll m) { return (((a % m * b % m) % m + m) % m); }
const double EPS = 1e-6;
const ll MOD = 1e9 + 7;
template <typename T, typename U>
ostream& operator<<(ostream& out, const pair<T,U>& p){
	out << '[' << p.fi << ", " << p.se << ']';
	return out;
}
template <template <typename, typename...> class ContainerType, typename ValueType, typename ...Args>
void print_container(const ContainerType<ValueType, Args...>& c){
	cout << "{ ";
	for(const auto& v : c)
		cout << v << ' ';
	cout << '}' << ln;
}

ll arr[20];

ll solve(int lo,int hi,ll c1,ll c2)
{
	if(lo + 1 == hi)
		return 0;
	ll ans = 1e18;
	for(int i = lo + 1;i < hi;i++)
		ans = min(ans,solve(lo,i,c1,c1 + c2) + solve(i,hi,c1 + c2,c2) + (c1 + c2) * arr[i]);
	return ans;
}

int main()
{
	FASTIO;
	int n;
	cin >> n;
	for(int i = 0;i < n;i++)
		cin >> arr[i];
	cout << (arr[0] + arr[n - 1] + solve(0,n - 1,1,1)) << ln;
	return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in);) {
            new Main().solve(sc);
        }
    }

    void solve(Scanner sc) {
        int n = sc.nextInt();
        int ans = 0;
        int[] points = new int[n];
        for (int i = 0; i < n; i++) {
            points[i] = sc.nextInt();
            ans += points[i];
        }

        Arrays.sort(points);
        for (int i = 0; i < n && ans % 10 == 0; i++) {
            if (points[i] % 10 != 0) {
                ans -= points[i];
            }
        }
        System.out.println(ans % 10 == 0 ? 0 : ans);
    }
}


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

string a, b;

int main() {
	cin>>a>>b;
	int x[30], y[30];
	memset(x, -1, sizeof(x));
	memset(y, -1, sizeof(y));
	for(int i = 0;i<a.length();i++){
		int u = a[i] - 'a';
		int v = b[i] - 'a';
		if(x[u] == -1 && y[v] == -1){
			x[u] = v, y[v] = u;
		}
		else if(x[u] == -1){
			cout<<"No";
			return 0;
		}
		else if(y[v] == -1){
			cout<<"No";
			return 0;
		}
		else if(x[u] != v || y[v] != u){
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes";
	return 0;
}

Measured memory_bytes: 776
# include<bits/stdc++.h>
using namespace std;
const int MAX=2e5+1;
struct p{
	int x,L;
}c[MAX],d[MAX];
int n;
int a[MAX],b[MAX];
bool look(int mid)
{
	int num1=0,num2=0,A1=0,A0=0,L0=0,L1=0,T1,T0;
	for(int i=1;i<2*n;++i)
	  if(a[i]>=mid) b[i]=1,++A1;
	  else b[i]=0,++A0;
	for(int i=1;i<2*n;++i)
	  if(!b[i])
	  {
	  	L1=0,++L0;
	  	if(L0==1) T0=i;
	  	if(L0==2) d[++num2].x=T0;
	  	if(L0>1) d[num2].L=L0;
	  }
	  else
	  {
	  	L0=0,++L1;
	  	if(L1==1) T1=i;
	  	if(L1==2) c[++num1].x=T1;
	  	if(L1>1) c[num1].L=L1;
	  }
	if(!num1&&!num2) return A1>A0;
	int minn=1e9;
	for(int i=1;i<=num1;++i)
	  if(minn>min(abs(c[i].x-n),abs(c[i].x+c[i].L-n-1))) minn=min(abs(c[i].x-n),abs(c[i].x+c[i].L-n-1));
	for(int i=1;i<=num2;++i)
	  if(minn>min(abs(d[i].x-n),abs(d[i].x+d[i].L-n-1))) return 0;
	return 1;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<2*n;++i)
	  scanf("%d",&a[i]);
	int l=1,r=n*2-1,ans;
	while(l<=r)
	{
		int mid(l+r>>1);
		if(look(mid)) l=mid+1,ans=mid;
		else r=mid-1;
	}
	return printf("%d",ans),0;
}

Measured memory_bytes: 4096
#include <vector>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<n;i++)
#define SORT(c) sort((c).begin(),(c).end())
#define ALL(a) (a).begin(),(a).end()

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

  string s, t;
  cin >> s >> t;
  vector<string> S;
  int ss = s.size(), ts = t.size();
  int n = ss - ts + 1;
  for (int i = 0; i < n; i++) {
      string x = s;
      bool f = true;
      for (int j = 0; j < ts; j++) {
        if(!(x[i+j] == '?' || x[i+j] == t[j])) {
          f = false;
        }
      }
      if(f){
          for (int j = 0; j < ts; j++) x[i+j] = t[j];
          replace(x.begin(), x.end(), '?', 'a');
          S.push_back(x);
      }
  }
  if(!S.size()){
      cout << "UNRESTORABLE" << endl;
      return 0;
  }
  string ans = S[0];
  for (int i = 1; i < S.size() ; i++) {
      if(ans > S[i]) ans = S[i];
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
n = input()
s = input()
count = 0
max_l = 0
max_r = 0

for c in s:
    if c =="(":
        count -= 1
    else:
        count += 1
    max_l = max(max_l, count)
count = 0
for c in s[::-1]:
    if c =="(":
        count += 1
    else:
        count -= 1
    max_r = max(max_r, count)

print("("*max_l + s + ")"*max_r)

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

int main() {
  int N;
  cin >> N;
  string S;
  int A,W,T,R;
  A=0;
  W=0;
  T=0;
  R=0;
  
  
  for(int i= 0;i<N;i++){
    cin >> S;
    
    if(S=="AC"){
      A +=1;
    }
    else if(S=="WA"){
      W +=1;
    }
    else if(S=="TLE"){
      T +=1;
    }
    else{
      R+=1;
    }
    
  }
  
  cout<< "AC x  " <<A <<endl;
  cout<< "WA x " <<W <<endl;
  cout<< "TLE x " << T <<endl;
  cout<<"RE x " <<R <<endl;
      
    
  
}

Measured memory_bytes: 3628
# abc110_d


def solve(H, W, matrix):
    ugoki = []

    for i in range(H):
        for j in range(W - 1):
            if matrix[i][j] % 2 == 1:
                matrix[i][j] -= 1
                matrix[i][j + 1] += 1
                ugoki.append((i + 1, j + 1, i + 1, j + 2))

    j = W - 1
    for i in range(H - 1):
        if matrix[i][j] % 2 == 1:
            matrix[i][j] -= 1
            matrix[i + 1][j] += 1
            ugoki.append((i + 1, j + 1, i + 2, j + 1))

    return ugoki


if __name__ == "__main__":
    H, W = map(int, input().split(" "))
    matrix = [list(map(int, input().split(" "))) for i in range(H)]
    ugoki = solve(H, W, matrix)
    print(len(ugoki))
    for mov in ugoki:
        print("{} {} {} {}".format(mov[0], mov[1], mov[2], mov[3]))


Measured memory_bytes: 26300
#include<bits/stdc++.h>
using namespace std;
#define intt long long int
#define intu unsigned long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
//#define mp make_pair
#define ff first
#define ss second
#define fast_io ios::sync_with_stdio(0);cin.tie(NULL);std::cout.tie(NULL);
# define PI           3.14159265358979323846 
#define all(a) a.begin(),a.end()
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define bloop(i,a,b) for (int i = a ; i>=b;i--)
#define tc(t) int t; cin >> t; while (t--)
int mod = 1000000007;
intt gcd(intt a, intt b) {return b ? gcd(b, a % b) : a;}
intt lcm(intt a, intt b) {return a * b / gcd(a, b); }
intt bpow(intt a,intt b) 
{
  intt res = 1;
  while (b > 0) {
    if (b & 1)res = ((res%mod) * (a%mod))%mod;
      a = ((a%mod) * (a%mod))%mod;
      b >>= 1;
  }
  return res;
}
intt fact(intt n) { 
   if ((n==0)||(n==1))
      return 1; 
   else
      return n*fact(n-1);
}
void go()
{
#ifndef ONLINE_JUDGE
  freopen("inn.txt","r",stdin);
  freopen("o.txt","w",stdout);
  #endif
}


int main()
{
	go();
	int n,d;cin>>n>>d;
	
	int ans=0;
	for0(i,n){
		long long int a,b;cin>>a>>b;
		if((sqrt(a*a+b*b))<=d)
			ans++;
	}
	cout << ans;

}

Measured memory_bytes: 3680
#include <stdio.h>

int main() {
	int n;
	scanf("%d", &n);
	
	char arr[n];
	scanf("%s", &arr);
	
	int x = 0;
	int max = 0;
	for(int i = 0; i < n; i++) {
		if(arr[i] == 'I') {
			x++;
			if(max < x) {
				max = x;
			}
		}
		else if(arr[i] == 'D') {
			x--;
		}
	}
	
	printf("%d\n", max);
	return 0;
}

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

bool find(std::vector<int> v, int i){
    bool found = (std::find(v.begin(), v.end(), i) != v.end());
    return found;
}

std::vector<int> copyVector(std::vector<int> v){
    std::vector<int> newV;
    for (int i=0; i<v.size(); i++){
        newV.push_back(v[i]);
    }
    return newV;
}

int main(){
    int N, M;
    cin >> N >> M;
    int a[M];
    int b[M];
    for (int i=0; i<M; i++){
        cin >> a[i] >> b[i];
    }

    std::queue<std::vector<int>> que;
    std::vector<int> init{1};
    que.push(init);
    int counter = 0;
    while (!que.empty()){
        std::vector<int> now;
        now = que.front();
        que.pop();
        if (now.size()==N){
            counter++;
            continue;
        }
        for (int i=0; i<M; i++){
            if (a[i] == now.back()){
                if (!find(now, b[i])){
                    std::vector<int> newV = copyVector(now);
                    newV.push_back(b[i]);
                    que.push(newV);
                }
            }
            if (b[i] == now.back()){
                if (!find(now, a[i])){
                    std::vector<int> newV = copyVector(now);
                    newV.push_back(a[i]);
                    que.push(newV);
                }
            }
        }

    }
    cout << counter << endl;
}

Measured memory_bytes: 640
#include <iostream>
using namespace std;
string s;
int main()
{
	cin>>s;
	int len=s.length();
	long long ans;
	long long ano=0;
		ans = 9*(len-1);
		ans+=s[0]-'0'-1;
	for(int i=0;i<len;i++)
	{
		ano+=s[i]-'0';
	}
	cout<<max(ans,ano);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long LL;
typedef long double ld;
typedef vector<ll>VI;
typedef pair<ll,ll>P;
#define VV(T) vector<vector<T>>
#define sz(x) int(x.size())
#define PI 3.1415926535897932384626433832795
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define ALL(a)  (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define c_max(a, b) (((ll)a)>((ll)b)?(a):(b))
#define c_min(a,b) (((ll)a)<((ll)b)?(a):(b))
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 vmax(v) *max_element(ALL(v))
#define vmin(v) *min_element(ALL(v))
#define $(x) {cout<<#x<<" = " <<(x)<<endl;}
#define fi first
#define se second
#define MAX 100100//5
#define MAX2 200100
#define MAX6 1001001//6
#define MAX7 10010010//7
#define SENTINEL 2000000000//9
const int MOD = 1000000007;
#define INF 1<<30
#define INFTY 1LL<<61
#define MAX_INT INT_MAX
#define Endl '\n'
#define CLR(mat) memset(mat, 0, sizeof(mat))
inline ll GCD(ll a,ll b){return b?GCD(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/GCD(a,b);}
template<class T> bool contain(const std::string& s, const T& v) {
   return s.find(v) != std::string::npos;
}
using Edge=pair<int,ll>;
using Graph=vector<vector<ll> >;//ll or Edge
//const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
// sort_reverse -> greater<long long>()
// vector型から重複を削除 list.erase(unique(ALL(list)),list.end());
// g++ -o a a.cpp -Wall -lm -std=c++17
//push_back -> emplace_back

int main(){
   ll n;cin>>n;
   VI a(n);
   rep(i,n)cin>>a[i];
   VI cnt(3,0);
   ll ans=1;
   rep(i,n){
      int mul=0;
      rep(j,3){
         if(cnt[j]==a[i]){
            mul++;
         }
      }
      rep(j,3){
         if(cnt[j]==a[i]){
            cnt[j]++;
            break;
         }
      }
      ans=(ans*mul)%MOD;
   }
   cout<<ans<<endl;
}

Measured memory_bytes: 4040
import sys

x, y, z, k = map(int, sys.stdin.readline().split())

xlist = sorted(list([int(i)
                     for i in sys.stdin.readline().split()]), reverse=True)[:min(x, k)]
ylist = sorted(list([int(i)
                     for i in sys.stdin.readline().split()]), reverse=True)[:min(y, k)]
zlist = sorted(list([int(i)
                     for i in sys.stdin.readline().split()]), reverse=True)[:min(z, k)]


anslist = [0]
for i in range(min(x, k)):
    for j in range(min(y, k)):
        for l in range(min(z, k)):
            if (i+1)*(j+1)*(l+1) <= k:
                anslist.append(xlist[i] + ylist[j] + zlist[l])
            else:
                break

anslist = sorted(anslist, reverse=True)
for i in range(k):
    print(anslist[i])


Measured memory_bytes: 9524
#include <stdio.h>

int main(void)
{
	int i,n,j,sa[7];
	for (i=0;i<7;i++){
		scanf("%d %d",&n,&j);
		sa[i]=n-j;
	}
	for (i=0;i<=6;i++){
		printf("%d\n",sa[i]);
	}
	return 0;
}


Measured memory_bytes: 2112
def bubbleSort(n, a)
	s = a.map{|i| i.delete("^0-9").to_i}
	flag = 1
	while flag==1 do
		flag = 0
		i = 0
		(n-1).downto(i+1) do |j|
			if s[j].to_i<s[j-1].to_i then
				v = s[j];s[j] = s[j-1];s[j-1] = v
				v = a[j];a[j] = a[j-1];a[j-1] = v
				flag = 1
			end
		end
		i += 1
	end
	return a
end

def selectionSort(n, a)
	s = a.map{|i| i.delete("^0-9").to_i}
	0.upto(n-1) do |i|
		minj = i
		i.upto(n-1) do |j|
			minj = j if s[j].to_i<s[minj].to_i
		end
		v = s[i];s[i] = s[minj];s[minj] = v
		v = a[i];a[i] = a[minj];a[minj] = v
	end
	return a
end

n = gets.to_i
a = gets.split.map(&:to_s)
a1, a2 = Array.new
a1 = a.dup
a2 = a.dup
s1 = bubbleSort(n, a1)
s2 = selectionSort(n, a2)
puts s1.join(' ')
puts "Stable"
puts s2.join(' ')
puts (s1 == s2) ? "Stable" : "Not stable"


Measured memory_bytes: 6884
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int n = s.size();

    bool check = true;
    int left = 0,right = n-1;
    while(left<=right)
    {
        if(s[left]==s[right])
        {
            left++;
            right--;
        }
        else
        {
            check=false;
            break;
        }
    }
    if(check)
    {
        int left = 0,right  = max(0,(n-1)/2 -1);
        bool game=true;
    while(left<=right)
    {
        if(s[left]==s[right])
        {
            left++;
            right--;

        }
        else
        {
            game=false;
            break;
        }
    }
    if(!game)
        cout<<"No\n";
    else
    {
        left = min(n-1,(n+3)/2-1);
        right = n-1;
        while(left<=right)
        {
            if(s[left]==s[right])
                {
                    left++;
                    right--;
                }
                else
                {
                    game=false;
                    break;
                }
        }
        if(!game)
            cout<<"No\n";
        else
            cout<<"Yes\n";

    }
    }
    else
        cout<<"No\n";


}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <boost/rational.hpp>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (int64_t)(n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  rep(i, N) { cin >> a[i]; }
  sort(a.begin(), a.end());

  int64_t result = 0;
  if (N % 2 == 0) {
    result += a[N / 2] - a[N / 2 - 1];
    rep(i, N / 2 - 1) { result += 2 * (a[N / 2 + i + 1] - a[i]); }
  } else {
    int64_t cand1 = a[N / 2] + a[N / 2 + 1];
    int64_t cand2 = -a[N / 2] - a[N / 2 - 1];

    rep(i, N / 2 - 1) {
      cand1 += 2 * a[N - 1 - i];
      cand2 -= 2 * a[i];
    }
    rep(i, N / 2) {
      cand1 -= 2 * a[i];
      cand2 += 2 * a[N - 1 - i];
    }
    result = max(cand1, cand2);
  }
  cout << result << endl;

  return 0;
}


Measured memory_bytes: 3760
s = input()
t = input()


def match(k):
    for i in range(len(t)):
        if t[i] != s[i + k] and s[i + k] != "?":
            return False
    return True


def construct(k):
    ans = list(s)
    for i in range(len(t)):
        ans[k + i] = t[i]
    for i in range(len(s)):
        if ans[i] == "?":
            ans[i] = "a"
    return "".join(ans)


K = len(s) - len(t) + 1

pw_candid = []

for i in range(K):
    if match(i):
        pw_candid.append(construct(i))
        # print(construct(i))
        # sys.exit()
if len(pw_candid):
    print(sorted(pw_candid)[0])
else:
    print("UNRESTORABLE")


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include<atcoder/all>
// Begin Header {{{
using namespace atcoder;
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i,n) for(ll i=0; i<n; i++)
#define loop(i, j, n) for(ll i=j; i<n; i++)
#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define Sp(p) cout<<setprecision(25)<< fixed<<p<<endl;
constexpr int INF  = 0x3f3f3f3f;
const long long mod=1e9+7;
const long double PI = acos(-1);
template<class T, class S> inline bool chmax(T &a, const S &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T, class S> inline bool chmin(T &a, const S &b) { if (a>b) { a = b; return 1; } return 0; }
#define INT(...)                                                                                                                                               \
    int __VA_ARGS__;                                                                                                                                           \
    IN(__VA_ARGS__)
#define LL(...)                                                                                                                                                \
    ll __VA_ARGS__;                                                                                                                                            \
    IN(__VA_ARGS__)
#define STR(...)                                                                                                                                               \
    string __VA_ARGS__;                                                                                                                                        \
    IN(__VA_ARGS__)
#define CHR(...)                                                                                                                                               \
    char __VA_ARGS__;                                                                                                                                          \
    IN(__VA_ARGS__)
#define DBL(...)                                                                                                                                               \
    double __VA_ARGS__;                                                                                                                                        \
    IN(__VA_ARGS__)
template<class T> void scan(T &a) { cin >> a; }
void IN() {}
template<class Head, class... Tail> void IN(Head &head, Tail &... tail){ scan(head); IN(tail...); }
// }}} End Header

int main() {
	LL(N, M);
	dsu d(N);
	rep(i,M){
		LL(a, b);
		a--; b--;
		d.merge(a, b);
	}
	ll ans = d.groups().size();
	cout << ans-1 << endl;
	return 0;
}


Measured memory_bytes: 8856
//#include "pch.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <limits.h>
#include <string>
#include <cmath>

using namespace std;

#define rip(i, n, s) for (int i = (s);i < (int)( n ); i++)
#define mp make_pair
#define all(a) (a).begin(), (a).end()
typedef long long ll;

ll cal(int &base, int &i, int &j, int &k, int &l){
    return (ll) base*(i + j + k + l) + j + k * 2 + l * 3;
}

int main(){
    int n;
    ll W;
    cin >> n >> W;
    vector<vector<int>> da(4,vector<int>(1,0));
    int base;
    cin >> base;
    int w,v;
    cin >> v;
    da[0].push_back(v);
    rip(i, n - 1 ,0){
        cin >> w >> v;
        da[w-base].push_back(v);
    }
    rip(i,4,0){
        sort(++(da[i].begin()),da[i].end());
        reverse(++(da[i].begin()),da[i].end());
    }
    vector<int> su(4,0);
    int ans = 0;
    rip(i,da[0].size(),0){
        su[0] += da[0][i];
        su[1]  = su[0];
        rip(j,da[1].size(),0){
            su[1] += da[1][j];
            su[2] = su[1];
            rip(k,da[2].size(),0){
                su[2] += da[2][k];
                su[3] = su[2];
                rip(l,da[3].size(),0){
                    su[3] += da[3][l];
                    if(cal(base,i,j,k,l) <= W){
                        //cout << su[3] << endl;
                        ans = max(ans, su[3]);
                    }
                }
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int32_t main()
{
	FIO;
	int a, b, c, d; cin >> a >> b >> c >> d;

	int mx = max({(a * c), (a * d), (b * c), (b * d)});
	cout << mx << '\n';
	return 0;
}

Measured memory_bytes: 3632