akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,s,f) for(i=s;i<f;i++)
#define print(v) for(auto &z:v) cout<<z<<' ';cout<<'\n'
#define db cout<<"db: "
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define B begin()
#define E end()
#define all(v) v.B,v.E
#define sz(v) (int)((v).size())
#define vi vector<int>
#define vii vector<pair<int,int>>
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define clk1 clock_t start_time=clock()
#define clk2 cout<<(clock()-start_time)/(double)CLOCKS_PER_SEC
#define clean(arr) memset(arr,0,sizeof(arr))
// #define mod 1000000007
#define mod 998244353
#define space 100005
//<<fixed << setprecision(9)



ll EE(ll a, ll b, ll *x, ll *y)
{
    if (a == 0) 
    { 
        *x = 0, *y = 1; 
        return b; 
    } 
  
    ll x1, y1;
    ll gcd = EE(b%a, a, &x1, &y1); 
  
    *x = y1 - (b/a) * x1; 
    *y = x1; 
  
    return gcd; 
}

ll inverse(ll a, ll m)
{
    ll x,y;
    EE(a,m,&x,&y);
    if(x<0) x += m;
    return x;
}

int main()
{
    int n,i,j,t;
    boost;

    ll p = inverse(2,mod);

    int s;
    cin>>n>>s;
    int arr[n];
    rep(i,0,n)cin>>arr[i];

    int two[n+1];
    two[0]=1;
    rep(i,1,n+1)
    {
        two[i] = (two[i-1]*2)%mod;
    }


    ll dp[n][s+1];
    clean(dp);
    dp[0][0]=two[n];
    if(arr[0]<=s) 
    {
        dp[0][arr[0]]=two[n-1];
    }
    rep(i,1,n)
    {
        rep(j,0,s+1)
        {
            dp[i][j]=dp[i-1][j];

            if(arr[i]<=j)
            {
                dp[i][j] +=  dp[i-1][j-arr[i]] * p  ;
                dp[i][j]%=mod;
            }
        }
    }

    cout<<dp[n-1][s];

    return 0;
}



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

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

  string s;
  cin >> s;
  set<int> d;
  for (size_t i = 0; i < s.size(); ++i) {
    d.insert(s[i]);
  }
  if (d.size() == 3) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }
}


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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] p = new int[n];
        for(int i=0; i<n; i++) {
            p[i] = sc.nextInt();
        }

        Arrays.sort(p);
        int sum = 0;
        for(int i=0; i<k; i++) {
            sum += p[i];
        }
        System.out.println(sum);
    }
}

Measured memory_bytes: 38844
#include<iostream>

using namespace std;

int main(){
  int sx,sy,tx,ty;
  string s;
  cin >> sx >> sy >> tx >> ty;

  for(int i = 0 ; i < ty - sy ; i++){
    s += 'U';
  }
  for(int i = 0 ; i < tx - sx ; i++){
    s += 'R';
  }

  for(int i = 0 ; i < ty - sy ; i++){
    s += 'D';
  }
  for(int i = 0 ; i < tx - sx ; i++){
    s += 'L';
  }

  s += 'L';
  for(int i = 0 ; i < ty - sy + 1 ; i++){
    s += 'U';
  }
  for(int i = 0 ; i < tx - sx + 1 ; i++){
    s += 'R';
  }
  s += 'D';

  s += 'R';
  for(int i = 0 ; i < ty - sy + 1 ; i++){
    s += 'D';
  }
  for(int i = 0 ; i < tx - sx + 1 ; i++){
    s += 'L';
  }
  s += 'U';

  cout << s << endl;
}


