akhauriyash/Code-Regression huggingface dataset:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
# sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = True
show_flg = False


def main():
    N, P = MI()
    A = LI()
    total = sum(A)
    dp = [0] * (total+1)
    dp[0] = 1

    # tmp = [0] * (total+1)
    # for i in range(2 ** N):
    #     groups = []
    #     for j in range(N):
    #         if ((i >> j) & 1):
    #             groups.append(A[j])
    #     tmp[sum(groups)] += 1

    # print(tmp)

    for i in range(N):
        dp_next = [0] * (total+1)
        for j in range(total+1):
            if dp[j] >= 1:
                dp_next[j] = max(dp[j], dp_next[j])
                if j + A[i] <= total:
                    dp_next[j+A[i]] = dp[j+A[i]]
                    dp_next[j+A[i]] += dp[j]
                # print(i, j, dp_next, dp[j])
        # print(i, dp_next)
        dp = dp_next

    ans = 0
    for i in range(total+1):
        if i % 2 == P:
            ans += dp[i]
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 40428
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
#define RF(x) freopen(x,"r",stdin)
#define WF(x) freopen(x,"w",stdout)
typedef long long LL;
using namespace std;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
const LL MOD = (LL)1e9+7;
const int MAXN = 1e5+5;
const LL INF = 1LL<<60;
const double eps = 1e-8;
const double PI=3.1415926535897932;

int d[100009];

int main(){
	DRI(n);
	RI(d[0]);int fv=d[0];
	LL ans=0,fans=INF;
	if(fv<=0){
		d[0]=1;ans=1-fv;
	}else d[0]=fv;
	LL csum=d[0];
	REPP(i,1,n){
		RI(d[i]);csum+=d[i];
		if((i%2)^(d[0]<0)){
			if(csum>=0){
				ans+=(csum+1);
				csum=-1;
			}
		}
		else{
			if(csum<=0){
				ans+=(1-csum);
				csum=1;
			}
		}
	}
	fans=min(fans,ans);
	ans=0;
	if(fv>=0){
		d[0]=-1;ans=fv+1;
	}
	else d[0]=fv;
	csum=d[0];
	REPP(i,1,n){
		csum+=d[i];
		if((i%2)^(d[0]<0)){
			if(csum>=0){
				ans+=(csum+1);
				csum=-1;
			}
		}
		else{
			if(csum<=0){
				ans+=(1-csum);
				csum=1;
			}
		}
	}
	fans=min(fans,ans);
	printf("%lld",fans);
}


Measured memory_bytes: 764
#include <iostream>
#include <queue>
#include <cctype>
#include <stdio.h>
#include <map>

using namespace std;


int main(int argc, char const* argv[])
{
    int time=0;
    int tmp;
    for (int i = 0; i < 4; i++) 
    {
        cin >> tmp;
        time += tmp;
    }
    cout << time / 60 << endl;
    cout << time % 60 << endl;
    return 0;
}

Measured memory_bytes: 1160
#include "stdio.h"
int main(){
  int K, X, i;
  scanf("%d %d", &K, &X);
  for(i = K; i > 0; i--){
    printf("%d ", X - (i - 1));
  }
  for(i = 1; i < K; i++){
    printf("%d ", X + i);
  }
}


Measured memory_bytes: 128
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e18)
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;

int N,W;
int dp[1000][100000];

int main() {

    cin >> N >> W;
    int v[N],w[N];
    for(int i=0;i<N;i++){
        cin >>v[i] >>w[i];
    }

    for (int w = 0; w <= W; ++w) dp[0][w] = 0;
    for(int i=0;i<N;i++){
        for(int j=0;j<=W;j++){
            if(j<w[i]){
                dp[i+1][j] = dp[i][j];
            }else{
                dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]);
            }
        }
    }
    cout << dp[N][W] << endl;


}



Measured memory_bytes: 7436
using System;

class main
{
    static void Main(string[] args)
    {
        string[] read = Console.ReadLine().Split(' ');

        int A = int.Parse(read[0]);
        int B = int.Parse(read[1]);
        int H = int.Parse(read[2]);
        int M = int.Parse(read[3]);

        double aAngle = H * 30 + M * 0.5;
        double bAngle = M * 6;
        double aX = A * Math.Cos(aAngle * Math.PI / 180);
        double aY = A * Math.Sin(aAngle * Math.PI / 180);
        //Console.WriteLine($"{aX} :{aY}");
        double bX = B * Math.Cos(bAngle * Math.PI / 180);
        double bY = B * Math.Sin(bAngle * Math.PI / 180);
        //Console.WriteLine($"{bX} :{bY}");
        double r = Math.Sqrt(Math.Pow(Math.Abs(bX - aX), 2) + Math.Pow(Math.Abs(bY - aY), 2));


                Console.Write($"{r:F20}");

    }
        
}



Measured memory_bytes: 27956
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

dp = [0]*(N+1)
for j in range(3):
    for i in range(1,N+1):
        if i-A[j] >= 0:
            dp[i] = max(dp[i],dp[i-1]+1,dp[i-A[j]]+B[j])
        else:
            dp[i] = max(dp[i],dp[i-1]+1)

M = dp[N]            
dp = [0]*(M+1)

for j in range(3):
    for i in range(1,M+1):
        if i-B[j] >= 0:
            dp[i] = max(dp[i],dp[i-1]+1,dp[i-B[j]]+A[j])
        else:
            dp[i] = max(dp[i],dp[i-1]+1)
    
print(dp[M])

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

