akhauriyash/Code-Regression huggingface dataset:
from string import ascii_lowercase as AL
n = int(input())
Slist = dict()
for i in range(len(AL)):
    Slist[AL[i]] = 51
for j in range(n):
    S = input()
    for i in range(len(AL)):
        Tar =AL[i]
        Slist[Tar] = min(Slist[Tar],S.count(Tar))
Answer = ''
for i in range(len(AL)):
    Num = Slist[AL[i]]
    Answer += AL[i]*Num
print(Answer)

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

#ifndef M_PI
#define M_PI 3.14159265358979
#endif
#define deg_to_rad(deg) (((deg) / 360) * 2 * M_PI)
#define rad_to_deg(rad) (((rad) / 2 / M_PI) * 360)

using namespace std;

typedef long long ll;
typedef vector<long long> vll;
typedef pair<long long, long long> pll;

const ll INF = 1e15;
const ll MOD = 1e9 + 7;

int main() {
    ll i, j, k;
    ll N;
    cin >> N;
    int digit = 1;
    vector<char> name;
    ll n = N;
    while(1) {
        ll d = (ll)pow(26, digit);
        if(n > d) {
            n -= d;
            digit++;
            continue;
        }
        break;
    }
    n--;
    for(ll di = digit; di > 0; di--) {
        ll d = (ll)pow(26, di - 1);
        ll s = n / d;
        n %= d;
        name.push_back('a' + s);
    }
    for(i = 0; i < digit; i++) {
        cout << name[i];
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 4028
#include <stdio.h>

main(void)
{
  char *pVal = (char *) malloc(sizeof(char) * 4);
  gets(pVal);

  int val = 0;
  int i = 0;
  while ('0' <= pVal[i])
  {
    val = val * 10 + pVal[i] - '0';
    i ++; 
  }

  int pages_duplex = (val+1) >> 1;
  printf("%d", pages_duplex);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N;
    cin >> N;
    int count = 0;
    int m = 1;
    int a;
    for(int i = 0;i < N;i++) {
       cin >> a;
       if(a == m) {
           m++;
       } 
       else {
           count++;
       }
    }
    if(m == 1) {
        if(N == 1) cout << 0 << endl;
        else cout << -1 << endl;
    }
    else {
        cout << N - m + 1 << endl;
    }
}

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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n, sum = 0, cnt1 = 0, cnt2 = 0;
	cin >> n;
	vector<ll> v(2 * n);
	for (ll i = 0; i < 2 * n; i++) {
		cin >> v.at(i);
	}
	sort(v.begin(), v.end(), greater<ll>());
	while (cnt1 < n) {
		cnt2++;
		sum += v[cnt2];
		cnt2++;
		cnt1++;
	}
	cout << sum << endl;
	return 0;
}


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

public class Main {

	public static void main(String[] args) {
		new Main().run();
	}

	boolean[][] M;
	int n;
	boolean color[];
	int d[];
	int f[];

	private void run() {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		M = new boolean[n][n];
		color = new boolean[n];
		d = new int[n];
		f = new int[n];
		for (int i = 0; i < n; i++) {
			int u = scanner.nextInt();
			int k = scanner.nextInt();
			u--;
			for (int j = 0; j < k; j++) {
				int v = scanner.nextInt();
				v--;
				M[u][v] = true;
			}
		}
		bfs(0);
	}

	private void bfs(int s) {
		Deque<Integer> deque = new ArrayDeque<Integer>();
		deque.offer(s);
		int count = 0;
		Arrays.fill(d, -1);
		d[0] = 0;
		color[0] = true;
		while (!deque.isEmpty()) {
			int size = deque.size();
			for (int i = 0; i < size; i++) {
				int q = deque.poll();
				d[q] = count;
				for (int j = 0; j < n; j++) {
					if (M[q][j] && !color[j]) {
						color[j] = true;
						deque.offer(j);
					}
				}
			}
			count++;

		}
		for (int u = 0; u < n; u++) {
			System.out.printf("%d %d\n", u + 1, d[u]);
		}
	}

	int tt = 1;

}

Measured memory_bytes: 20920
#include <iomanip>
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

int main(void) {
  ios::sync_with_stdio(false);
  string T;
  cin >> T;
  int N = T.size();
  rep(i, N) {
    if (T[i] == '?') T[i] = 'D';
  }
  cout << T << endl;
  return 0;
}


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

pair<bool, long> B(long X, long A) {
  long N = A*A*A*A*A - X;
  long B = lround(pow((long double)(abs(N)), 0.2L));
  if (N < 0) B = -B;
  int correct = (B*B*B*B*B == N);
  return make_pair(correct, B);
}

int main() {
  long X; cin >> X;
  for (long A = 0; true; A++) {
    pair<bool, long> res;
    res = B(X, A);
    if (res.first) { cout << A << " " << res.second << endl; break; }
    res = B(X, -A);
    if (res.first) { cout << -A << " " << res.second << endl; break; }
  }
}

Measured memory_bytes: 3688
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Random;
import java.util.StringTokenizer;

public final class Main {

    public static void main(String[] args) {
        final FastScanner fs = new FastScanner();
        final int a = fs.nextInt();
        final int b = fs.nextInt();
        final int c = fs.nextInt();
        System.out.println((a * b) / 2);
    }

    static final class Utils {
        public static void shuffleSort(int[] arr) {
            shuffle(arr);
            Arrays.sort(arr);
        }

        public static void shuffleSort(long[] arr) {
            shuffle(arr);
            Arrays.sort(arr);
        }

        public static void shuffle(int[] arr) {
            final Random r = new Random();

            for (int i = 0; i <= arr.length - 2; i++) {
                final int j = i + r.nextInt(arr.length - i);
                swap(arr, i, j);
            }
        }

        public static void shuffle(long[] arr) {
            final Random r = new Random();

            for (int i = 0; i <= arr.length - 2; i++) {
                final int j = i + r.nextInt(arr.length - i);
                swap(arr, i, j);
            }
        }

        public static void swap(int[] arr, int i, int j) {
            final int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }

        public static void swap(long[] arr, int i, int j) {
            final long t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }

        private Utils() {}
    }

    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        private String next() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    //noinspection CallToPrintStackTrace
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

        int[] nextIntArray(int n) {
            final int[] a = new int[n];
            for (int i = 0; i < n; i++) { a[i] = nextInt(); }
            return a;
        }

        long[] nextLongArray(int n) {
            final long[] a = new long[n];
            for (int i = 0; i < n; i++) { a[i] = nextLong(); }
            return a;
        }
    }
}