Measured memory_bytes: 256
def main():
    n , a , b , c , d = map(int,input().split())
    dic = {}
    def f(x):
        if x == 0:
            return 0
        elif x == 1:
            return d
        elif x in dic: #メモ化
            return dic[x]
        t1 = d*x                           #愚直に引いていく 
        t2 = d*(x%2)     + a + f(x//2)     #下げて2で割る
        t3 = d*(2-(x%2)) + a + f(-(-x//2)) #上げて2で割る
        t4 = d*(x%3)     + b + f(x//3)     #下げて3で割る
        t5 = d*(3-(x%3)) + b + f(-(-x//3)) #上げて3で割る
        t6 = d*(x%5)     + c + f(x//5)     #下げて5で割る
        t7 = d*(5-(x%5)) + c + f(-(-x//5)) #上げて5で割る
        t = min(t1,t2,t3,t4,t5,t6,t7) #どの操作が最小？
        dic[x] = t #メモ化
        return t
    print(f(n))
    return
    
t = int(input())
for i in range(t):
    main()

Measured memory_bytes: 20068
#include "bits/stdc++.h"
using namespace std;
const int mod = 1e9 + 7;
void add_self(int& a, int b) {
    a += b;
    if(a >= mod) {
        a -= mod;
    }
}
int can[22][22];
int dp[1<<21];
int main() {
    int n;
    scanf("%d", &n);

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            scanf("%d", &can[i][j]);
        }
    }

    dp[0] = 1;

    for(int mask = 0; mask < (1 << n) - 1; ++mask) {
        int a = __builtin_popcount(mask);
        for(int b = 0; b < n; ++b) {
            if(can[a][b] && !(mask & (1 << b))) {
                int m2 = mask ^ (1 << b);
                add_self(dp[m2], dp[mask]);
            }
        }
    }

    printf("%d\n", dp[(1<<n)-1]);
}


Measured memory_bytes: 8448
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define SORT(a) sort(a.begin(),a.end())
 
int main() {
	
	//string ans="";
	//vector<int> c(30,0);
	int a1,a2,b1,b2;
	
	cin >> a1 >> a2 >> b1 >> b2;
	
	if(b2==1){
		 cout << 1 << endl;
		 return 0;
	}
	

	
    cout << 0 << endl;
    
    return 0;

}

Measured memory_bytes: 256
N = int(input())
A = [int(input()) for _ in range(N)]

A_max = max(A)
A_copy = A.copy()
A_copy.remove(A_max)
A_max_second = max(A_copy)

for a in A:
    if a != A_max:
        print(A_max)
    else:
        print(A_max_second)


Measured memory_bytes: 14076
/*Whose woods these are I think I know.
His house is in the village though;
He will not see me stopping here
To watch his woods fill up with snow.

My little horse must think it queer
To stop without a farmhouse near
Between the woods and frozen lake
The darkest evening of the year.

He gives his harness bells a shake
To ask if there is some mistake.
The only other sound’s the sweep
Of easy wind and downy flake.

The woods are lovely, dark and deep,
But I have promises to keep,
And miles to go before I sleep,
And miles to go before I sleep.*/

#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007
const int maxn= 100010;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n=0,m=0,q=0;
    cin>>n>>m>>q;
    vector<int> v(m-1+n);
    for(int i=m-1;i<m-1+n;++i)
        v[i]=1;
    vector<int> a(q),b(q),c(q),d(q);
    for(int i=0;i<q;++i)
    {
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        --a[i];--b[i];
    }
    vector<int> aux(n);
    int res=0;
    do{
        int temp=0,pos=0;
        for(auto i:v)
        {
            if(!i)
                ++temp;
            else
                aux[pos++]=temp;
        }
        int sum=0;
        for(int i=0;i<q;++i)
        {
            if(aux[b[i]]-aux[a[i]]==c[i])
                sum+=d[i];
        }
        res=max(res,sum);
    }while(next_permutation(v.begin(),v.end()));
    cout<<res<<endl;
}

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> city(N);
  for (int i=0; i<M; i++) {
    int a, b;
    cin >> a >> b;
    city.at(a-1) += 1;
    city.at(b-1) += 1;
  }
  for (int i=0; i<N; i++) {
    cout << city.at(i) << endl;
  }
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=1000000007ll;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int n;
ll a[252525], f[252525];
ll k;

bool is_ok(ll mid){
  ll cnt=0;
  REP(i, n){
    if(a[n-1-i]*f[i]<=mid) continue;
    ll tmp=mid/f[i];
    cnt+=a[n-1-i]-tmp;
  }
  return cnt<=k;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	// cout<<setprecision(10)<<fixed;
  cin>>n>>k;
  REP(i, n){
    cin>>a[i];
  }
  REP(i, n){
    cin>>f[i];
  }
  sort(a, a+n);
  sort(f, f+n);
  ll lb=-1, ub=1e15;
  while(ub-lb>1){
    ll mid=(ub+lb)/2;
    if(is_ok(mid)){
      ub=mid;
    }
    else{
      lb=mid;
    }
  }
  cout<<ub<<'\n';
	return 0;
}


Measured memory_bytes: 3456
#include<iostream>
using namespace std;
int main(){
	int n,a,b,ct =0;
	scanf("%d %d %d",&n,&a,&b);
	for(int i = 0;i<n;i++){
		int c;
		scanf("%d",&c);
		if(c <a || c>=b){
			ct++;
		}
	}
	printf("%d\n",ct);
	return 0;
}

Measured memory_bytes: 256
object Main extends App {
	val pw = new java.io.PrintWriter(System.out)

	@scala.annotation.tailrec
	def loop(start: Int, end: Int)(f: Int => Unit): Unit =
		if (start < end) {
			f(start)
			loop(start + 1, end)(f)
		}

	val x = Math.abs(Scanner.nextLong)
	val k, d = Scanner.nextLong

	pw.println(
		if (k < x / d) x - k * d
		else if ((k - x / d) % 2 == 0) x % d
		else Math.abs(x % d - d)
	)

	pw.flush()
}

object Scanner {
	private val buf = new Array[Byte](1024); private var ptr = 0; private var len = 0

	@inline private def isPrintableChar(c: Int): Boolean = 33 <= c && c <= 126
	@inline private def hasNextByte(): Boolean = if (ptr >= len) { ptr = 0; len = System.in.read(buf); len > 0 } else true
	@inline private def hasNext(): Boolean = {
		while (hasNextByte() && !isPrintableChar(buf(ptr))) ptr += 1
		hasNextByte()
	}
	@inline private def readByte(): Byte = if (hasNextByte()) { val res = buf(ptr); ptr += 1; res } else -1

	def next(): String = {
		if(!hasNext()) ???
		val sb = new StringBuilder; var b = readByte()
		while (isPrintableChar(b)) { sb.append(b.toChar); b = readByte() }
		sb.toString
	}

	def nextInt(): Int = {
		val n = nextLong()
		if (n < Int.MinValue || Int.MaxValue < n) ???
		n.toInt
	}

	def nextLong(): Long = {
		if(!hasNext()) ???
		var minus = false; var b = readByte()
		if (b == '-') { minus = true; b = readByte() }

		@scala.annotation.tailrec
		def go (b: Byte, n: Long = 0): Long = if ('0' <= b && b <= '9') go(readByte(), n * 10 + b - '0') else if (minus) -n else n

		go(b)
	}

	def nextDouble(): Double = next().toDouble
}


Measured memory_bytes: 54508
import java.util.AbstractMap.SimpleEntry;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		try(Scanner sc = new Scanner(System.in)) {
			int n = sc.nextInt();
			PriorityQueue<SimpleEntry<Integer, Integer>> queue = new PriorityQueue<>((e1, e2) -> {
				return Integer.compare(e1.getValue(), e2.getValue());
			});
			for(int i = 0 ; i < n ; i++) {
				queue.add(new SimpleEntry<Integer, Integer>(sc.nextInt(), sc.nextInt()));
			}
			SimpleEntry<Integer, Integer> entry;
			int current = 0;
			while((entry = queue.poll()) != null) {
				if(current + entry.getKey() > entry.getValue()) {
					System.out.println("No");
					System.exit(0);
				} else {
					current += entry.getKey();
				}
			}
			System.out.println("Yes");
		}

	}

}


Measured memory_bytes: 117132
#include <bits/stdc++.h>
#include <math.h>
#include <float.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
 
const ll INF = 1LL<<62;
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; }
// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

const int MOD = 1000000007;

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

    bool isOK = false;
    for(int i = 1; i <=B; i++){
        int t = A*i;
        if (t % B == C){
            isOK = true;
        }
    }

    if (isOK) cout << "YES" << endl;
    else cout << "NO" << endl;
}

Measured memory_bytes: 3468
N = int(input())
A = list(map(int, input().split())) 
sum = 0

for i in range(A[0],A[1]+1):
    if i % N ==0:
        sum =1
if A[0] == A[1]:
    if A[0] % N ==0:
        print("OK")
    else:
        print("NG")
else:
    if sum == 0:
        print("NG")
    else:
        print("OK")

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int K;

int dist[111111];
signed main(){
    fill_n(dist,111111,INT_MAX);
    cin>>K;

    dist[0]=0;
    priority_queue<pint,vector<pint>,greater<pint>>que;
    que.push({0,0});
    int ans=INT_MAX;
    while(que.size()){
        int c,v;
        tie(c,v)=que.top();
        que.pop();
        for(int i=0;i<10;i++){
            int tmp=i*K+v;
            int nc=c+tmp%10;
            int nv=tmp/10;
            if((v||i)&&nv==0)chmin(ans,nc);
            if(dist[nv]<=nc)continue;
            dist[nv]=nc;
            que.push({nc,nv});
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 6512
#include <stdio.h>

long gcd(long a,long b){
  if(b == 0) return a;
  else return gcd(b,a%b);
}

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

   long ans,a;
   scanf("%ld",&ans);
   for(int i = 0;i < N-1;i++){
      scanf("%ld",&a);
      ans = gcd(a,ans);
   }

   printf("%ld\n",ans);

  return 0;
}

Measured memory_bytes: 128
#include <iostream>

using namespace std;

constexpr long long BASE = 1000000000;
int main()
{
	int n;
	cin >> n;
	long long res = 1;
	for (int i = 0; i < n; i++)
	{
		long long temp;
		cin >> temp;
		if (res == -1 && temp != 0)
			continue;
		if (temp == 0)
		{
			res = 0;
			continue;
		}
		long long a1 = res / BASE;
		long long b1 = res % BASE;
		long long a2 = temp / BASE;
		long long b2 = temp % BASE;
		long long temp1 = ((a1 * b2 + a2 * b1) % BASE) * BASE + b1 * b2;
		long long c1 = a1 * a2 + (a1 * b2 + a2 * b1) / BASE + temp1 / BASE / BASE;
		long long c2 = temp1 % (BASE * BASE);
		if (c1 > 1 || (c1 == 1 && c2 > 0))
			res = -1;
		else
			res *= temp;
	}
	cout << res << endl;
}

Measured memory_bytes: 3636
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(A: int, B: int, C: int):
    ret = NO
    if A <= C <= B:
        ret = YES
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    solve(A, B, C)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#1600_入学試験
#1行目：（m, nmin, nmax) [(データ個数, 合格者最小人数, 合格者最大人数)]
#合格者数 n は nmin 人以上，nmax 人以下とする． n はこの範囲内でギャップを最大とするものでなくてはいけない． 
#ギャップとは合格者の最低点と不合格者の最高点の差
#同じギャップになる n が複数あるときは，その中で n が最大になるように選ぶ．


while True :

  m, nmin, nmax = map(int,input().split())
  #もしm=0ならbreak
  if m == 0:
    break
  else:
    #配列n[i]を読み込む(1<=i<=n)
    n = [int(input()) for i in range(m)]
    
    gap = 0
    cnt = 0
    
    for i in range(nmax, nmin-1,-1) :
      #iのときのギャップを求める
      if (abs(n[i]- n[i-1])) > gap :
        
        gap =  abs(n[i] - n[i-1])
        cnt = i
        
        
        
    
    print(cnt)
   
      
      


Measured memory_bytes: 5624
import heapq

N, M = map(int, input().split())
A = [-i for i in list(map(int, input().split()))]
heapq.heapify(A)
for m in range(M):
    A_max = -heapq.heappop(A)  # Aの最大値を削除して取り出す
    heapq.heappush(A, -(A_max // 2))
print(-sum(A))


Measured memory_bytes: 14184
#include<stdio.h>
#include<stdlib.h>
#define NIL NULL

typedef struct node *Node;
struct node{
  int key;
  Node Right;
  Node Left;
  Node Parent;
};

Node root;

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 r){
  if(r == NIL) return;
  inorder(r->Left);
  printf(" %d",r->key);
  inorder(r->Right);
}

void preorder(Node r){
  if(r == NIL) return;
  printf(" %d",r->key);
  preorder(r->Left);
  preorder(r->Right);
}
   void print()
{
  inorder(root);
  printf("\n");
  preorder(root);
  printf("\n");
}

int main()
{
  int m,i,k;
  char s[6];
  scanf("%d",&m);

  for(i=0; i<m; i++){
    scanf("%s%d",s,&k);
    //printf("i = %d\n",i);
    if(s[0] == 'i')
      insert(k);
    else
      print();
  }
  return 0;
}



Measured memory_bytes: 25164
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int mod = 998244353;
int n, q, p10[N], i9;

int add(int x, int y) {
	if (x + y >= mod) {
		return x + y - mod;
	}
	return x + y;
}

int sub(int x, int y) {
	if (x - y < 0) {
		return x - y + mod;
	}
	return x - y;
}

int mul(int x, int y) {
	return (long long) x * y % mod;
}

int exp(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1) {
			ans = mul(ans, x);
		}
		x = mul(x, x);
		y >>= 1;
	}
	return ans;
}

int inv(int x) {
	return exp(x, mod - 2);
}

struct ST {
	int st[4 * N];
	int lazy[4 * N];

	int same(int d, int len) {
		int fact = mul(sub(p10[len], 1), i9);
		return mul(d, fact);
	}

	int merge(int a, int b, int len) {
		return add(mul(a, p10[len]), b);
	}

	void push(int v, int tl, int tr) {
		if (!lazy[v]) return;

		int tm = (tl + tr) / 2;

		st[2 * v] = same(lazy[v], tm - tl + 1);
		st[2 * v + 1] = same(lazy[v], tr - tm);

		lazy[2 * v] = lazy[v];
		lazy[2 * v + 1] = lazy[v];

		lazy[v] = 0;
	}

	void build(int v, int tl, int tr) {
		if (tl == tr) {
			st[v] = 1;
			return;
		}
		int tm = (tl + tr) / 2;
		build(v * 2, tl, tm);
		build(v * 2 + 1, tm + 1, tr);
		st[v] = merge(st[v * 2], st[v * 2 + 1], tr - tm);
	}

	void update(int v, int tl, int tr, int l, int r, int val) {
		if (l > r) {
			return;
		}
		if (tl == l && tr == r) {
			st[v] = same(val, r - l + 1);
			lazy[v] = val;
			return;
		}
		push(v, tl, tr);
		int tm = (tl + tr) / 2;
		update(v * 2, tl, tm, l, min(tm, r), val);
		update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, val);
		st[v] = merge(st[v * 2], st[v * 2 + 1], tr - tm);
	}

	int query() {
		return st[1];
	}
};

ST st;

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

	p10[0] = 1;
	for (int i = 1; i < N; i++) {
		p10[i] = mul(p10[i - 1], 10);
	}
	i9 = inv(9);

	cin >> n >> q;

	st.build(1, 1, n);

	int l, r, d;
	for (int qi = 0; qi < q; qi++) {
		cin >> l >> r >> d;
		st.update(1, 1, n, l, r, d);
		cout << st.query() << '\n';
	}

	return 0;
}


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

int main(){
  long long N;
  
  cin >> N;
  long long d[N];

  for(int i = 0; i < N; i++){
    cin >> d[i];
  }
  long long sum = 0;
  for(int i = 0; i < N; i++){
   for(int j = i + 1; j < N; j++){
     sum = sum + (d[i] * d[j]);
   }
  }
  cout << sum;    
  return 0;
}

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





int main()
{

    ll x;
    cin >> x;
    ll ans = x / 11 * 2;
    if (x % 11 > 0)
    {
        if (x % 11 <= 6) ans++;
        else ans += 2;
    }

    cout << ans;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int a[200005],b[200005],c[200005];
int main(int argc, char** argv) {
	int n;
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i] >> b[i];
	int ans=0;
	for(int i=1;i<=n;i++) c[i]=a[i]+b[i];
	sort(c+1,c+n+1);
	ans=max(ans,c[n]-c[1]);
	for(int i=1;i<=n;i++) c[i]=a[i]-b[i];
	sort(c+1,c+n+1);
	ans=max(ans,c[n]-c[1]);
	cout << ans;
	return 0;
}

Measured memory_bytes: 5540
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
int n;
        
#define MIN(a,b) (((a)<(b))?(a):(b))
//vector<int> g[200020];
/*
vector<ll> g[200020];
ll s[200020];
bool used[200020];
ll ans[200020];
*/
vector<ll> g[200005];
ll s[200005];
bool used[200005];
ll ans[200005];
ll depth[200005];
ll par[200005];
void bfs(queue<ll> que){
	
}
const int INF=1e9+7;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll N,M;cin>>N>>M;
    for(ll i=0;i<N;i++){
		ans[i]=1e9;
	}
	fill(depth, depth+200005, INF);
	depth[0]=0;
	for(ll i=0;i<M;i++){
        ll a,b;cin>>a>>b;
        a--;b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
	queue<ll>que;
	que.push(0);
	//bfs(que);
	while(!que.empty()){
		int x;
		x=que.front();
		que.pop();
		for(auto y:g[x]){
			if(depth[y]>depth[x]+1){
				depth[y]=depth[x]+1;
				que.push(y);
				par[y]=x;
			}
			
		}
	}
	puts("Yes");
	for(ll i=1;i<N;i++){
		printf("%lld\n",par[i]+1);
	}

	return 0;
}


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

int main() {
int H, W;
cin >> H >> W;
vector<string>M(H);
  
for(int i = 0; i < H; i++){
  cin >> M.at(i);
}
 
for(int i = 0; i < H + 2; i++){
 
  if(i == 0 || i == H+1){
for(int x =0; x < W + 2; x++){
    cout << '#'; 
}
cout << endl;    
}else{
    cout << '#' << M.at(i-1) << '#' << endl;
  }
} 
 
}

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

int main()
{
	int H, W;
	cin >> H >> W;
	vector<vector<int>> a(H, vector<int>(W));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> a[i][j];
		}
	}
	vector<tuple<int, int, int, int>> qs;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (a[i][j] & 1) {
				if (j + 1 < W) {
					qs.emplace_back(i + 1, j + 1, i + 1, j + 2);
					--a[i][j];
					++a[i][j + 1];
				}
				else if (i + 1 < H) {
					qs.emplace_back(i + 1, j + 1, i + 2, j + 1);
					--a[i][j];
					++a[i + 1][j];
				}
			}
		}
	}
	cout << qs.size() << endl;
	for (auto q : qs) {
		int px, py, qx, qy;
		tie(px, py, qx, qy) = q;
		cout << px << ' ' << py << ' ' << qx << ' ' << qy << endl;
	}
	return 0;
}