int main() {
  int N;
  int cnt = 0;

  cin >> N;

  int max_cnt = -1;
  int ans = -1;

  rep(1, N+1) {
    int cnt = 0;
    int y = i;

    while (y%2 == 0) {
      y /= 2;
      ++cnt;
    }

    if (max_cnt < cnt) {
      max_cnt = cnt;
      ans = i;
    }
  }

  cout << ans << endl;

  return 0;
}

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

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

    ll cntr = 0, cntl = 0;
    vector<ll> cnt(S.size(), 0);
    for(ll i=0; i<S.size()-1; i++){
        if(S.at(i) == 'R'){
            cntr++;
        }

        if(S.at(i) == 'R' && S.at(i+1) == 'L'){
            if(cntr == 1){
                cnt.at(i) += 1;
            }
            else if(cntr%2 == 0){
                cnt.at(i) += cntr/2;
                cnt.at(i+1) += cntr/2;
            }
            else{
                cnt.at(i) += cntr/2 + 1;
                cnt.at(i+1) += cntr/2;
            }
            cntr = 0;

            for(ll j=i+1; j<S.size(); j++){
                if(S.at(j) == 'L'){
                    cntl++;
                    if(j==S.size()-1){
                        if(cntl == 1){
                            cnt.at(i+1) += 1;
                        }
                        else if(cntl%2 == 0){
                            cnt.at(i) += cntl/2;
                            cnt.at(i+1) += cntl/2;
                        }
                        else{
                            cnt.at(i) += cntl/2;
                            cnt.at(i+1) += cntl/2 + 1;
                        }
                        
                        break;
                    }
                   
                }

                if(S.at(j) == 'L' && S.at(j+1) == 'R'){
                    if(cntl == 1){
                        cnt.at(i+1) += 1;
                    }
                    else if(cntl%2 == 0){
                        cnt.at(i) += cntl/2;
                        cnt.at(i+1) += cntl/2;
                    }
                    else{
                        cnt.at(i) += cntl/2;
                        cnt.at(i+1) += cntl/2 + 1;
                    }
                
                    i = j;
                    cntl = 0;
                    break;
                }
            }
        }
    }

    rep(i, S.size()){
        cout << cnt.at(i);
        if (i!=S.size()-1) cout << " "; 
    }
    
    cout << endl;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
	int n;
	cin>>n;
	vector<int>arr(n);
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	sort(arr.begin(),arr.end());
	cout<<arr[n/2]-arr[n/2-1];
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define y_n(ans) cout<<(ans?"Yes":"No")<<endl;

int main() {
    int x, y;
    cin >> x >> y;
    bool ans = false;
    for (int i=0; i<=100; ++i) {
        if (4*i > y) break;
        if (4*i + 2*(x-i) == y) ans = true;
    }
    y_n(ans);
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

const ll INF = 1e17;
ll N, M, L, Q;
ll fuel[305][305];
ll dist[305][305];
ll s[105000], t[105000];
ll A[100000], B[100000], C[100000];

void input() {
  cin >> N >> M >> L;
  for (int i = 1; i <= M; i++) cin >> A[i] >> B[i] >> C[i];
  cin >> Q;
  for (int i = 1; i <= Q; i++) cin >> s[i] >> t[i];
}

void solve() {
  input();
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      fuel[i][j] = INF;
      dist[i][j] = INF;
    }
    fuel[i][i] = 0;
    dist[i][i] = 0;
  }
  for (int i = 1; i <= M; i++) {
    chmin(fuel[A[i]][B[i]], C[i]);
    chmin(fuel[B[i]][A[i]], C[i]);
  }
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      for (int k = 1; k <= N; k++) {
        chmin(fuel[j][k], fuel[j][i] + fuel[i][k]);
      }
    }
  }
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      if (i == j) continue;
      if (fuel[i][j] <= L) chmin(dist[i][j], 1LL);
    }
  }
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      for (int k = 1; k <= N; k++) {
        chmin(dist[j][k], dist[j][i] + dist[i][k]);
      }
    }
  }
  for (int i = 1; i <= Q; i++) {
    if (dist[t[i]][s[i]] < INF)
      cout << dist[t[i]][s[i]] - 1 << "\n";
    else
      cout << -1 << "\n";
  }
  return;
}

int main() {
  solve();
  return 0;
}

Measured memory_bytes: 4864
n = int(input())
a = list(map(int, input().split()))
flag = 1
ans = 1

for i in range(n):
  if a[i] == 0:
    flag = 0
    print(0)
    
if flag:
  for i in range(n):
    ans = ans * a[i]
    if ans > 1000000000000000000:
      flag = 0
      print(-1)
      break
      
if flag:
  print(ans)
      

Measured memory_bytes: 21648
#include <bits/stdc++.h>[
using namespace std;
int main(){
  int x,y;
  cin >> x >> y;
  int ans=0;
  if (x < 4) ans+=(4-x)*100000;
  if (y < 4) ans+=(4-y)*100000;
  if (x==1 && y==1) ans+=400000;
  cout << ans << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
int main() {
	int N;
	cin >> N;
	int h = 0;
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int H;
		cin >> H;
		if (H >= h) ans++;
		h = max(h, H);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

    final long M = 1_000_000_007;
    int n = scanner.nextInt();
    int m = scanner.nextInt();
    int[] x = new int[n];
    int[] y = new int[m];
    for (int i = 0; i < n; i++) x[i] = scanner.nextInt();
    for (int i = 0; i < m; i++) y[i] = scanner.nextInt();

    System.out.println(compute(x, M) * compute(y, M) % M);
  }

  private static long compute(int[] a, long mod) {
    long ans = 0;
    int n = a.length;
    for (int i = 1; i < n; i++) {
      long d = a[i] - a[i - 1];
      long c = nc2(n, mod);
      c -= nc2(i, mod);
      if (c < 0) c += mod;
      c -= nc2(n - i, mod);
      if (c < 0) c += mod;
      ans += (c * d) % mod;
      ans %= mod;
    }
    return ans;
  }
  private static long nc2(long n, long mod) {
    if (n < 2) return 0;
    return (n * (n - 1) / 2) % mod;
  }
}