Measured memory_bytes: 32700
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
// Welcome to my source code!

int main() {
    int nums[32] = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
    int k;
    cin >> k;
    cout << nums[k - 1] << endl;
}

Measured memory_bytes: 256
//#include "pch.h"
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <stdio.h>
#include <vector>
#include <time.h>
#include <iomanip>
#include <thread>
#include <atomic>
#include <mutex>
#include <future>
#define double long double
#define int long long
#define mii map<int,int>
#define pii pair<int,int>
#define low lower_bound
#define upp upper_bound
#define mod 1000000007 //10^9+7
#define inf 10000000000000000 //10^16
#define rep(i,n) for(int i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()
#define vsort(vec) sort(all(vec))
#define vrever(vec) reverse(all(vec));
#define vunsort(vec) vsort(vec); vrever(vec);
#define bisea binary_search
#define cend cout<<endl;
#define F first
#define S second
using namespace std;
signed main() {
	string s;
	cin >> s;
	int n = s.size();
	stack<char>st;
	rep(i, n) {
		if (i != 0 && !st.empty() && st.top() != s[i]) {
			st.pop();
		}
		else {
			st.push(s[i]);
		}
	}
	cout << n-st.size() << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
#define pb push_back
#define mp make_pair
#define ms memset
#define FOR(i, a, b) for(int i = a; i <= b; i++)

int main()
{
    string S, T; cin >> S >> T;
    int cnt = 0; int n = S.size();
    FOR(i,0,n-1){
        if (S[i] != T[i]) cnt++;
    }
    cout << cnt << '\n';
    return 0;
}

Measured memory_bytes: 3852
#include <iostream>
using namespace std;
int main()
{
	int n;
	int x;
	int L[200];
	int D[200];
	cin >> n;
	cin >> x;
	for (int i = 0; i < n; i++)
		cin >> L[i];
	int sum = 1;
	D[0] = 0;
	for (int i = 1; i < n+1; i++)
	{
		D[i] = D[i - 1] + L[i - 1];
		if (D[i] <= x)sum++;
		else break;
	}
	cout << sum;
}

Measured memory_bytes: 256
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define d long double
#define pii pair<int,int>
#define pb push_back
#define pf push_front
#define cases int t;cin>>t;while(t--)
#define N 100003
#define M 103
#define inf LLONG_MAX
//int mod=1e9+7;
//int mod=998244353;

signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    int i,j;
    int dp[n+2];
    fill(dp,dp+n+2,0);
    for(i=0;i<=n-2;++i)
    {
        if(s[i]=='A' && s[i+1]=='C')
        {
            dp[i+1]++;
        }
    }
    for(i=1;i<=n;++i)
        dp[i]+=dp[i-1];

    while(q--)
    {
        int l,r;
        cin>>l>>r;
        cout<<dp[r-1]-dp[l-1]<<"\n";
    }

    return 0;
}


Measured memory_bytes: 1872
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.LinkedHashSet;

public class Main {

	public static void main(String[] args) {
	int N;
  Scanner sc = new Scanner(System.in);
    N = sc.nextInt();
    int i=0;
    ArrayList<String> strList = new ArrayList<String>();
    do {
    strList.add(sc.next());
    i++;
}while(i<N);
    List<String> listA= strList;
    List<String> listB = new ArrayList<String>(new LinkedHashSet<>(listA));
	
    System.out.println(listB.size());
	sc.close();
	
	
	}}

Measured memory_bytes: 73128
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using ld = long double;
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rep3(i, n) for (int i = 1; i < (int)(n+1); i++)
#define rep4(i, s, n) for (int i = (s); i < (int)(n+1); i++)
#define repr(i,n) for (int i = (n-1); i>=0;i--)
#define repr3(i,n) for(int i = (n);i>0;i--)
#define stlen(s) ll s.size()-1
#define all(v) v.begin(), v.end()
#define cout(n) cout<<std::fixed<<std::setprecision(n)
using Graph = vector<vector<int>>;
#define INF1  100012101;
#define INF2  LLONG_MAX;
#define PI  3.14159265358979323846;
 