Measured memory_bytes: 5232
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/detail/standard_policies.hpp>
// using namespace __gnu_pbds;
using namespace std;
// using cd = complex<double>;
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
//     tree_order_statistics_node_update>;
 

typedef long long int ll;
typedef long double ld;
const ll N = 1e6 + 9;
const ll mod = 1e9 + 7;
const ll inf= 1e14;

const double PI = acos(-1);
#define x first
#define y second
#define pb push_back
#define mp make_pair    
#define pii pair<ll,ll>
#define pld pair<ld,ld>
ll powm(ll a, ll b,ll mod) { a = a%mod;ll res = 1; while (b) { if (b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }
ll parent[N],siz[N];
void make_set(int v) {
    parent[v] = v;
    siz[v] = 1;
}
int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (siz[a] < siz[b])
            swap(a, b);
        parent[b] = a;
        siz[a] += siz[b];
    }
}


int main() {    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
    #endif
    ll T = 1;
    // cin>>t;

    while(T--){
        ll n,m;cin>>n>>m;
        for(int i = 1;i<=n;i++){
            make_set(i);
        }
        for(int i = 0;i<m;i++){
            ll u,v;cin>>u>>v;
            union_sets(u,v);
        }
        ll ans = 0;
        for(int i = 1;i<=n;i++){
            ans = max(ans,siz[find_set(i)]);
        }
        cout<<ans<<'\n';
    }
}