Measured memory_bytes: 85080
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<cmath>
#include<set>
#include<stack>
#define ll long long
#define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)>(y)?(y):(x)
#define cls(name,x) memset(name,x,sizeof(name))
using namespace std;
const int inf=1<<28;
const int maxn=100010;
const int maxm=110;
const int maxk=100010;
const int mod=1e9+7;
const double pi=acos(-1.0);
ll n,m;
ll func(ll a,ll b,ll c)
{
    ll i=max(max(a,b),c);
    ll j=min(min(a,b),c);
    return i-j;
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(~scanf("%lld %lld",&n,&m))
    {
        ll a,b,c;
        ll ans=maxn*maxn;
        for(ll i=1;i<n;i++)
        {
            a=i*m;
            b=(n-i)/2*m;
            c=((n-i)-(n-i)/2)*m;
            if(a!=0&&b!=0&&c!=0)
                ans=min(ans,func(a,b,c));
            b=(n-i)*(m/2);
            c=(n-i)*(m-m/2);
            if(a!=0&&b!=0&&c!=0)
                ans=min(ans,func(a,b,c));
        }
        swap(n,m);
        for(ll i=1;i<n;i++)
        {
            a=i*m;
            b=(n-i)/2*m;
            c=((n-i)-(n-i)/2)*m;
            if(a!=0&&b!=0&&c!=0)
                ans=min(ans,func(a,b,c));
            b=(n-i)*(m/2);
            c=(n-i)*(m-m/2);
            if(a!=0&&b!=0&&c!=0)
                ans=min(ans,func(a,b,c));
        }
        printf("%lld\n",ans);
    }
    return 0;
}


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

int main(void) {
	int a[4], b[4], e = 0, f = 0;
	while(cin >> a[0] >> a[1] >> a[2] >> a[3]){
		e = 0;
		f = 0;
		cin >> b[0] >> b[1] >> b[2] >> b[3];
		for (int i = 0; i < 4; i++) {
			if (a[i] == b[i]) e++;
		}
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (i != j) {
					if (a[i] == b[j]) {
						f++;
					}
				}
			}
		}
		cout << e << " " << f << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
int acs(const void *a, const void *b) { return *(int *)a - *(int *)b; }                            /* 1,2,3,4.. */
int des(const void *a, const void *b) { return *(int *)b - *(int *)a; }                            /* 8,7,6,5.. */
int cmp_char(const void *a, const void *b) { return *(char *)a - *(char *)b; }                     /* a,b,c,d.. */
int cmp_str(const void *a, const void *b) { return strcmp(*(const char **)a, *(const char **)b); } /* aaa,aab.. */
#define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b)
#define rep(i, n) for (int i = 0; i < n; i++)
#define MAX 100001
#define MOD 1000000007

typedef long long int lli;

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

  int cost[21], get[21];
  rep(i, n)
  {
    scanf("%d", &get[i]);
  }
  rep(i, n)
  {
    scanf("%d", &cost[i]);
  }

  int ans = 0;
  rep(i, n)
  {
    int value = get[i] - cost[i];
    if (value < 0)
      continue;
    ans += value;
  }
  printf("%d\n", ans);
  return 0;
}


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

using namespace std;

#define pb push_back
#define mk make_pair
#define mod 1000000007
#define ff first
#define ss second

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