int main(){
    ll N;
    cin>>N;
    ll ans=1;
    rep3(i,N){
        ans*=i;
        ans%=((ll)pow(10,9)+7);
    }
    cout<<ans<<endl;
return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<map>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<set>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
#define INF 1000000100
#define rep(i,n) for (int i=0;i<n;i++)

int main(){
    int N;
    cin >> N;
    ll sum=0;
    rep(i,N) sum+=i;
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3112
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
#import numpy as np
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#N = int(input())
#S = str(input())
  
MOD = pow(10, 9) + 7
n, a, b = map(int, input().split())
 
#   (2^n - nCa - nCb) mod MOD
# = ( (2^n - 1 mod MOD) - (nCa mod MOD) - (nCb mod MOD ) ) mod MOD
#   (nCr mod MOD) = ( n*(n-1)*...*(n-r+1) * (a!)^-1 ) mod MOD
# = ( (n mod MOD) * ((n-1) mod MOD) * ... * ((n-r+1) mod MOD) * (r!)^(MOD-2) )  mod MOD

a = min(a, n-a)
b = min(b, n-b)
rMAX = max(a, b)

#分子のmod
nCr_Mol_ModList = [1 for _ in range(rMAX+1)]
#分母（rの階乗）のmod
fac_ModList = [1 for _ in range(rMAX+1)]
nCr_Mol_ModList[1] = n % MOD
fac_ModList[1] = 1 % MOD
for i in range(2, rMAX+1) :
  nCr_Mol_ModList[i] = (nCr_Mol_ModList[i-1] * (n-i+1)) % MOD
  fac_ModList[i] = (fac_ModList[i-1] * i) % MOD

#(2^n - 1 mod MOD) = X
#(nCa mod MOD) = Y
#(nCb mod MOD ) = Z とする

X = pow(2,n,MOD)-1%MOD
Y = ( nCr_Mol_ModList[a] * pow(fac_ModList[a], MOD-2, MOD) )%MOD
Z = ( nCr_Mol_ModList[b] * pow(fac_ModList[b], MOD-2, MOD) )%MOD

ans = (X - Y - Z) % MOD
print (ans)


Measured memory_bytes: 19444
#include <stdio.h>
#include <err.h>

#define MAX 101

int fillnum( char table[MAX][MAX], int i, int j, int h, int w, char c )
{
	if ( i > h || j > w || i < 0 || j < 0 ) {
		return 0;
	}

	if ( table[i][j] != c ) { return 0; } 

	table[i][j] = 0;

	fillnum( table, i-1, j, h, w, c );
	fillnum( table, i, j-1, h, w, c );
	fillnum( table, i+1, j, h, w, c );
	fillnum( table, i, j+1, h, w, c );

	return 0;
}


int search( char table[MAX][MAX], int h, int w )
{
	int num = 0;
	for ( int i = 0 ; i < h ; i++ ) {
		for ( int j = 0 ; j < w ; j++ ) {
			if ( table[i][j] == 0 ) {
				continue;
			} else {
				fillnum( table, i, j, h, w, table[i][j] );
				num++;
			}
		}
	}
	return num;
}

int main()
{
	int H = 0, W = 0, i = 0, k = 0;
	int ans = 0;
	char str[MAX];
	char farm[MAX][MAX];

	while ( scanf( "%d %d", &H, &W ) == 2 ) {
		if ( H == 0 && W == 0 ) { break; }
		for ( i = 0 ; i < H ; i++ ) {
			scanf( "%s", str );
			for ( k = 0 ; k < W ; k++ ) {
				farm[i][k] = str[k];
			}
		}

		/*for ( i = 0 ; i < H ; i++ ) {
			for ( k = 0 ; k < W ; k++ ) {
				printf( "%2c", farm[i][k] );
			}
			printf( "\n" );
		}*/
		ans = search( farm, H, W );
		printf( "%d\n", ans );
		/*for ( i = 0 ; i < H ; i++ ) {
			for ( k = 0 ; k < W ; k++ ) {
				printf( "%2d", farm[i][k] );
			}
			printf( "\n" );
		}*/
	}
	return 0;
}



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

using namespace std;
using ll = long long;

#define FOR(i,m,n) for(ll (i)=(m); (i)<(ll)(n); ++(i))
#define REP(i,n) FOR(i,0,n)
#define ALL(a) (a).begin,(a).end

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s; cin >> s;
  string res;
  if(s == "ABC") res = "ARC";
  else res = "ABC";
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 3616
n, k = map(int, input().split())
mod = 998244353
lr = [list(map(int, input().split())) for _ in range(k)]

dp = [0] * (n + 10)
dp[1] = 1
cumsum = [0] * (n + 10)
cumsum[1] = 1

for i in range(2, n + 1):
    for l, r in lr:
        if l >= i:
            continue

        ll = max(1, i - r)
        rr = i - l
        dp[i] += cumsum[rr] - cumsum[ll - 1]
        dp[i] %= mod
    cumsum[i] = cumsum[i - 1] + dp[i]
    cumsum[i] %= mod

print(dp[n] % mod)


Measured memory_bytes: 24556
def f():
 for c in range(n):
  for d in a[c+1:]:
   for p in([0,1,2,3,4,5],[1,5,2,0,4,3],[2,1,5,3,0,4],[3,0,2,5,4,1],[4,1,0,3,5,2],[5,1,4,3,2,0]):
    f=[d[i]for i in p]
    if f[::5]==a[c][::5]:
     f=f[1:5]*2
     for k in range(4):
      if f[k:k+4]==a[c][1:5]:return"No"
 return"Yes"
import sys
b=0
n=int(input())
a=[e.split()for e in sys.stdin]
for b in a:b[3:5]=b[4],b[3]
print(f())


Measured memory_bytes: 5608
#提出用
n,m,q = list(map(int, input().split()))

a=[]
b=[]
c=[]
d=[]

for i in range(q):
    aa,bb,cc,dd = list(map(int, input().split()))
    a.append(aa)
    b.append(bb)
    c.append(cc)
    d.append(dd)

ans = 0

def dfs(la):
    global ans
    if len(la)==n+1:
        sum_d=0
        #print(la)
        #print(ans)
        for i in range(q):
            if la[b[i]] - la[a[i]] == c[i]:
                sum_d += d[i]
        if sum_d > ans:
            ans = sum_d
        return
    
    la.append(la[-1])
    while(la[-1]<=m):
        dfs(la.copy())
        la[-1] += 1
        

dfs([1])
print(ans)

Measured memory_bytes: 73344
#include <iostream>
#include <vector>


using namespace std;

int main(void)
{
    int n;
    bool flag = true;
    
    cin >> n;
    int box[n];
    for (size_t i = 0; i < n; i++)
    {
        cin >> box[i];
        if(box[i]%2 == 0){
            if(box[i]%3 == 0 || box[i]%5 == 0){
                flag = true;
            }
            else {
                flag = false;
                break;
            }
        }
    }
    

    if(flag == true) cout << "APPROVED" << endl;
    else cout << "DENIED" << endl;


    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<string>
#include<algorithm>
#include<vector>
#include<utility>
#include<tuple>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<bitset>
#include<math.h>
using namespace std;
using ll = int64_t;
using Graph = vector<vector<int> >;
const ll M = 1000000007;

int main(){
    int n,l;
    cin >> n >> l;
    int a[n];
    for(int i=0;i<n;i++){
        a[i] = l+i;
    }
    int c=1;
    if(a[0]<0) c=0;
    int m = abs(a[0]);
    for(int i=0;i<n;i++){
        if(m>abs(a[i])){
            if(a[i]>=0){
                c=1;
            }else{
                c=0;
            }
            m = abs(a[i]);
        }
    }

    int sum =0;
    for(int i=0;i<n;i++){
        sum += a[i];
    }
    if(c){
        cout << sum-m << endl;
    }else{
        cout << sum+m << endl;
    }
}

Measured memory_bytes: 3592
/* vo00_04.cpp */
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
using namespace std;

int is_double(double dl);
double m_round(double d);
int dmax(int d1, int d2) { return (d1 < d2) ? d2 : d1; }

int main()
{
	double x1, y1, a1;
	double x2, y2, a2;
	double x, y;
	bool f_x, f_y;

	while (true) {
		cin >> x1 >> y1 >> a1 >> x2 >> y2 >> a2;
		if (cin.eof()) break;
		


		f_x = false; f_y = false;

		int p = dmax(dmax(is_double(x1), is_double(x2)), dmax(is_double(y1), is_double(y2)));
		if (p) { p *= 10; x1 *= p; x2 *= p; y1 *= p; y2 *= p; }

		if (x1 && x2 && (y1 || y2)) {
			int temp = x1;
			x1 *= x2; y1 *= x2; a1 *= x2;
			x2 *= temp; y2 *= temp; a2 *= temp;

			double y3 = y2 - y1, a3 = a2 - a1;

			y = a3 / y3;
			f_y = true;
		}

		if (y1 && y2 && (x1 || x2)) {
			int temp = y1;
			x1 *= y2; y1 *= y2; a1 *= y2;
			x2 *= temp; y2 *= temp; a2 *= temp;

			double x3 = x2 - x1, a3 = a2 - a1;

			x = a3 / x3;

			f_x = true;
		}

		if (!f_x || !f_y) {
			// どちらかに0があれば
			if (!x1) { y = a1 / y1; f_y = true; }
			else if (!x2) { y = a2 / y2; f_y = true; }

			if (!y1) { x = a1 / x1; f_x = true; }
			else if (!y2) { x = a2 / x2; f_x = true; }

			if (f_x && !f_y) {

				if (!y1 && !y2) { y = 0; }

				else if (x1 && y1) { x1 *= x; a1 -= x1; y = a1 / y1; }
				else if (x2 && y2){ x2 *= x; a2 -= x2; y = a2 / y2; }

				f_y = true;
			}
			if (f_y && !f_x) {

				if (!x1 && !x2) { x = 0; }

				else if (y1 && x1) { y1 *= y; a1 -= y1; x = a1 / x1; }
				else if (y2 && x2) { y2 *= y; a2 -= y2; x = a2 / x2; }
				
				f_x = true;
			}
		}

		if (f_x && f_y) {
			x = m_round(x); y = m_round(y);
			printf("%.3lf %.3lf\n", x, y);
		}
	}

	return 0;
}

int is_double(double dl)
{
	dl = fabs(dl);
	int d = (int)dl;
	double temp = dl - (double)d;

	if (!temp) return 0;

	else {
		int i;
		for (i = 0; temp < 1; ++i) temp *= 10;

		return i;
	}
}

double m_round(double d)
{
	bool flag = false;
	if (d < 0) { flag = true; d = -d; }

	d *= 1000;
	d += 0.5;

	int t1 = (int)d;
	double t2 = d - (double)t1;
	d -= t2;

	d /= 1000;

	if (flag) { d = -d; }

	return d;
}

Measured memory_bytes: 1236
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;}
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;

//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};

const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod



signed main(){

    int N, K; cin >> N >> K;
    vec A(N); cin >> A;
    REP(i, N) A[i]--;

    map<int, int> cnt;
    cnt[0] += 1;
    int ans = 0;
    vec s(N + 1, 0);
    REP(i, N){
        s[i + 1] = (s[i] + A[i]) % K;
        if(i >= K - 1) cnt[s[i - (K - 1)]] -= 1; 
        ans += cnt[s[i + 1]];
        cnt[s[i + 1]] += 1;
    }
    Out(ans);

    return 0;
}


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

typedef long long LL;
typedef pair<int, int> PII;

typedef vector<int> VI;
typedef vector<VI> VVI;

typedef vector<bool> VB;
typedef vector<VB> VVB;

#define fst first;
#define snd second;
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) (x).begin(), (x).end()
#define RANGE(x, y, w, h) (0 <= (x) && 0 <= (y) && (x) < (w) && (y) < (h))
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, init, n) for (int i = (init); i < (n); i++)

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const int DX[] = {1,0,-1,0}, DY[] = {0,-1,0,1};