Measured memory_bytes: 6772
import java.util.*;

public class Main{
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    char[] c = S.toCharArray();
    for(int i = 0; i < S.length(); i+=2){
      System.out.print(c[i]);
    }
    System.out.println("");
  }
}

Measured memory_bytes: 28952
#include <stdio.h>
int main(void) {
	int n, x;
	int i, j, k;

	while (1)
	{
		int count = 0;
		scanf("%d %d", &n, &x);

		if (n == 0 && x == 0) {
			break;
		}

		for (i = 1; i <= n; i++) {
			for (j = 1; j <= n; j++) {
				for (k = 1; k <= n; k++) {
					if (i + j + k == x && i != j && j != k && k != i) {
						count++;
					}
				}
			}
		}
		printf("%d\n", count / 6);
	}
	return 0;
}

Measured memory_bytes: 600
H,W = map(int,input().split())
canvas = []

for h in range(H):
    input_line = input()
    l = []
    [l.append(input_line[i]=='#') for i in range(W)]
    canvas.append(l)

for h in range(H):
    for w in range(W):
        if canvas[h][w]:
            if not((h!=0 and canvas[h-1][w]) or (w!=0 and canvas[h][w-1]) or (h!=H-1 and canvas[h+1][w]) or (w!=W-1 and canvas[h][w+1])):
                print('No')
                break
    else:
        continue
    break