ll modpow(ll a, ll b){

    ll ans=1;
    while(b){
        if(b&1){
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        b=b/2;
    }
    return ans;
}


int main(){

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

    int h,a;
    cin>>h>>a;

    int ans = ceil((h*1.0)/a);
    cout<<ans<<endl;
    

}


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



using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;


//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)



int main(void){

	int a, b; cin >> a >> b;
	if((a*b)%2 == 0) cout << "Even" << endl;
	else cout << "Odd" << endl;


	return 0;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int (i)=(a);(i)<(int)(b);(i)++)
#define RREP(i,a,b) for(int (i)=(a);(i)>=(int)(b);(i)--)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;

template<typename T> class Edge{
    public:
        int to;
        T cost;

        Edge(){}
        Edge(int t, T c){
            this->to = t;
            this->cost = c;
        }
        bool operator<(Edge e){return this->cost < e.cost;}
        bool operator>(Edge e){return this->cost > e.cost;}
};

template<typename T> class Graph_list{
    public:
        vector<vector<Edge<T>>> list;

        Graph_list(int n);
        void add(int f, int t, T c);
        void add(int f, int t);
        vector<Edge<T>> operator[](int i){
            return list[i];
        }
};

template<typename T> Graph_list<T>::Graph_list(int n){
    list = vector<vector<Edge<T>>>(n + 1, vector<Edge<T>>());
}

template<typename T> void Graph_list<T>::add(int f, int t, T c){
    list[f].push_back(Edge<T>(t, c));
}
template<typename T> void Graph_list<T>::add(int f, int t){
    list[f].push_back(Edge<T>(t, 1));
}


template<typename T>
vector<T> bfs_graph(Graph_list<T>& g, int s){
    const auto INF = numeric_limits<T>::max();
    vector<T> dist(g.list.size(), INF);
    
    queue<T> que;
    que.push(s);
    dist[s] = 0;
    while(que.size()){
        int p = que.front(); que.pop();
        for (auto e : g[p]){
            if (dist[e.to] == INF){
                dist[e.to] = dist[p] + e.cost;
                que.push(e.to);
            }
        }
    }
    return dist;
}


int main(){
    int n;
    cin >> n;
    Graph_list<ll> G(n);
    REP(i,0,n - 1){
        int a, b, c;
        cin >> a >> b >> c;
        G.add(a, b, c);
        G.add(b, a, c);
    }

    int q, k;
    cin >> q >> k;
    vector<ll> d = bfs_graph<ll>(G, k);
    REP(i,0,q){
        int x, y;
        cin >> x >> y;
        cout << d[x] + d[y] << endl;
    }
    
    
    return 0;
}

Measured memory_bytes: 10480
#include <stdio.h>

void merge(int* A, int left, int mid, int right, int* count){
    int n1 = mid - left;
    int n2 = right - mid;

    int L[n1];
    for(int i = 0; i < n1; i++){
        L[i] = A[left + i];
    }
    int R[n2];
    for(int i = 0; i < n2; i++){
        R[i] = A[mid + i];
    }

    L[n1] = 1000000001;
    R[n2] = 1000000001;

    int i = 0;
    int j = 0;
    int k = 0;
    for(k = left; k < right; k++){
        (*count)++;
        if(L[i] <= R[j]){
            A[k] = L[i];
            i++;
        }else{
            A[k] = R[j];
            j++;
        }
    }
}

void mergeSort(int* A, int left, int right, int* count){
    if(left + 1 < right){
        int mid = (left + right) / 2;
        mergeSort(A, left, mid, count);
        mergeSort(A, mid, right, count);
        merge(A, left, mid, right, count);
    }
}

int main(void){
    int n;
    int A[500000];

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

    int count = 0;
    mergeSort(A, 0, n, &count);

    for(int i = 0; i < n; i++){
        printf("%d", A[i]);
        if(i == n - 1){
            printf("\n");
        }else{
            printf(" ");
        }
    }

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

    return 0;
}



Measured memory_bytes: 6496
N,Q = map(int,input().split())
S = list(input())
l=[]
r=[]
for i in range(Q):
    L,R = map(int,input().split())
    l.append(L)
    r.append(R)

#累積和
count = [0]*(N+1)
for i in range(N):
    if i+1 < N and S[i] == 'A' and S[i+1] == 'C':
        count[i+1] = count[i] + 1
    else:
        count[i+1] = count[i]

#クエリ
for i in range(Q):
    print(count[r[i]-1] - count[l[i]-1])


Measured memory_bytes: 14900
#include <iostream>
#include <string>

int main() {
    int n;
    
    std::cin >> n;
    
    char c;
    long long cnt, stat = 0;
    for(int i = 0; i < n; ++i) {
        std::cin >> c >> cnt;
        
        if(c == ')') stat -= cnt;
        else stat += cnt;
        
        if(stat < 0) {
            std::cout << "NO" << std::endl;
            
            return 0;
        }
    }
    
    if(stat == 0)
        std::cout << "YES" << std::endl;
    else 
        std::cout << "NO" << std::endl;
}

Measured memory_bytes: 3096
# include <bits/stdc++.h>
using namespace std;
# define FOR(i, a, b) for (int i = a; i <= b; ++i)
# define FDR(i, a, b) for (int i = a; i >= b; --i)
# define mp make_pair
# define pb push_back
typedef long long i64;
const int N = 15;

i64 p[N], c[N];
int a[N];

int main ()
{
    i64 D, G;
    cin >> D >> G;
    FOR(i, 1, D) cin >> p[i] >> c[i];
    FOR(i, 1, D) a[i] = i;
    i64 ans = 1e18;
    do {
        i64 s = G, cnt = 0;
        FOR(i, 1, D) {
            if (s <= 0) break;
            i64 mi = min(p[a[i]], (s + a[i] * 100 - 1) / (a[i] * 100));
            cnt += mi;
            s -= mi * a[i] * 100;
            if (mi == p[a[i]]) s -= c[a[i]];
        }
        ans = min(ans, cnt);
    }while (next_permutation(a + 1, a + D + 1));
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
n, x = map(int, input().split())
aList = list(map(int, input().split()))
aList.sort()
sums = 0
i = 0
while sums < x and i < n:
    sums += aList[i]
    i += 1
i -= 1
if sums == x:
    i += 1
print(i)

Measured memory_bytes: 2940
/*
_________________________
|   LIVE FREE OR DIE     |
|       327 2153         |
|          New           |
|_______HAMPSHIRE________|

*/
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define MAX 20
#define int long long
#define MOD 998244353

int32_t main()
{
	IOS
	int a,b,c,d;cin>>a>>b>>c>>d;
	int flag=0;
	while(1)
	{
		if(a<=0)
		{
			flag=1;
			break;
		}
		c-=b;
		if(c<=0)
			break;
		a-=d;
	}
	if(flag) cout<<"No";
	else cout<<"Yes";
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sim template < class c
#define ris return *this
#define dor > debug & operator <<
#define eni(x) sim > typename \
	enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
	ris << "(" << d.first << ", ", d.second << ")";
}
sim dor(rge<c> d) {
	*this << "[";
	for (auto it = d.b; it != d.e; it++)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

int n;
const int N = 1e5 + 5;
ll a[N][3], dp[N][3];

ll solve(int day, int ch) {
	if (day == n + 1) {
		return 0;
	}
	if (dp[day][ch] != -1) {
		return dp[day][ch];
	}
	ll &ret = dp[day][ch];
	for (int i = 0; i < 3; i++) {
		if (i == ch) {
			continue;
		}
		ret = max(ret, a[day][ch] + solve(day + 1, i));
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> a[i][j];
		}
	}
	memset(dp, -1, sizeof(dp));
	ll ans = max({solve(1, 0), solve(1, 1), solve(1, 2)});
	cout << ans;
	
	return 0;
}


Measured memory_bytes: 12800
N,K = map(int,input().split())
XY = [tuple(map(int,input().split())) for i in range(N)]
xs = []
ys = []
for x,y in XY:
    xs.append(x)
    ys.append(y)
xs.sort()
ys.sort()

def is_ok(l,r,d,u):
    k = 0
    for x,y in XY:
        if l <= x <= r and d <= y <= u:
            k += 1
            if k >= K:
                return True
    return False

ans = float('inf')
for i in range(N-1):
    for j in range(i+1,N):
        for k in range(N-1):
            for l in range(k+1,N):
                l,r,d,u = xs[i],xs[j],ys[k],ys[l]
                if (r-l)*(u-d) >= ans: continue
                if is_ok(l,r,d,u):
                    ans = (r-l)*(u-d)
print(ans)

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

int main() {
    int n, ans = 0;
    cin >> n;
    vector<int> t[15], f[15];
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        for (int j = 0; j < a; j++) {
            int x, y;
            cin >> x >> y;
            x--;
            if (y)
                t[i].push_back(x);
            else
                f[i].push_back(x);
        }
    }
    // {0, 1, ..., n-1} の部分集合の全探索
    for (int bit = 0; bit < (1 << n); ++bit) {
        unordered_map<int, bool> mp;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (bit & (1 << i)) {
                mp[i] = true;
                cnt++;
            } else
                mp[i] = false;
        }

        for (int i = 0; i < n; i++) {
            if (!mp[i]) continue;
            for (int j = 0; j < t[i].size(); j++) {
                if (!mp[t[i][j]]) cnt = 0;
            }
            for (int j = 0; j < f[i].size(); j++) {
                if (mp[f[i][j]]) cnt = 0;
            }
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}

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

res = [0]*10**5

for i in range(N):
    a, b = map(int, input().split())
    res[a-1]+=b

count = 0
for i,r in enumerate(res):
    count+=r
    if count >= M:
        print(i+1)
        break


Measured memory_bytes: 5744
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

bool check(string s,string t){
    REP(i,s.size()){
        if(s[i]!='?' and s[i]!=t[i]) return false;
    }
    return true;
}

signed main()
{   
    string s,t; cin>>s>>t;
    string ans="~";
    REP(i,s.size()-t.size()+1){
        if(check(s.substr(i,t.size()),t)){
            string u=s;
            for(int j=0;j<i;j++)
                if(u[j]=='?') u[j]='a';
            for(int j=i;j<i+t.size();j++)
                u[j]=t[j-i];
            for(int j=i+t.size();j<s.size();j++)
                if(u[j]=='?') u[j]='a';
            ans=min(ans,u);
        }
    }
    if(ans=="~") cout<<"UNRESTORABLE"<<endl;
    else cout<<ans<<endl;
}


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

#ifdef LOCAL
#define debug(var) cerr << #var << " = " << var << endl;
#else
#define debug(var)
#endif

void init() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
}

const int N = 12345;

int a[N];

void solve() {
	int n, k; scanf("%d%d", &n, &k);
	for (int i = 0; i < n; ++i) scanf("%d", a+i);
	sort(a, a+n);
	long long sum = 0;
	for (int i = n-1; i >= n-k; --i) sum += a[i];
	printf("%lld", sum);
}

int main() {
	init();
	int t = 1; //scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}


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

using ll=long long;
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define ALL(v) v.begin(),v.end()

const ll INF=1e14;

void dfs2(int index,int end,int maxn,vector<vector<ll>> &vec,vector<ll> buf){
  if(index==end){
    vec.push_back(buf);
    return;
  }
  vector<ll> tmp;
  for(int i=-1;i<maxn;++i) {
  	tmp=buf;
  	tmp[index]=i;
  	dfs2(index+1,end,maxn,vec,tmp);
  }

}



ll dfs(vector<ll> a,vector<vector<int>> flag){
	
  if(a.size()==0) return 0;
  if(a[0]<=0){
  	a.erase(a.begin());
  	flag.erase(flag.begin());
  	REP(i,flag.size()){
		flag[i].erase(flag[i].begin());
	}
	return dfs(a,flag);
  }

  ll res=INF;
  vector<vector<ll>> vec;

  vector<ll> buf(a.size()-1);
  dfs2(0,a.size()-1,min(ll(a.size())-1,a[0]),vec,buf);

	REP(i,vec.size()){
		vector<vector<int>> tmpflag(a.size(),vector<int>(a.size(),false));
		REP(j,vec[i].size()){
			REP(k,vec[i].size()){
				if(k==j)continue;
				if(vec[i][j]!=-1&&vec[i][j]==vec[i][k])tmpflag[j+1][k+1]=true;
			}	
		}
		
		bool ok=true;
		REP(j,a.size())REP(k,a.size()){
			if(flag[j][k]&&tmpflag[j][k])ok=false;
			tmpflag[j][k] = flag[j][k] || tmpflag[j][k];
		}
		REP(j,vec[i].size()){
			if(vec[i][j]!=-1&&flag[0][j+1])ok=false;
		}
		
		if(!ok)continue;
		vector<ll> newa(a.size()-1);
		REP(j,a.size()-1){
			newa[j]=a[j+1];
			if(vec[i][j]!=-1)newa[j]--;
		}
		tmpflag.erase(tmpflag.begin());
		REP(j,tmpflag.size())tmpflag[j].erase(tmpflag[j].begin());
		res=min(res,dfs(newa,tmpflag));
	
	}
  
  return res+a[0];
}

 main(){
  int n;
  cin>>n;
  vector<ll> a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  
  vector<vector<int>> flag(n,vector<int>(n,false));
  cout<<dfs(a,flag)<<endl;
  return 0;
}



Measured memory_bytes: 3212
class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

n,m = map(int,input().split())

M = 1
u = Unionfind(n+1)
for i in range(m):
    a,b = map(int,input().split())
    u.union(a,b)
    M = max(M,u.size(a))
print(M)

Measured memory_bytes: 14544
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp11
{
    class Class1
    {
        static void Main()
        {
            string[] S = Console.ReadLine().Split();

            int A = int.Parse(S[0]);
            int B = int.Parse(S[1]);
            int ans;

            if (!(A < 10 & B < 10))
                ans = -1;
            else
                ans = A * B;
            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define ll long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) // rep(i, 1, 5) --> {1,2,3,4} // rep(i, 5, 1) --> {4,3,2,1} // rep(it, end(v), begin(v)) --> *it

using namespace std;

int main()
{
    int x;
    cin >> x;
    int a = x / 500;
    int res = x % 500;
    int b = res / 5;
    cout << a * 1000 + b * 5;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#define N 501
int n,M[N][N];
int t=0,A[N],B[N],C[N];
//黒が２、グレーが１、白が０
void dfs(int);

int main(){
  int a,b,c;
  int i,j;
  scanf("%d", &n);
  for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
      M[i][j] = 0;
    }
  }

  for(i = 0; i < n; i++){
    scanf("%d %d", &a, &b);
    a--;
    for(j = 0; j < b; j++){
      scanf("%d", &c);
      c--;
      M[a][c] = 1;
    }
  }

  for(i = 0; i < n; i++)
    A[i] = 0;

  for(i = 0; i < n; i++){
    if( A[i] == 0)
      dfs(i);
  }

  for( i = 0; i < n; i++)
    printf("%d %d %d\n", i+1, B[i], C[i]);

  return 0;
}

void dfs(int i){
  int j;
  A[i] = 1;
  t++;
  B[i] = t;
  for( j = 0; j < n; j++){
    if( M[i][j] == 0)
      continue;
    if( A[j] == 0)
      dfs(j);
  }
  A[i] = 2;
  C[i] = ++t;
}




Measured memory_bytes: 2100
#include <stdio.h>

int main()
{
    char s[100000];
    int n = scanf("%s",s);
    int n0 = 0, n1 = 0;
    for (int i = 0; i != strlen(s); ++i)
    {
        if (s[i] == '0')
            ++n0;
        else
            ++n1;
    }
    int answer = (n0 < n1 ? n0 : n1) * 2;
    printf("%d", answer);
    return 0;
}


Measured memory_bytes: 256
use std::io::Read;
use std::collections::HashMap;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

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

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();
    let k: usize = iterator.next().unwrap().parse().unwrap();

    let mut map: HashMap<usize, usize> = HashMap::new();
    for _ in 0..n {
        let a: usize = iterator.next().unwrap().parse().unwrap();
        let b: usize = iterator.next().unwrap().parse().unwrap();
        *map.entry(a).or_insert(0) += b;
    }

    let mut keys: Vec<usize> = map.keys().map(|it| *it).collect();
    keys.sort();

    let mut sum: usize = 0;
    for key in keys {
        let count = map.get(&key).unwrap();
        sum += *count;
        if sum >= k {
            return key.to_string();
        }
    }

    unreachable!();
}


Measured memory_bytes: 14240
N,M = map(int,input().split())
div = []
for i in range(2,int(M**(1/2))+2):
    cur = 0
    while M%i==0:
        M//=i
        cur += 1
    if cur >=1:
        div.append(cur)
if M>1:div.append(1)
div.sort()
mod = 10**9+7
frac = [1]*(N+50)
num=len(frac)
for i in range(num-1):
    frac[i+1] = frac[i]*(i+1)%mod
finv = [1]*(N+50)
finv[-1] = pow(frac[-1],mod-2,mod)
ans = 1
for i in range(1,num):
    finv[num-1-i] = finv[num-i]*(num-i)%mod
for i in div:
    ans  =ans*frac[N+i-1]*finv[N-1]*finv[i]%mod
print(ans)

Measured memory_bytes: 66752
N = int(input())
A = list(map(int, input().split()))

x = A[0]
y = sum(A[1:])
ans = abs(x - y)

for i in range(1, N - 1):
    x += A[i]
    y -= A[i]
    ans = min(ans, abs(x - y))

print(ans)

Measured memory_bytes: 24812
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
 
using namespace std;
 
int n, a[200100];
 
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
 
    long long ans = 0;
 
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {
            int st = j + 1;
            int dr = n;
            while (st <= dr) {
                int mid = (st + dr) / 2;
                if (a[mid] < a[i] + a[j])
                    st = mid + 1;
                else dr = mid - 1;
            }
 
            ans += (dr - (j + 1) + 1);
        }
 
    cout << ans;
    return 0;
}

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

int main() {
  int h,w;
  cin>>h>>w;
  std::vector<string>v(h+2);
  v[0]="agdsfgjjklajkadsjkfjaksdgkjfadgjkdfjkl;fajsdjlkgsakfjsajkflhjhafglasfldsjfhsadhflaskhflsahflhdslghaghlas";
  v[h]="agdsfgjjklajkadsjkfjaksdgkjfadgjkdfjkl;fajsdjlkgsakfjsajkflhjhafglasfldsjfhsadhflaskhflsahflhdslghaghlas";
  for(int i=1;i<h+1;i++)cin>>v[i];
  int a=0;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
    if(v[i][j]=='#'&&v[i-1][j]!='#'&&v[i+1][j]!='#'&&v[i][j-1]!='#'&&v[i][j+1]!='#')a=1;
}}
if(a==0)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h> 
#define ll long long
#define pb push_back
#define mp make_pair
#define mod 1000000007
using namespace std;
char a[1001][1001];
ll gcd(ll a,ll b) 
{ 
	if (a == 0) 
		return b; 
	return gcd(b % a, a); 
} 
bool isprime(ll n)
{
    for(ll i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
            return false;
    }
    return true;
}
ll dp[1001][1001]={0};
/*ll ways(ll h,ll w)
{
	//cout<<h<<" "<<w<<endl;
	if(h==0&&w==0)
		return 1;
	if(dp[h][w]!=0)
		return dp[h][w];
	ll ans1=0,ans2=0,ans;
	if(w-1>=0&&a[h][w-1]=='.')
	ans1=ways(h,w-1)%mod;
	if(h-1>=0&&a[h-1][w]=='.')
	ans2=ways(h-1,w)%mod;
	ans=(ans1%mod+ans2%mod)%mod;
	dp[h][w]=ans;
	return ans;
}*/
int main()
{
	ll h,w,i,j;
	cin>>h>>w;
	for(i=0;i<h;i++)
	{
		for(j=0;j<w;j++)
			cin>>a[i][j];
	}
	for(i=0;i<h;i++)
	{
		for(j=0;j<w;j++)
		{
			if(i==0&&j==0)
			dp[i][j]=1;
			else if(i==0&&a[i][j]=='.')
			dp[i][j]=dp[i][j-1]%mod;
			else if(j==0&&a[i][j]=='.')
			dp[i][j]=dp[i-1][j]%mod;
			else if(a[i][j]=='.')
			dp[i][j]=(dp[i-1][j]%mod+dp[i][j-1]%mod)%mod;
		}
	}
	cout<<dp[h-1][w-1];
	return 0;
}