int N, M;
int R;
VI rs;

VVI seas;
VVI loads;

int solve() {
    // ????????????
    rep(k, N) {
        rep(i, N) {
            rep(j, N) {
                if (i == j || i ==k || k == j) continue;
                seas[i][j] = min(seas[i][j], seas[i][k] + seas[k][j]);
                loads[i][j] = min(loads[i][j], loads[i][k] + loads[k][j]);
            }
        }
    }
    // 8,000,000

//    cout << "????????????ok!" << endl;

    // dp[ri][where]
    VVI dp(R, VI(N, INF));
    dp[0][rs[0]] = 0;

    rep(ri, R - 1) {    // 1000
        rep(w, N) {     // 200
            if (dp[ri][w] == INF) continue;

            int s = rs[ri];
            int g = rs[ri + 1];

            dp[ri + 1][w] = min(dp[ri + 1][w], dp[ri][w] + loads[s][g]);

            int cost = dp[ri][w] + loads[s][w];
            rep(w2, N) {    // 200
                int cost2 = cost;
                cost2 += seas[w][w2];
                cost2 += loads[w2][g];
                dp[ri + 1][w2] = min(dp[ri + 1][w2], cost2);
            }
        }
    }
    // 40,000,000


    return *min_element(ALL(dp[R - 1]));
}

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

    while (cin >> N >> M, N) {
        seas = VVI(N, VI(N, INF));
        loads = VVI(N, VI(N, INF));
        rep(i, N) rep(j, N) {
            if (i != j) continue;
            seas[i][j] = 0;
            loads[i][j] = 0;
        }

        rep(i, M) {
            int x, y, t;
            char sl;
            cin >> x >> y >> t >> sl;
            --x; --y;

            bool is_sea = sl == 'S';

            (is_sea ? seas : loads)[x][y] = t;
            (is_sea ? seas : loads)[y][x] = t;
        }

        cin >> R;
        rs = VI(R);
        for (auto &r : rs) {
            cin >> r;
            --r;
        }

        cout << solve() << endl;
    }

    return 0;
}