else:
    print('Yes')


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

int main(){
    ll n, k;
    cin >> n >> k;
    vector<ll> h(n);
    rep(i, 0, n) cin >> h[i];
    sort(h.begin(), h.end(), greater<ll>());
    ll mn = 1e9;
    rep(i, 0, n-k+1){
        mn = min(mn, h[i] - h[i+k-1]);
    }
    cout << mn << endl;
    return 0;
}

Measured memory_bytes: 1024
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

no = "Impossible"
h, w = 0, 0
while h < H-1 or w < W-1:
    if A[h][w] == ".":
        print(no)
        break
    A[h][w] = "."
    if h > 1:
        if A[h-1][w] == "#":
            print(no)
            break
    if w > 1:
        if A[h][w-1] == "#":
            print(no)
            break
    
    if h < H-1:
        if A[h+1][w] == "#":
            h += 1
            continue

    if w < W-1:
        if A[h][w+1] == "#":
            w += 1
            continue

else:
    A[H-1][W-1] = "."
    for i in range(H):
        if A[i].count("#") > 0:
            print(no)
            break
    else:
        print("Possible")


Measured memory_bytes: 9132
#include<stdio.h>

int main()
{
  int x,y,i;
  for (i=1;; i++) {
    scanf("%d %d", &x, &y);
    if (x==0 && y==0) {
      break;
    }
    if (x>y) {
      int tmp=x;
      x=y;
      y=tmp;
    }
    printf("%d %d\n", x, y);
  }
  return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <assert.h>
#include <numeric>
#include <time.h>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < n; i++)
#define all(c) (c).begin(), (c).end()
#define P pair<int, int>
#define chmin(x, y) x = min(x, y)

int main()
{
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++)
  {
    cin >> a[i];
  }

  unordered_map<int, int> mp;
  for (int i = 0; i < n; i++)
  {
    mp[a[i]]++;
  }

  vector<int> c, d;
  for (auto el : mp)
  {
    c.push_back(el.first);
    if (el.second == 1)
    {
      d.push_back(el.first);
    }
  }

  vector<int> b((int)(1e6 + 1));
  for (int i = 0; i < c.size(); i++)
  {
    for (int j = 1; j <= ((int)(1e6) / c[i]); j++)
    {
      b[c[i] * j]++;
    }
  }

  int ans = 0;
  for (int i = 0; i < d.size(); i++)
  {
    if (b[d[i]] == 1)
    {
      ans++;
    }
  }

  cout << ans << endl;
}


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