Measured memory_bytes: 9088
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int gcd(int x,int y){
  return y==0?x:gcd(y,x%y);
}

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

  if(s[0]!=t[0]){
    cout<<-1<<endl;
    return 0;
  }

  ll z=gcd(n,m);
  ll a=n/z;
  ll b=m/z;
  ll lcm=z*a*b;

  bool flag=0;
  for(ll i=0;i*a<n&&i*b<m;i++){
    if(s[i*a]!=t[i*b]) flag=1;
  }
  if(flag) cout<<-1<<endl;
  else cout<<lcm<<endl;

  /*if(n==m){
    if(s==t) cout<<n<<endl;
    else cout<<-1<<endl;
  }else if(n<m){
    if(z==1) cout<<lcm<<endl;
    else{
      bool flag=0;
      for(int i=0;i<n;i++){
        if(s[i]!=t[i*b]) flag=1;
      }
      if(flag) cout<<-1<<endl;
      else cout<<lcm<<endl;
    }
  }else{
    if(z==1) cout<<lcm<<endl;
    else{
      bool flag=0;
      for(int i=0;i<m;i++){
        if(t[i]!=s[i*a]) flag=1;
      }
      if(flag) cout<<-1<<endl;
      else cout<<lcm<<endl;
    }
  }*/


  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,K;
  cin >> N >> K;
  vector<int> A(N);
  for(int i = 0; i < N; ++i) cin >> A[i];
  vector<bool> first(K+1);
  for(int i = 1; i <= K; ++i){
    for(int j : A){
      if(i >= j and first[i-j] == false){
        first[i] = true;
	break;
      }
    }
  }
  if(first[K]) cout << "First";
  else cout << "Second";
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
typedef pair<int, int> P;
typedef pair<int, P> S;
int M, N, K;
int to_id(string s){
  if(s[0] == 'C'){
    string num = s.substr(1);
    int id = atoi(num.c_str());
    return id - 1;
  }else if(s[0] == 'L'){
    string num = s.substr(1);
    int id = atoi(num.c_str());
    return M + id - 1;
  }else if(s[0] == 'H'){
    return N + M;
  }else if(s[0] == 'D'){
    return N + M + 1;
  }else{
    assert(false);
  }
}