Measured memory_bytes: 2368
#include <iostream>

int main() {
    int D;
    std::cin >> D;
    std::string result;
    if (D == 25) {
        result = "Christmas";
    } else if (D == 24) {
        result = "Christmas Eve";
    } else if (D == 23) {
        result = "Christmas Eve Eve";
    } else if (D == 22) {
        result = "Christmas Eve Eve Eve";
    }
    std::cout << result << std::endl;
    return 0;
}


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

int go( int a, int b )
{
    int temp;
    if( a < b ) { temp = a; a = b; b = temp; }
    if( a % b == 0 ) return b;
    return go( b, a % b );
}

int main(){
  int n,i,kotae=0;
  cin>>n;
  int a[n],b[n],c[n];
  for(i=0;i<n;i++){
    cin>>a[i];
  }
  b[0]=a[0];
  for(i=1;i<n;i++){
    b[i]=go(b[i-1],a[i]);
  }
  c[n-1]=a[n-1];
  for(i=n-2;i>=0;i--){
    c[i]=go(c[i+1],a[i]);
  }
  for(i=1;i<n-1;i++){
    kotae=max(go(b[i-1],c[i+1]),kotae);
  }
  cout<<max(kotae,max(b[n-2],c[1]));
}

Measured memory_bytes: 1408
import java.io.IOException;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
       Scanner sc = new Scanner(System.in);
       double r = sc.nextDouble();
       double x,y,z;
       x=Math.PI;
       y=2*r*x;
       z=r*r*x;
       System.out.printf("%f ",z);
       System.out.printf("%f\n",y);
	}

}

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;

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

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;

ll n,q;
const ll maxn=200005;
vll G[maxn];

ll dist[maxn];

void dfs(ll v, ll p){
  for(auto nv: G[v]){
    if(nv==p) continue;
    dist[nv]+=dist[v];
    dfs(nv,v);
  }
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  cin>>n>>q;
  rep(i,n-1){
    ll a,b; cin>>a>>b; a--,b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  rep(i,q){
    ll p,x; cin>>p>>x; p--;
    dist[p]+=x;
  }
  dfs(0,-1);
  rep(i,n){
    cout<<dist[i]<<endl;
  }
}

Measured memory_bytes: 24320
from collections import deque

def solve(n, q, a, b, p, x):
    E = [[] for i in range(n+1)]
    for a_i, b_i in zip(a, b):
        E[a_i].append(b_i)
        E[b_i].append(a_i)
    res = {i: 0 for i in range(1, n+1)}
    for j in range(q):
        res[p[j]] += x[j]
    used = [False] * (n+1)
    used[1] = True
    que = deque([1])
    while que:
        u = que.popleft()
        for v in E[u]:
            if not used[v]:
                used[v] = True
                res[v] += res[u]
                que.append(v)
    return " ".join(map(str, [res[i] for i in range(1,n+1)]))

n, q = map(int, input().split())
a = [0] * (n-1)
b = [0] * (n-1)
for i in range(n-1):
    a[i], b[i] = map(int, input().split())
p = [0] * q
x = [0] * q
for j in range(q):
    p[j], x[j] = map(int, input().split())
print(solve(n, q, a, b, p, x))

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

signed main() {
  int n, x;
  cin >> n >> x;

  vector<int> a(n);
  rep(i,n) cin >> a[i];

  sort(a.begin(),a.end());
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if(i == n - 1) {
      if(x == a[i]) ans++;
      break;
    }

    if(a[i] <= x) {
      x -= a[i];
      ans++;
    } else {
      break;
    }

  }
  cout << ans << endl;
}