int main(void){
  string x, y;
  cin >> x >> y;

  int m = x.length(), n = y.length();
  
  vector<vector<int> > dp(m + 1, vector<int>(n + 1));
  for(int i = 0; i <= m; i++){ dp[i][0] = i; }
  for(int i = 0; i <= n; i++){ dp[0][i] = i; }
  
  for(int i = 1; i <= m; i++){
    for(int j = 1; j <= n; j++){
      dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
      if(x[i - 1] == y[j - 1])
        dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
      else
        dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
    }
  }

  cout << dp[m][n] << endl;  
  return 0;
}




Measured memory_bytes: 6880
N, M = map(int, input().split())

ac = [False] * N
wa = [0] * N
for _ in range(M):
    p, S = input().split()
    p = int(p) - 1
    if S == 'AC':
        ac[p] = True
    else:
        if not ac[p]:
            wa[p] += 1

a = 0
b = 0
for i in range(N):
    if ac[i]:
        a += 1
        b += wa[i]
print(*[a, b])

Measured memory_bytes: 10256
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <numeric>
#include <string>
#include <cassert>
#include <bitset>

using namespace std;
typedef long long ll;

int main() {
  int N;
  cin >> N;
  double sum = 0.0;
  for (int i = 0; i < N; ++i) {
    int A;
    cin >> A;
    sum += 1.0/double(A);
  }
  cout << setprecision(20) << 1.0 / sum << endl;
  return 0;
}


Measured memory_bytes: 256
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
counter = [0]*N
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for _ in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x
# print(G)
# print(counter)
seen = [0]*N
todo = [0]
seen[0] = 1
while todo:
    v = todo.pop()
    cost = counter[v]
    for nv in G[v]:
        if seen[nv]:
            continue
        seen[nv] = 1
        counter[nv] += cost
        todo.append(nv)

print(*counter)

Measured memory_bytes: 55856
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=998244353;
const ll N = 2e5+10;



ll mul(ll a,ll b){
    return ((a%mod)*(b%mod)*1LL)%mod;
}

void solve(){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    for (int i = 0; i < 1000; i++) {
        ll ah=c-b;
        ll th=a-d;
        if(ah<=0){
            cout<<"Yes\n";
            return;
        }
        if(th<=0){
            cout<<"No\n";
            return;
        }
        c=ah;a=th;
    }
    


    

       
}



int main(){

    
        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        ll T=1;
        //cin>>T;
        while(T--){
            solve();
        }
        return 0;

}

Measured memory_bytes: 3648
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		long answer=1;
		for(int i=1; i<=n; i++){
			answer*=i;
		}
		System.out.println(answer);
	}
}

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

using namespace std;

#define N 300000

const int mod=1000000007;
int n,a[N],nxt[N],sum[N],f[N],ans;
char s[N];

void upd(int &x,int y){x=(x+y)%mod;}

int main(){
	scanf("%s",s+1); n=strlen(s+1);
	for (int i=n;i;--i){
		a[i]=s[i]=='a'?1:2;
		nxt[i]=a[i]==a[i+1]?i+1:nxt[i+1];
		sum[i]=(sum[i+1]+a[i])%3;
	}
	if (!nxt[1]){
		puts("1");
		return 0;
	}
	f[0]=1;
	for (int i=0;i<=n;++i){
		upd(f[i+1],f[i]);
		if (nxt[i+1]) upd(f[nxt[i+1]],f[i]);
		if (i&&!sum[i+1]) upd(ans,f[i]);
	}
	printf("%d\n",ans);
	
	return 0;
}
			

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
int main(){
    char a;
    cin >>a;

    if(a=='A'){
        cout<<'T'<<endl;
    }
    if(a=='T'){
        cout<<'A'<<endl;
    }
    if(a=='C'){
        cout<<'G'<<endl;
    }
    if(a=='G'){
        cout<<'C'<<endl;
    }
}

Measured memory_bytes: 256
from sys import stdin

input = stdin.readline

N = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
res = a[0]
cnt = N - 2
cur = 1
while cnt:
    if cnt == 1:
        res += a[cur]
        break
    else:
        res += a[cur] * 2
        cur += 1
        cnt -= 2

print(res)

Measured memory_bytes: 105112
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <climits>
using namespace std;
#define MOD int(1e9 + 7)
#define INF (long long)(1e18)

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

    long long min_ope = LLONG_MAX;
    for (long long i = 0; i < 26; i++)
    {
        string c = S;
        long long ope = 0;
        while (true)
        {
            long long count = 0;
            for (long long j = 0; j < c.size(); j++)
                if (c[j] - 'a' == i)
                    count++;

            if (count == c.size())
            {
                min_ope = min(min_ope, ope);
                break;
            }

            string ns(c.size() - 1, '*');
            for (long long j = 0; j < ns.size(); j++)
                if (c[j] - 'a' == i || c[j + 1] - 'a' == i)
                    ns[j] = i + 'a';

            c = ns;
            ope++;
        }
    }

    cout << min_ope << endl;
}

Measured memory_bytes: 256
info = [int(input()) for _ in range(4)]
ans = 0
for i in range(info[0] + 1):
  for j in range(info[1] + 1):
    k = (info[3] - (500*i + 100*j)) // 50
    if 0 <= k <= info[2]:
      ans += 1
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
#include <bitset>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    ll val = 1, ans = 0;
    while(val * 2 - 1 <= n)
    {
        val *= 2;
        ans++;
    }
    cout << ans << endl;
    return 0;
}




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