int main(){
  while(cin >> M >> N >> K && N){
    int D; cin >> D;
    vector<int> cal(M);
    REP(i, M) cin >> cal[i];
    int dist[200][200] = {};
    REP(i, N + M + 2) REP(j, N + M + 2) dist[i][j] = INF;
    REP(i, D){
      string a, b; cin >> a >> b;
      int c; cin >> c;
      c *= K;
      int u = to_id(a);
      int v = to_id(b);
      dist[u][v] = dist[v][u] = c;
    }
    priority_queue<S, vector<S>, greater<S> > que;
    int ans[200][1 << 6];
    REP(i, N + M + 2) REP(j, 1 << M) ans[i][j] = INF;
    que.push(S(0, P(N + M, 0)));
    ans[N + M][0] = 0;
    int answer = INF;
    while(!que.empty()){
      int u = que.top().second.first;
      int s = que.top().second.second;
      int c = que.top().first;
      que.pop();
      //printf("u = %d s = %d c = %d\n", u, s, c);
      if(ans[u][s] > c) continue;
      if(u == N + M + 1){
        answer = min(answer, c);
      }
      REP(i, M) if(dist[u][i] < INF && !(s >> i & 1)){
        int ns = s | (1 << i);
        int nc = c + dist[u][i] - cal[i];
        if(nc < ans[i][ns]){
          ans[i][ns] = nc;
          que.push(S(nc, P(i, ns)));
        }
      }
      REP(i, N + 2) if(dist[u][i + M] < INF){
        int nc = c + dist[u][i + M];
        if(nc < ans[i + M][s]){
          ans[i + M][s] = nc;
          que.push(S(nc, P(i + M, s)));
        }
      }
    }
    cout << answer << endl;
  }
  return 0;
}