Measured memory_bytes: 3596
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <math.h>
#include <stdlib.h>
#include <algorithm>

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

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

//INT_MAX	2,147,483,647 = 2*1.0e9

const int INF = 1e9;
int N;
int ABC[3];
vector<int> l;

int calcCost(vector<int>& _dstrb){
  int cost = 0;
  for(int j = 0; j < 3; j++){
    // Aについてやる
    int sum = 0;
    int cnt = 0;
    for(int i = 0; i < N; i++){
      if(_dstrb[i] == j){
        sum += l[i];
        cnt++;
      }
    }
    cost += 10 * (cnt -1);
    cost += abs(sum - ABC[j]);
    if(cnt == 0) cost = INF;
  }

  return cost;
}

void dfs(vector<int>& _dstrb, int _pos, int& _cmin){
  if(_pos == N){
    _cmin = min(calcCost(_dstrb), _cmin);
  } else {
    for(int i = 0; i < 4; i++){
      _dstrb[_pos] = i;
      dfs(_dstrb, _pos+1, _cmin);
    }
  }
}

int main(){

  cin >> N >> ABC[0] >> ABC[1] >> ABC[2];

  l.assign(N, 0);
  for(int i = 0; i < N; i++){
    cin >> l[i];
  }

  vector<int> dstrb(N, 0);
  int ans = INF;
  dfs(dstrb, 0, ans);

  cout << ans << endl;

  return 0;
}



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

class Program
{
    static void Main(string[] args)
    {
        var N = int.Parse(Console.ReadLine());

        var B = Console
            .ReadLine()
            .Split(' ')
            .Select(x => int.Parse(x))
            .ToArray();

        var A = new int[N];

        A[0] = B[0];
        A[N - 1] = B[N - 2];

        for(var i = 1; i < N - 1; i++)
        {
            if(B[i - 1] <= B[i])
            {
                A[i] = B[i - 1];
            }
            else
            {
                A[i] = B[i];
            }
        }

        Console.WriteLine(A.Sum());
    }
}

Measured memory_bytes: 13396
import java.util.Scanner;

public class Main{
    public static double toti(int a, int b){
        double c = a * b / 3.305785;
         
        return c;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        System.out.printf("%10f5",toti(sc.nextInt(),sc.nextInt()));
    }
}



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

int main() 
{ 
    int n;
    cin>>n;
    vector<vector<int>> arr(n,vector<int>(3));
    vector<vector<int>> dp(n,vector<int>(3));
    for(int i = 0;i<n;i++){
        cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
    }
    dp[0][0] = arr[0][0];
    dp[0][1] = arr[0][1];
    dp[0][2] = arr[0][2];
    vector<pair<int,int>> pr;
    pr.push_back({1,2});
    pr.push_back({0,2});
    pr.push_back({0,1});
    for(int i = 1;i<n;i++){
        for(int j = 0;j<3;j++){
            int  u = pr[j].first,v = pr[j].second;
            dp[i][j] = arr[i][j] + max(dp[i-1][u],dp[i-1][v]);
        }
    }
    cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
    return 0; 
} 

Measured memory_bytes: 11136
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <limits>
#include <sstream>
#include <typeinfo>
#include <cstdint>

using namespace std;

typedef long long ll;

int N;
ll X;
vector<ll> a;
vector<vector<ll>> memo;
vector<vector<bool>> done;

ll f(int x, int k)
{
	if (k == 0)
		return a[x];
	if (done[x][k])
		return memo[x][k];
	done[x][k] = true;
	auto& ret = memo[x][k];
	int idx = (x + N - k) % N;
	ret = min(f(x, k - 1), a[idx]);
	return ret;
}

int main() {
	cin >> N >> X;
	a.resize(N);
	memo.resize(N, vector<ll>(N));
	done.resize(N, vector<bool>(N));
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	ll ans = numeric_limits<ll>::max() / 3;
	for (int k = 0; k < N; k++) {
		ll tmp = k*X;
		for (int i = 0; i < N; i++) {
			tmp += f(i, k);
		}
		ans = min(ans, tmp);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 32256
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
map<int,int>d;
int read() {
	char ch=getchar();
	int x=0,q=1;
	while(ch>'9' || ch<'0')q=ch==45?-1:q,ch=getchar();
	while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
	return x*q;
}
int solve(int x) {
	if(d[x]!=0)
		return d[x];
	else
		return d[x]=((solve(x/2)+solve((x-1)/2)+solve((x-2)/2)))%mod;
}
signed main() {
	d[0]=1;
	d[1]=2;
	int n;
	n=read();
	int ans=solve(n);
	cout<<ans;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args)throws Exception {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(input.readLine());
        int a = Integer.parseInt(tokenizer.nextToken());
        int b = Integer.parseInt(tokenizer.nextToken());
        System.out.println((a*b) - (a+b) + 1);
    }
}


Measured memory_bytes: 21332
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<set>
#include<map>
#include<cassert>
#include<algorithm>
using namespace std;
typedef long long  ll;
typedef long double ld;
//typedef vector<int>        vi;
//typedef vector<ll>        vl;
//#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
//#define pb    push_back;
//#define fo(i,n) for(int i=0;i<n;i++)
int dp[100005];
int arr[100005];
const int INF=1e9 + 5;
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    dp[1]=0;
    dp[2]=abs(arr[1]-arr[2]);
    for(int i=3;i<=n;i++)
    {
        dp[i]=INF;
    }
    for(int i=3;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            if(j<i)
                dp[i]=min(dp[i],dp[i-j]+abs(arr[i-j]-arr[i]));
        }
    }
    cout<<dp[n]<<endl;
   
    return 0;
}
 