int64_t N, K, MOD = 1e9 + 7, ans;

int main() {    
    cin >> N >> K;
    while (K <= N + 1) {
        int64_t L = (K - 1) * K / 2;
        int64_t R = K * (N + (N - K + 1)) / 2;
        ans += R - L + 1;
        ans %= MOD;
        K++;
    }
    cout << ans << endl;
}

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

int main() {
  int r, c;
  cin >> r >> c;
  int table[r + 1][c + 1] = {0};

  int i, j;
  for (i = 0; i < r; i++) {
    for (j = 0; j < c; j++) {
      cin >> table[i][j];
      if (j == 0) {
        table[i][c] = 0;
      }
      table[i][c] += table[i][j];
      table[r][j] += table[i][j];
    }
  }
  for (i = 0; i < c; i++) {
    table[r][c] += table[r][i];
  }

  for (i = 0; i < r + 1; i++) {
    for (j = 0; j < c + 1; j++) {
      cout << table[i][j];
      if (j != c) {
        cout << " ";
      }
    }
    cout << endl;
  }

  return 0;
}



Measured memory_bytes: 3108
// made by egor <https://pypi.org/project/egor/>
// @author MaxHeap

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <map>

using namespace std;

int main() {
  int h, n; cin >> h >> n;
  int sum = 0;
  for(int i = 0;i < n; ++i) {
    int x; cin >> x;
    sum += x; 
  }
  
  cout << (sum >= h ? "Yes": "No") << endl;
}


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


int main(){
 int hiki,hon;
  int flug=0;
  cin>>hiki>>hon;
  for(int i=0;i<=hiki;i++){
    if(i*2+(hiki-i)*4==hon){
      flug=1;
      break;
    }
  }
  if(flug==0) cout<<"No";
  else cout<<"Yes";  
  
 return 0;
}

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

ll solve() {
    ll N, M, X;
    cin >> N >> M >> X;
    vector<ll> C(N);
    vector<vector<ll>> A(N, vector<ll>(M));
    for ( int i = 0; i < N; i++ ) {
        cin >> C[i];
        for ( int j = 0; j < M; j++ ) {
            cin >> A[i][j];
        }
    }
    ll INF =1LL << 60;
    ll ans = INF;
    for ( int b = 0; b < 1<<N; b++ ) {
        vector<ll> s(M);
        ll cs = 0;
        for ( int ii = 0; ii < N; ii++ ) {
            if ( (b >> ii) & 1 ) {
                cs += C[ii];
                for ( int j = 0; j < M; j++ ) {
                    s[j] += A[ii][j];
                }
            }
        }
        bool ng = false;
        for ( int j = 0; j < M; j++ ) {
            if ( s[j] < X ) ng = true;
        }
        if ( !ng ) {
            ans = min(ans, cs);
        }
    }
    if ( ans == INF ) return -1;
    else return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  
  if (N/100 == 7) {
    cout << "Yes" << endl;
  }
  
  else if (N/10-(N/100)*10 == 7) {
    cout << "Yes" << endl;
  }
  
  else if (N-(N/10)*10 == 7) {
    cout << "Yes" << endl;
  }
  
  else {
    cout << "No" << endl;
  }
}
 

Measured memory_bytes: 3644
#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

const int maxn = 110;

int n;
int a[maxn];
ll f[maxn][2],g[maxn];

int main()
{
	scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	f[0][0]=1ll; g[0]=1ll;
	for(int i=1;i<=n;i++)
	{
		if(a[i]&1) f[i][1]=2ll*g[i-1]+f[i-1][1],f[i][0]=f[i-1][0];
		else f[i][0]=2ll*f[i-1][0],f[i][1]=g[i-1]+2ll*f[i-1][1];
		g[i]=f[i][0]+f[i][1];
	}
	printf("%lld\n",f[n][1]);
	
	return 0;
}


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

typedef long long int ll;

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

    ll ans = 0;
    for(ll i = n - 1;i >= 0;i--){
        if((a[i] + ans) % b[i] != 0)
            ans += b[i] - ((a[i] + ans) % b[i]);
    }

    cout << ans;

    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {0,1,0,-1,1,-1,1,-1};
ll dx[8] = {1,0,-1,0,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << "\n";}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << "\n";
}
const int mod = 1e9 + 7;
//const int mod = 998244353;

struct edge{
    ll to, a, b;
};

int main(){
    ll n,m,s,t; cin >> n >> m >> s >> t; s--; t--;
    vector<vector<edge>> G(n);
    rep(i,m){
        ll u,v,a,b; cin >> u >> v >> a >> b; u--; v--;
        G[u].push_back({v,a,b});
        G[v].push_back({u,a,b});
    }
    vl d(n,linf);
    vl e(n,linf);
    d[s] = 0; e[t] = 0;
    priority_queue<P,vector<P>,greater<P>> pq;
    pq.emplace(0,s);
    while(!pq.empty()){
        P p = pq.top(); pq.pop();
        ll u = p.second;
        //if(d[u] > p.first) continue;
        for(auto v : G[u]){
            if(d[v.to] > d[u] + v.a){
                d[v.to] = d[u] + v.a;
                pq.emplace(d[v.to], v.to);
            }
        }
    }
    pq.emplace(0,t);
    while(!pq.empty()){
        P p = pq.top(); pq.pop();
        ll u = p.second;
        //if(e[u] > p.first) continue;
        for(auto v : G[u]){
            if(e[v.to] > e[u] + v.b){
                e[v.to] = e[u] + v.b;
                pq.emplace(e[v.to], v.to);
            }
        }
    }
    vl ans(n);
    ll mn = linf;
    for(ll i=n-1; i>=0; i--){
        chmin(mn,d[i]+e[i]);
        ans[i] = mn;
    }
    rep(i,n){
        cout << 1000000000000000 - ans[i] << "\n";
    }
}