Measured memory_bytes: 1500
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<numeric>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<functional>

#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
string str;
int l;
int ansi;
int ansj;
using namespace std;

int main(){
	int t, l;
	while(cin >> t >> l, t || l){
		vector<int> a;
		a.pb(t);
		int index = 0, j;
		bool flag = true;
		while(flag){
			vector<int> dig(l);
			int tmp = a[index];
			for(int i = 0;i <l;i++){
				dig[i] = tmp % 10,
						tmp /= 10;
			}
			sort(dig.begin(),dig.end());

			int maxa = 0, mina = 0;
			for(int i =0;i <l;i++){
				maxa *= 10;
				mina *= 10;
				maxa += dig[l-i-1];
				mina += dig[i];
			}

			a.pb(maxa - mina);
			index++;

			for(int i =0;i <index;i++){
				if(a[index] == a[i]){
					flag = false;
					j = index;
					ansi = i;
					break;
				}
			}
		}
		cout << ansi << ' ' << a[index] << ' ' << index-ansi << endl;
	}
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<pair<int,int>> vec(n);
    int mx=-2e9-10;
    int mx2=-2e9-10;
    int mn=2e9+10;
    int mn2=2e9+10;
    for(auto &e:vec)
    {
        cin>>e.first>>e.second;
        mx=max(mx,e.first+e.second);
        mn=min(mn,e.first+e.second);
        mx2=max(mx2,e.first-e.second);
        mn2=min(mn2,e.first-e.second);
    }
    cout<<max(mx-mn,mx2-mn2)<<"\n";
}