Measured memory_bytes: 4392
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

#define ll long long
#define int long long
#define FOR(i, x, y) for(int i = x; i <= y; ++i)
#define pb push_back
#define eb emplace_back
#define Size(v) (int)v.size()

using namespace std;
// using namespace __gnu_pbds;

int n, q;
const int nax = 5e5 + 5;
int ft[nax], ans[nax], a[nax];

int LSOne(int x) {
	return (x & (-x));
}

void update(int pos, int val) {
	while (pos < nax) {
		ft[pos] += val;
		pos += LSOne(pos);
	}
}

int get(int pos) {
	int res = 0;

	if (pos < 1) return 0;

	while (pos > 0) {
		res += ft[pos];
		pos -= LSOne(pos);
	}

	return res;
}

int get(int l, int r) {
	return (get(r) - get(l - 1));
}

vector<pair<int, int>> query[nax];
map<int, int> last;

void solve() {
	cin >> n >> q;

	FOR (i, 1, n) cin >> a[i];

	for (int i = 1; i <= q; ++i) {
		int l, r; cin >> l >> r;

		query[r].pb({l, i});
	}

	for (int i = 1; i <= n; ++i) {
		if (last[a[i]] != 0) {
			update(last[a[i]], -1);
		}

		last[a[i]] = i;

		update(last[a[i]], 1);

		for (auto &p : query[i]) {
			int idx = p.second;

			ans[idx] = get(p.first, i);
		}
	}

	for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}

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

	int t = 1;
	while (t--) 
		solve();
	return 0;
}