Measured memory_bytes: 13560
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
#define ote(x) cout<<(x)<<endl
#define all(x) (x).begin(),(x).end()
#define rp(i,s,e) for(int i=(s);i<(e);++i)
#define rpz(i,e) rp(i,0,(e))
#define irp(i,s,e) for(int i=(s);i>(e);--i)
#define irpz(i,s) irp(i,(s),-1)
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;}

ll N,A,B;

ll MOD = 1000000007L;

// a^n mod を計算する(二分累乗法:O(logn))
ll modpow(ll a, ll n, ll mod) {
	ll res = 1;
	while(n > 0){
		if(n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

ll modinv(ll a, ll m) {
	ll b = m, u = 1, v = 0;
	while(b){
		ll t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if(u < 0) u += m;
	return u;
}

// nCr mod
ll nCr(ll n, ll r, ll m){
	ll ret = 1;
	for(ll i=0; i<r; ++i){
		ret = (ret * (n-i))%m * modinv(r-i,m) % m;
	}
	return ret;
}

ll solve(){
	// cout<<N<<" "<<A<<" "<<B<<"\n";//
	ll sum_nCr = modpow(2, N, MOD) - 1;
	ll nca = nCr(N, A, MOD);
	ll ncb = nCr(N, B, MOD);
	// cout<<sum_nCr<<" "<<nca<<" "<<ncb<<"\n";//

	ll ans = (sum_nCr - (nca + ncb)%MOD)%MOD;
	if(ans < 0L) ans += MOD;
	return ans;
}

int main(){
	cin>>N>>A>>B;
	cout<< solve() <<endl;
}


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

int N;

int main(void)
{

    int N, a;
    int count = 0;
    cin >> N;

    rep(i, N)
    {
        cin >> a;

        if ((i + 1) % 2 == 1 && a % 2 == 1)
        {
            count++;
        }
    }

    cout << count;
}

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

int main(){
    int n;
    cin>>n;
    vector<int> h(n);
    rep(i,n) cin>>h[i];
    int ans = 0, temp = 0;
    rep(i,n-1){
        if (h[i] >= h[i+1]) {
            temp++;
            ans = max(ans, temp);
        }
        else {
            ans = max(temp, ans);
            temp = 0;
        };
    }
    cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

ll n,k;
Vi d;

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	std::cout<<std::fixed<<std::setprecision(30);
	cin>>n>>k;
	d.resize(k);
	rep(i,k){
		cin>>d[i];
	}
	Vi v;
	rep(i,10){
		bool fg = true;
		rep(j,k){
			if(i==d[j]){
				fg = false;
				break;
			}
		}
		if(fg){
			v.pb(i);
		}
	}
	priority_queue< ll ,vector<ll>,greater<ll>> pq;
	pq.push(0);
	ll ans = 0;
	while(!pq.empty()){
		ll top = pq.top();
		pq.pop();
		if(top>=n){
			ans = top;
			break;
		}
		rep(i,v.size()){
			ll tp =v[i];
			if(top==0 && tp ==0)continue;
			tp = top*10+tp;
			pq.push(tp);
		}
	}
	print(ans);
	return 0;
}

Measured memory_bytes: 892
from collections import deque
from itertools import permutations
from math import factorial
N = int(input())
places = [list(map(int, input().split())) for i in range(N)]
total = 0
for p in permutations(places):
  d = deque(p)
  departure = d.popleft()
  while d:
    arrival = d.popleft()
    total += ((departure[0] - arrival[0])**2 + (departure[1] - arrival[1])**2)**0.5
    departure = arrival
print(total / factorial(N))

Measured memory_bytes: 3444
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int main(void){
    int n;
    int max;
    int w[1000][1001];
    char data[1000][1001];
    
    while(cin>>n,n!=0){
        max=0;
        for(int i=0;i<n;i++){
            scanf("%s",data[i]);
        }
        for(int i=0;i<n;i++){
            w[0][i]=(data[0][i]=='*')?0:1;
            w[i][0]=(data[i][0]=='*')?0:1;
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<n;j++){
                if(data[i][j]=='*'){
                    w[i][j]=0;
                }
                else{
                    w[i][j]=min(w[i-1][j-1],min(w[i-1][j],w[i][j-1]))+1;
                }
                if(max<w[i][j]){
                    max=w[i][j];
                }
            }
        }
        cout<<max<<endl;;
    }
    return(0);
}

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

const ll INF=1LL<<60;
const int N_MAX=210;

int N,M,R;
ll dp[N_MAX][N_MAX];

int main() {
  cin>>N>>M>>R;
  vector<int> r;
  rep(i, R) {
    int x; cin>>x;
    x--;
    r.push_back(x);
  }
  rep(i, N_MAX) {
    rep(j, N_MAX) {
      dp[i][j]=INF;
    }
    dp[i][i]=0;
  }
  rep(i, M) {
    int a,b,c; cin>>a>>b>>c;
    a--; b--;
    dp[a][b]=c;
    dp[b][a]=c;
  }
  rep(k, N) {
    rep(i, N) {
      rep(j, N) {
        dp[i][j]=min(dp[i][j], dp[i][k]+dp[k][j]);
      }
    }
  }
  ll res=INF;
  sort(r.begin(), r.end());
  do {
    ll tmp=0;
    rep(i, r.size()-1) tmp+=dp[r[i+1]][r[i]];
    res=min(res, tmp);
  } while (next_permutation(r.begin(), r.end()));
  cout<<res<<endl;
}

Measured memory_bytes: 640