Measured memory_bytes: 4844
import Data.List
import Data.Int

modulus :: Int64
modulus = 10^9 + 7

addMod, subMod, mulMod :: Int64 -> Int64 -> Int64
addMod x y
  | x + y >= modulus = x + y - modulus
  | otherwise        = x + y

subMod x y
  | x - y < 0 = x - y + modulus
  | otherwise = x - y

mulMod x y = (x * y) `rem` modulus

powMod :: Int64 -> Int64 -> Int64
powMod n p
  | p == 0    = 1
  | odd p     = n * powMod n (p-1) `mod` modulus
  | otherwise = let t = powMod n (p `div` 2)
                 in (t^2) `mod` modulus

modInv :: Int64 -> Int64
modInv n = powMod n (modulus - 2)

productMod :: [Int64] -> Int64
productMod = foldr mulMod 1

nCrMod :: Int64 -> Int64 -> Int64
nCrMod n r = productMod [(n-r+1)..n] `mulMod` modInv (productMod [1..r])

main :: IO ()
main = do
    [n,a,b] <- map read . words <$> getLine :: IO [Int64]
    print $ (powMod 2 n - 1) `subMod` nCrMod n a `subMod` nCrMod n b

Measured memory_bytes: 7420
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int N = 1e6 + 6;
pair <int, int> a[N];
int main(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++ i){
        int x, l;
        cin >> x >> l;
        a[i].fi = x + l, a[i].se = x - l;
    }
    sort(a + 1, a + 1 + n);
    int ans = 0;
    for (int i = 1, r = -(2e9); i <= n; ++ i)
        if (a[i].se >= r)
            ++ ans, r = a[i].fi;
    cout << ans << endl;
}


Measured memory_bytes: 1024
s=[i for i in input()];a,b=0,0;c,d=list(s),list(s)
for i in range(len(s)):
  if i%2==0:
    if c[i]!="0":c[i]=0;a+=1
    if d[i]!="1":d[i]=0;b+=1
  else:
    if c[i]!="1":c[i]=0;a+=1
    if d[i]!="0":d[i]=0;b+=1
print(min(a,b))

Measured memory_bytes: 5532
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
inline void read(int &x){
	x=0;char ch=getchar();int f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}x*=f;
}
inline void judge(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
}
const int maxn=2005;
int sum[maxn][maxn],suml[maxn][maxn],sumr[maxn][maxn],sumu[maxn][maxn],sumd[maxn][maxn];
int tot[maxn][maxn];
char s[maxn][maxn];
int n,m,Q;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int main(){
	read(n);read(m);read(Q);
	rep(i,1,n)scanf("%s",s[i]+1);
	rep(i,1,n){
		rep(j,1,m)if(s[i][j]=='1'){
			tot[i][j]=(s[i][j]=='1');	
			suml[i][j]=(s[i][j-1]=='1');
			sumr[i][j]=(s[i][j+1]=='1');
			sumu[i][j]=(s[i-1][j]=='1');
			sumd[i][j]=(s[i+1][j]=='1');
			sum[i][j]=suml[i][j]+sumu[i][j];
		}
	}
	rep(i,1,n)rep(j,1,m){
		tot[i][j]+=tot[i-1][j]+tot[i][j-1]-tot[i-1][j-1];
		sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
		suml[i][j]+=suml[i][j-1];
		sumr[i][j]+=sumr[i][j-1];
		sumu[i][j]+=sumu[i-1][j];
		sumd[i][j]+=sumd[i-1][j];
	}
	while(Q--){
		int lx,ly,rx,ry;
		read(lx);read(ly);read(rx);read(ry);
		int ans=0;
		ans=tot[rx][ry]-tot[lx-1][ry]-tot[rx][ly-1]+tot[lx-1][ly-1];
		if(rx-lx>0&&ry-ly>0)
			ans-=(sum[rx][ry]-sum[lx][ry]-sum[rx][ly]+sum[lx][ly]);
		ans-=suml[lx][ry]-suml[lx][ly];
		ans-=sumu[rx][ly]-sumu[lx][ly];
		printf("%d\n",ans);
	}
}

Measured memory_bytes: 99968
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <fstream>
#define ni(n) scanf("%d", &n)
#define nl(n) scanf("%lld", &n)
#define nai(a,n) for (int i = 0; i < (n); i++) ni((a)[i])
#define nal(a,n) for (int i = 0; i < (n); i++) nl((a)[i])
#define case(t) printf("Case #%d: ", (t))
#define pii pair<int, int>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define f first
#define s second
typedef long long ll;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e5 + 5;
const double eps = 1e-9;
using namespace std;
int a[MAXN];

int main()
{
    int n;
    ni(n);
    a[0] = 0;
    for (int i = 1; i <= n; i++)
        ni(a[i]);
    a[n + 1] = 0;
    int ans = 0;
    for (int i = 1; i <= n + 1; i++)
        ans += abs(a[i] - a[i - 1]);
    for (int i = 1; i <= n; i++)
    {
        int tmp = ans - abs(a[i] - a[i - 1]) - abs(a[i + 1] - a[i]) + abs(a[i + 1] - a[i - 1]);
        printf("%d\n", tmp);
    }
    return 0;
}


Measured memory_bytes: 1664