Measured memory_bytes: 71544
#include<stdio.h>
int main(){
  int n,v[22],c[22];
  scanf("%d",&n);
  for(int i=0;i<n;i++)scanf("%d",&v[i]);
  for(int i=0;i<n;i++)scanf("%d",&c[i]);
  int ans=0;
  for(int i=0;i<n;i++)if(v[i]-c[i]>0)ans+=v[i]-c[i];
  printf("%d",ans);
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
const ll mod = 1e9+7;

main(){
    int x;cin>>x;
    if(x>=30) cout<<"Yes\n";
    else cout<<"No\n";
}

Measured memory_bytes: 3632
s = input()
n = len(s)
def ifc(s,f):
    n = len(s)
    for i in range(n//2):
        if s[i] != s[-1-i]:
            f = False
    return f
f =True
f = ifc(s,f)
f = ifc(s[0:(n-1)//2],f)
f = ifc(s[(n+3)//2-1:],f)
if f:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

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

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

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

fn solve(ls: &Vec<usize>, ps: &Vec<usize>, x: usize, lv: usize) -> usize {
    if lv == 0 {
        return if x >= 1 { 1 } else { 0 };
    }
    if x == 0 {
        return 0;
    }

    if x >= ls[lv] {
        return ps[lv];
    }

    let mut x1 = x-1;
    let mut ans = solve(ls, ps, x1, lv-1);
    let x2 = ls[lv-1] + 1;
    if x2 >= x {
        return ans;
    }
    ans += 1;
    x1 = x - (ls[lv-1] + 2);
    ans += solve(ls, ps, x1, lv-1);
    ans
}

fn main() {
    input!{
      n: usize,
      x: usize,
    }

    let mut ls = vec![0usize; n+1];
    let mut ps = vec![0usize; n+1];
    ls[0] = 1;
    ps[0] = 1;

    for i in 1..n+1 {
        ls[i] = ls[i-1]*2 + 3;
        ps[i] = ps[i-1]*2 + 1;
    }
    println!("{}", solve(&ls, &ps, x, n));
}


Measured memory_bytes: 4352
import sys
import numpy as np

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n = I[0]
v, c = I[1:].reshape(2, n)

def main():
    return np.sum(np.maximum(v - c, 0))

if __name__ == '__main__':
    ans = main()
    print(ans)

Measured memory_bytes: 12512
x = list(map(int,input().split()))
n = x[0]
cap = x[1]
weights = []
vals = []
for i in range(n):
    y = list(map(int,input().split()))
    vals.append(y[0])
    weights.append(y[1])
# status = [0] * len(weights)
# dp = [0] * (cap + 1)
dp = [[-1]*(cap+1) for i in range(len(weights)+1)]
cnt = 0

# def knapsack(s):
#     w = 0
#     v = 0
#     if s == len(weights):
#         for i in range(len(status)):
#             if status[i] == 1:
#                 w += weights[i]
#                 v += vals[i]
#         if w <= cap:
#             return v
#         elif w > cap:
#             return -1
    
#     status[s] = 0
#     a = knapsack(s+1)
#     status[s] = 1
#     b = knapsack(s+1)

#     return max(a,b)

def knapsack(s,av):
    global cnt
    cnt += 1

    if dp[s][av] != -1:
        return dp[s][av]

    if s == len(weights):
        dp[s][av] = 0
        return 0
    
    a = knapsack(s+1,av)

    if av >= weights[s]:
        b = vals[s] + knapsack(s+1,av-weights[s])
    else:
        b = -1
    
    dp[s][av] = max(a,b)

    return max(a,b)


print(knapsack(0,cap))
# print(f'Count: {cnt}')




# def knapsack(w):
#     global status
#     global cnt
#     cnt += 1
#     isFin = True
#     for i in range(len(weights)):
#         if status[i] == 0 and weights[i] <= w:
#             isFin = False
#             break
    
#     if isFin == True:
#         return 0
#     max_v = -float('inf')
#     for i in range(len(weights)):
#         if status[i] == 1 or weights[i] > w:
#             continue
#         status[i] = 1
#         r = knapsack(w-weights[i]) + vals[i]
#         status[i] = 0
#         max_v = max(max_v,r)
#     return max_v



# def knapsack2(w):
#     global status
#     global cnt
#     cnt += 1
#     isFin = True
#     for i in range(len(weights)):
#         if status[i] == 0 and weights[i] <= w:
#             isFin = False
#             break
    
#     if isFin == True:
#         return 0
#     max_v = -float('inf')
#     for i in range(len(weights)):
#         if status[i] == 1 or weights[i] > w:
#             continue
#         status[i] = 1
#         r = 0
#         if dp[w-weights[i]] == 0:
#             r = knapsack2(w-weights[i]) + vals[i]
#         else:
#             r = dp[w-weights[i]] + vals[i]
#         status[i] = 0
#         max_v = max(max_v,r)
#         dp[w] = max_v
#         print(dp)
#     return max_v



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

int main() {
    int n;
    while(cin >> n, n) {
        int A = 0, B = 0;
        for(int i=0; i<n; ++i) {
            int a, b; cin >> a >> b;
            if(a > b) {
                A += a+b;
            } else if(a < b) {
                B += a+b;
            } else {
                A += a;
                B += b;
            }
        }
        cout << A << " " << B << endl;
    }
}


Measured memory_bytes: 2992
from heapq import heappush, heappop

n, m = map(int, input().split())
d = dict()
for _ in range(n):
    a, b = map(int, input().split())
    d.setdefault(a, [])
    d[a].append(-b)

h = []
ans = 0
for i in range(1, m + 1):
    for b in d.get(i, []):
        heappush(h, b)
    if len(h) > 0:
        m = heappop(h)
        ans -= m
print(ans)


Measured memory_bytes: 27428
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=100000+5;
int n,m,x[150],y[150];
int main()
{
    scanf("%d%d%d%d",&n,&m,&x[0],&y[0]);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&y[i]);
    }

    sort(x,x+n+1);
    sort(y,y+m+1);
    if(y[0]>x[n]) printf("No War");
    else printf("War");
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define mfill(x,y) memset(x,y,sizeof(x))
#define all(v) v.begin(), v.end()
#define in(x,y,h,w) if(0<=x&&x<h&&0<=y&&y<w)
#define y0 y12345
#define y1 y54321

#ifdef LOCAL
#define debug(...) fprintf(stderr,__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ul = unsigned long;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;using vvint = vector<vector<int>>;
using vll = vector<ll>;using vvll = vector<vector<ll>>;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a, const T &b){if(a>b){a=b;return 1;}return 0;}
template <class T>void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}
template <class T>T gcd(T &a, T &b){if(a<b){swap(a,b);} T r = a%b; while(r!=0){a=b;b=r;r=a%b;} return b;}

vint dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
vint dx8 = {-1, -1, -1, 0, 1, 1, 1, 0}, dy8 = {-1, 0, 1, 1, 1, 0, -1, -1};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    debug("debug test\n");
    int n,r;cin>>n>>r;
    cout << r + (n >= 10?0:100*(10-n)) << endl;
    return 0;
}


Measured memory_bytes: 256
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#define bged(v) (v).begin(),(v).end()
#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
typedef long long ll;
const int Imx=2147483647;
const ll Lbig=2e18;
const int mod=1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it,len;
	fastio(){it=len=0;}
	inline char get()
	{
		if(it<len)return s[it++];it=0;
		len=fread(s,1,100000,stdin);
		if(len==0)return EOF;else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while(c==' '||c=='\n')c=get();
		if(it>0)it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0;bool ng=0;char c;c=_buff.get();
	while(c!='-'&&(c<'0'||c>'9'))c=_buff.get();
	if(c=='-')ng=1,c=_buff.get();
	while(c>='0'&&c<='9')r=r*10+c-'0',c=_buff.get();
	return ng?-r:r;
}
template<class T> inline void putnum(T x)
{
	if(x<0)putchar('-'),x=-x;
	register short a[20]={},sz=0;
	while(x)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1;i>=0;i--)putchar('0'+a[i]);
}
inline char getreal(){char c=_buff.get();while(c==' '||c=='\n')c=_buff.get();return c;}
ll k;
int a[211];
int main()
{
	cin>>k;
	k++;
	int n=0;
	bool fb=0;
	for(int i=49;i>=0;i--)
	{
		if(fb)
		{
			a[++n]=n;
		}
		if((k>>i)&1)
		{
			if(!fb)fb=1;
			else
			{
				for(int i=n;i>=1;i--)a[i+1]=a[i];
				a[1]=++n;
			}
		}
	}
	putsi(n*2);
	for(int i=1;i<=n;i++)puti(i);
	for(int i=1;i<=n;i++)puti(a[i]);
	
	return 0;
}

Measured memory_bytes: 256