akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define REPr(i,n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define FORqr(i, m , n) for(int i = (n);i >=(m);--i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define SCLLD(n) scanf("%lld",&n)
#define SCLLD2(m,n) scanf("%lld%lld",&m,&n)
#define SCLLD3(m,n,k) scanf("%lld%lld%lld",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define VSCD(v,N) REP(i,N){int x; SCD(x); v.PB(x);}
#define VSCLLD(v,N) REP(i,N){long long x; SCLLD(x); v.PB(x);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x,S) (S.count(x) != 0)
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector < VI > VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
////////////////////////////////////////////////////////////////////

int dx[9] = {0,0,1,1,1,0,-1,-1,-1};
int dy[9] = {0,1,1,0,-1,-1,-1,0,1};

int main(){
    cin.tie(0);
    map<PII,ll> f;
    ll H,W,N;
    cin >> H >> W >> N;
    REP(i,N){
        int a,b;
        cin >> a >> b;
        REP(j,9){
            PII p = MP(a+dx[j],b+dy[j]);
            f[p] = f[p] + 1;
        }
    }

    ll ans[10] = {};

    for(pair<PII, ll> p:f){
        int a = (p.first).first;
        int b = (p.first).second;

        if ((a <= 1) or (b <= 1) or (a >= H) or (b >= W)) continue;
        ans[p.second]++;

		//cout << p.first << " " << p.second << endl;
	}
    
    ll em = 0;
    FORq(i,1,9){
        em += ans[i];
    }

    cout << ((H-2)*(W-2)-em) << "\n";

    FORq(i,1,9){
        cout << ans[i] << "\n";
    }

}


Measured memory_bytes: 56448
#include "bits/stdc++.h"
using namespace std;
int main(void)
{
	int a,b,c;
	vector<int>arr(3, 0);
	cin >> arr[0] >> arr[1] >> arr[2];
	sort(arr.begin(), arr.end());
	cout << arr[2] * 10 + arr[1] + arr[0]<<"\n";
}
	

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

using namespace std;

//A, C, G, T

int main(int argc, char const *argv[])
{
    string s;
    cin >> s;
    int max = 0;
    int cnt = 0;
    for (char c : s)
    {
        if (c == 'A' || c == 'C' || c == 'G' || c == 'T')
        {
            cnt += 1;
        }else
        {
            if (cnt > max)
            {
                max = cnt;
            }
            cnt = 0;
        }
        
    }
    if (cnt > max) max = cnt;

    cout << max << endl;

    return 0;
}


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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define all2(a, b) (a).begin(), (a).begin() + (b)
#define debug(vari) cerr << #vari << " = " << (vari) << endl;

int count(int n)
{
    int cnt = 0;
    while (n / 2)
    {
        cnt++;
        n /= 2;
    }
    return cnt;
}

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

    int ans = 0;
    rep2(i, 1, n + 1) ans = max(ans, count(i));
    cout << int(pow(2.0, float(ans))) << endl;
    return 0;
}


Measured memory_bytes: 256
n,k= map(int,input().split())

l = list(map(int,input().split()))

min_v = min(l)

min_idx = []

for i in range(n):
    if l[i] == min_v:
        min_idx.append(i)

tail = 0

curr_min = 0
pre_min_idx = 0
res = 0
idx = min_idx[0]
i = 0
while tail < n:
    for i in range(tail,n):
        if l[i]==min_v:
            idx = i
            break
    if idx != i:
        res += (n-tail)//(k-1) + (not not (n-tail)%(k-1)) 
        break
    interval = idx - tail
    num = interval//(k-1)
    delta = not not interval%(k-1)
    res += num+delta
    
    tail += (num+delta)*(k-1)+1
    #print(str(idx)+" "+str(tail)+" "+str(res)) 
print(res)


Measured memory_bytes: 14008
import math
import operator
from itertools import *
from functools import *


def main():
    #infile = open("compprog.txt", mode="r")
    n = int(input())
    res = -1
    divisors_found = set()
    for subset in powerset(prime_factors(n)):
        div1 = prod(subset)
        if div1 not in divisors_found:
            div2 = n // div1
            this_f = f(div1, div2)
            if res == -1 or this_f < res:
                res = this_f
            divisors_found.add(div1)
            divisors_found.add(div2)
    print(res)
    #infile.close()


def f(a, b):
    return max(len(str(a)), len(str(b)))


def prime_factors(num):
    factor_list = []
    while num % 2 == 0:
        factor_list.append(2)
        num //= 2
    i = 3
    while i <= math.sqrt(num):
        if num % i == 0:
            factor_list.append(i)
            num //= i
            i = 3
        else:
            i += 2
    if num > 1:
        factor_list.append(num)
    return factor_list


def powerset(iterable):
    s = list(iterable)
    return list(chain.from_iterable(combinations(s, r) for r in range(len(s) + 1)))


def prod(iterable):
    return reduce(operator.mul, iterable, 1)



if __name__ == "__main__":
    main()


Measured memory_bytes: 146724
N,T = map(int,input().split())
array = []
array = [ [lista for lista in map(int,input().split())] for I in range(N) ]

min = 1001
for I in array:
    if I[1] > T:
        continue
    elif I[1] <= T:
        if I[0] < min: min = I[0]
print(min) if min < 1001 else print('TLE')

Measured memory_bytes: 9052
(n,m,c) = map(int, input().split())
bs = list(map(int, input().split()))
cnt = 0
for _ in range(n):
    #print(cnt)
    ass = list(map(int, input().split()))
    #print(ass)
    sum = 0
    for (a,b) in zip(ass,bs):
        sum = sum + a*b
    #print(sum)
    if sum + c > 0:
        cnt = cnt + 1

print(cnt)


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

int main(){
  int n, l;
  long long k, sa;
  
  cin >> n >> k >> l;
  vector<int> a(n, 0);
  sa = k - l;
  
  for(int i = 0; i < l; i++){
    int d;
    cin >> d;
    
    a[d-1]++;
  }
  
  for(int i = 0; i < n; i++){
    //cout << a[i] << " ";
    if((a[i] + sa) > 0){
      cout << "Yes" << endl; 
    }else{
      cout << "No" << endl; 
    }
  }

  
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	static int[][] dp = new int[100001][3];
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] a = new int[100001][3];
		for(int i = 0 ; i < n ; i++) {
			for(int j = 0 ; j < 3 ; j++) {
				a[i][j] = sc.nextInt();
			}
		}
		for(int i = 0 ; i < n ; i++) {
			for(int j = 0 ; j < 3 ; j++) {
				insMax(a , i , j);
			}
		}



		sc.close();
		System.out.println(Math.max(Math.max(dp[n][0], dp[n][1]),dp[n][2]));

	}
	public static void insMax(int[][] a , int i , int j) {
		int[] b = new int[2];
		int count = 0;
		for(int t = 0 ; t < 3 ; t++) {
			if(t != j) {
				b[count] = dp[i][t] ;
				count++;
			}
		}
      
		dp[i + 1][j] = Math.max(b[0], b[1]) + a[i][j];
	}
}



Measured memory_bytes: 66684
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int[] pri = new int[1000001];
		
		for(int i=2;i<=1000000;i++){
			pri[i] = i;
		}

		for(int i=2;i<=1000000;i++){
			for(int j=i+i;j<=1000000;j+=i){
					pri[j]=0;
			}
		}
	
		boolean exit = true;
		while(sc.hasNext()){
			int n = sc.nextInt();
			int sum=0;
			for(int i=2;i<=n;i++){
				if(pri[i]>0)sum++;
			}
			System.out.println(sum);
		}
	}
	
}

Measured memory_bytes: 24764
import sys
input = sys.stdin.readline
def main():
    S = input().rstrip("\r\n")
    ans = 0
    for i in range(2**(len(S)-1)):
        nums = []
        num_str = S[0]
        for j in range(len(S)-1):
            if (i >> j) & 1:
                nums.append(int(num_str))
                num_str = S[j+1]
            else:
                num_str += S[j+1]
        if num_str != "":nums.append(int(num_str))
        ans += sum(nums)
    print(ans)
if __name__ == "__main__":
    main()

Measured memory_bytes: 41328
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<cctype>
#include <string>
using namespace std;

int main(){
char ch;
int NUM = 26;
int num = 'a';
int sum[NUM];

for ( int i = 0; i < NUM; i++){ 
  sum[i] = 0;
}

while(cin >> ch){
  if(isalpha(ch)){
       if(islower(ch)){//小文字
           sum[ch - 'a']++;
       }
       if(isupper(ch)){//大文字
           sum[ch - 'A']++;
       }
  }
}
for ( int i = 0; i < NUM; i++){ 
  printf("%c : %d\n" , num+i , sum[i] );
}

return 0;
}


Measured memory_bytes: 3220
#include "bits/stdc++.h"
using namespace std;

string st;
int a;
int getnum() {
	int num = 0;
	while (1) {
		if (st[a] == ']') {
			return num/2+1;
		}
		else {
			num *= 10;
			num += st[a] - '0';
			a++;
		}
	}

}

int getans() {
	vector<int>nums;
	while (1) {

		if (st[a] == '[') {
			a++;
			nums.push_back(getans());
		}
		else if (st[a] == ']') {
			sort(nums.begin(), nums.end());
			int ans = 0;
			for (int i = 0; i < nums.size() / 2 + 1; ++i) {
				ans += nums[i];
			}
			a++;
			return ans;
		}
		else {
			nums.push_back(getnum());
		}
	}
}

int main() {
	int n; cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> st;
		a = 1;
		const int ans(getans());
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3212
# include <bits/stdc++.h>
using namespace std;
# define maxN 100005
char s[maxN];
int N, Q, sum[maxN];
int main() {
	cin >> N >> Q >> s + 1;
	for(int i = 1; i <= N; ++i) {
		sum[i] = sum[i - 1];
		if(s[i] == 'C' && s[i - 1] == 'A') ++sum[i];
	}
	while(Q--) {
		int x, y; cin >> x >> y;
		cout << sum[y] - sum[x] << endl;
	}
	return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <string>
#include <map>
#include <iterator>

using namespace std;

int debug = 0;

int main(void){
	string tmp;
	string max_len_word, max_times_word;
	unsigned int max_len = 0, max_times = 0;
	map<string, int> words;

	while(cin >> tmp){
		if(tmp.size() > max_len){
			max_len_word = tmp;
			max_len = tmp.size();
			if(debug) cout << "longest word overwritten." << endl;
		}
		++words[tmp]; 
		if(debug) cout << "count " << tmp << " is " << words[tmp] << endl;
	}

	map<string, int>::iterator it;
	max_times=0;
	for(it=words.begin(); it!=words.end(); ++it){
		if(max_times < it->second){
			max_times_word = it->first;
			max_times = it->second;
			if(debug) cout << "the most frequent word is now" << it->first << endl;
		}
		if(debug) cout << "count " << it->first << " is " << it->second << endl;
	}

	cout << max_times_word << " " << max_len_word << endl;

	return 0;
}

Measured memory_bytes: 0
def Bit_Loop():
    h,w,k = map(int,input().split())
    field = [input() for i in range(h)]
    ans = 0
    for i in range(2 ** h):
        for j in range(2 ** w):
            black = 0
            for s in  range(h):
                for t in range(w):
                    if ((((i >> s) & 1) == 0) and (((j >> t) & 1) == 0) and field[s][t] == '#'):
                        black += 1
            if black == k:
                ans += 1
    print(ans)

if __name__ == "__main__":
    Bit_Loop()


Measured memory_bytes: 9228
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define MAX 128
#define fst first
#define sec second
#define pb push_back
#define mp make_pair
#define ALL(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << ": " << x << '\n'
#define bit(n) (1LL << (n))
#define int long long
const double PI = 3.141593;
const int MOD = (int)1e9 + 7;
const int INF = 100100100;
const double EPS = 1e-9;
template <class T>
bool chmax(T &a, const T &b){if (a < b){a = b;return 1;}return 0;}
template <class T>bool chmin(T &a, const T &b){if (b < a){a = b;return 1;}return 0;}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } //最大公約数
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }     //最小公倍数
ll combination(ll n, ll r){if (r * 2 > n)r = n - r;ll dividend = 1;ll divisor = 1;for (ll i = 1; i <= r; ++i){dividend *= (n - i + 1);divisor *= i;}return dividend / divisor;}


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

  char s;
  cin >> s;
  s++;

  cout << s << endl;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_map>

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

using namespace std;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main(){
    int n; cin >> n;
    string s; cin >> s;
    int count = 0;
    for(int i = 0; i< s.size()-2; i++) {
        if(s[i] =='A' && s[i+1] == 'B' && s[i+2] == 'C')
            count++;
    }
    cout << count << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define  ft  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define  ll  long long
#define  pi  pair<int,int>
#define  pb  push_back
#define  F   first
#define  S   second
const int N=2e5+3;
//string s,p;
//vector<int>v;
//map<int,int>mp;

int main()
{
    ft
    ll t,i,j,n,m,l,r;
    cin>>n;
    l=n/15ll;
    r=n*800ll - l*200ll;
    cout<<r<<"\n";
    return 0;
}



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

class Program
{
    static void Main(string[] args)
    {
        // 入力
        var n = double.Parse(Console.ReadLine());
        double[] numbers = Console.ReadLine().Split().Select(double.Parse).ToArray();

        Array.Sort(numbers);
        double ans = numbers[0];
        for (int i = 1; i < n; i++)
        {
            ans = (ans + numbers[i]) / 2;
        }
        //出力
        Console.WriteLine(ans);
    }
}


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

std::string data;
int i=0,pointerEnd=0;/*iはdataのpointer*/
int ansList[10000];

void solve(int pointerStart){
  int i0=i,temp=0;
  while (i<data.length()){
    if (data[i]=='\\'){
      i++;
      solve(pointerEnd);
    }else if (data[i]=='_'){
      i++;
    }else if (data[i]=='/'){
      i++;
      for (int j=pointerStart;j<pointerEnd;j++)temp+=ansList[j];
      ansList[pointerStart]=i-i0+temp;
      pointerStart++;
      pointerEnd=pointerStart;
      return;
    }
  }
}
int main(){
  int check=0;
  std::cin >> data;
/*  for (int j=0;j>20002;j++)ansList[j]=0;*/
  ansList[1]=0;
  while (i<data.length()){
    if (data[i++]=='\\'){
      solve(pointerEnd);
    }
  }
  int temp=0;
  for (int j=0;j<pointerEnd;j++)temp+=ansList[j];
  std::cout << temp << '\n';
  std::cout << pointerEnd;
  for (int j=0;j<pointerEnd;j++){
    std::cout<<' '<<ansList[j];
  }
  std::cout<<'\n';

}



Measured memory_bytes: 3828
#include <stdio.h>
#include <string.h>
int main(void)
{
	char str[100001];
	scanf("%s", str);
	int n = strlen(str);
	char b[n];
	char w[n];
	b[0] = '0';
	w[0] = '1';
	int i = 1;
	while (i < n)
	{
		if (i % 2)
		{
			b[i] = '1';
			w[i] = '0';
		}
		else
		{
			b[i] = '0';
			w[i] = '1';
		}
		i++;
	}
	int countb = 0;
	int countw = 0;
	i = 0;
	while (str[i])
	{
		if (str[i] != b[i])
			countb++;
		if (str[i] != w[i])
			countw++;
		i++;
	}
	if (str[0] == '1')
		printf("%d", countw);
	else
		printf("%d", countb);
	return (0);
}


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

  int fx(int N){
    int sumx=0;
    while (N>0){
      sumx += N%10;
      N /= 10;
    }
  return sumx;
  }

int main(){
  int n;
  cin >>n;
  int calc =fx(n);
  if (n%calc == 0){
    cout <<"Yes"<<endl;
  }else {
    cout <<"No"<<endl;
  }
return 0;
}

Measured memory_bytes: 384
N = int(input())
D = list(map(int, input().split()))
M = int(input())
T = list(map(int, input().split()))

D.sort(reverse=True)
T.sort(reverse=True)

count = 0

j = 0

for i in range(M):
    while True:
        if j >= N:
            break
        if T[i] == D[j]:
            count += 1
            j += 1
            break
        else:
            j += 1

if count == M:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 35420
#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<int> vec(5);
    for(int i = 0; i < 5; i++)
    {
        cin >> vec[i];
    }
    int l=0,m=0;
    for(int i = 0; i < 5; i++)
    {
        if (vec[i]%10 != 0 && m < (vec[i]/10+1)*10-vec[i]) {
            l = i;
            m = (vec[i]/10+1)*10-vec[i];
        }
    }
    int ans = 0;
    for(int i = 0; i < 5; i++)
    {
        if (i == l) {
            ans += vec[i];
        }
        else
        {
            if (vec[i]%10 == 0) {
                ans += vec[i];
            }
            else
            {
                ans += (vec[i]/10+1)*10;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 100000007
#define ll long long
#define F first
#define S second
#define pii pair<int,int>
#define FOR(i,k,n) for(int i=k;i<n+k;i++)
#define ALL(x) x.begin(),x.end()
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);
#define deg(x) cout<<"--"<<x<<endl;
int II(){int q;scanf("%d",&q);return q;}
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
int dxx[]={0,-1,-1,-1,0,1,1,1};
int dyy[]={-1,-1,0,1,1,1,0,-1};
#define int ll
void solve(){
	int n;cin>>n;
	int ar[n+10];
	for(int i=1; i<=n; i++){
		int q;cin>>q;
		ar[i]=q-i;
	}
	sort(ar+1,ar+1+n);
	int arr[]={ar[(n+1)/2]};
	int mi=1e16;
	for(int i=0; i<1; i++){
		int to=0;
		for(int j=1; j<=n; j++){
			to+=abs(ar[j]-arr[i]);
		}
		mi=min(mi,to);
	}
	cout<<mi<<endl;
}
 
main(){
    int tt=1;
    int cas=1;
    while(tt--){
        //printf("Case %d: ",cas++);
        solve();
    }
}

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

string s;

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

	cin >> s;
	if (s[0] == s[1] && s[1] == s[2]) cout << "No\n";
	else cout << "Yes\n";

	return 0;
}

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

using namespace std;

int rows_l_to_r[2000][2000] = {};
int rows_r_to_l[2000][2000] = {};
int columns_l_to_r[2000][2000] = {};
int columns_r_to_l[2000][2000] = {};

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> s_vec;
    for (int i = 0; i < h; ++i) {
        string s;
        cin >> s;
        s_vec.push_back(s);
    }

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (j == 0) rows_l_to_r[i][j] = (s_vec[i][j] == '.') && 1;
            else if (s_vec[i][j] == '#') rows_l_to_r[i][j] = 0;
            else if (s_vec[i][j] == '.') rows_l_to_r[i][j] = rows_l_to_r[i][j - 1] + 1;
        }
    }

    for (int i = 0; i < h; ++i) {
        for (int j = w - 1; j >= 0; --j) {
            if (j == w - 1) rows_r_to_l[i][j] = (s_vec[i][j] == '.') && 1;
            else if (s_vec[i][j] == '#') rows_r_to_l[i][j] = 0;
            else if (s_vec[i][j] == '.') rows_r_to_l[i][j] = rows_r_to_l[i][j + 1] + 1;
        }
    }

    for (int i = 0; i < w; ++i) {
        for (int j = 0; j < h; ++j) {
            if (j == 0) columns_l_to_r[j][i] = (s_vec[j][i] == '.') && 1;
            else if (s_vec[j][i] == '#') columns_l_to_r[j][i] = 0;
            else if (s_vec[j][i] == '.') columns_l_to_r[j][i] = columns_l_to_r[j - 1][i] + 1;
        }
    }

    for (int i = 0; i < w; ++i) {
        for (int j = h - 1; j >= 0; --j) {
            if (j == h - 1) columns_r_to_l[j][i] = (s_vec[j][i] == '.') && 1;
            else if (s_vec[j][i] == '#') columns_r_to_l[j][i] = 0;
            else if (s_vec[j][i] == '.') columns_r_to_l[j][i] = columns_r_to_l[j + 1][i] + 1;
        }
    }

    int res = 0;
    for (int k = 0; k < h; ++k) {
        for (int i = 0; i < w; ++i) {
            if (s_vec[k][i] == '#') continue;
            res = max(res, rows_r_to_l[k][i] + rows_l_to_r[k][i] + columns_r_to_l[k][i] + columns_l_to_r[k][i] - 3);
        }
    }
    cout << res << endl;

    return 0;
}





Measured memory_bytes: 66816
k,q = map(int,input().split())
d = list(map(int,input().split()))
al = []
for i in range(q):
    n,x,m = map(int,input().split())
    pd = []
    count = 0
    for j in range(k):
        pd.append(d[j]%m)
        if d[j]%m == 0:
            count += 1
    a = sum(pd)
    ans = x%m
    ans += a*((n-1)//k)
    #print(pd)
    c = 0
    for j in range((n-1)%k):
        ans += pd[j]
        if pd[j] == 0:
            c += 1
    al.append(n-1-(ans//m)-count*((n-1)//k)-c)
for i in range(q):
    print(al[i])

Measured memory_bytes: 61916
// AtCoder template
// sabaより胡蝶しのぶさんの方が可愛いのではないか？
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n; ++i)



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n,a,b; cin >> n >> a >> b;
    ll x = a + b;

    ll ret;
    if(n%x >= a) ret = a;
    else ret = n%x;
    cout << n/x*a + ret << endl;
}

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

using namespace std;

ll n,pr,sum,ans,a[5050],minn[5050][5050];

int main()
{
	scanf("%lld%lld",&n,&pr);
	for(ll i=1;i<=n;i++)
	{
		scanf("%lld",a+i);a[n+i]=a[i];ans+=a[i];
	}
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=n;j++)
		{
			minn[i][0]=a[i];
			minn[i][j]=min(minn[i][j-1],a[n+i-j]);
		}
	}
	for(ll i=0;i<n;i++)
	{
		sum=pr*i;
		for(ll j=1;j<=n;j++)
		{
			sum+=minn[j][i];
		}
		ans=min(ans,sum);
	}
	printf("%lld",ans);
}

Measured memory_bytes: 79104
def partition(A, p, r):
    x = A[r][1]
    i = p - 1
    for j in range(p, r):
        if A[j][1] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1


def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)


def main():
    n = int(input())
    A = []
    for i in range(n):
        m, s = input().split()
        s = int(s)
        A.append([m, s])
    B = A[:]
    quicksort(B, 0, n-1)

    for i in range(n-1):
        if B[i][1] == B[i + 1][1]:
            if A.index(B[i]) > A.index(B[i + 1]):
                print("Not stable")
                break
    else:
        print("Stable")

    for i in range(n):
        print(*B[i])


if __name__ == '__main__':
    main()



Measured memory_bytes: 18836
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include<stack>
#include<sstream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<list>
#include<numeric>
typedef long long ll;

#define pi 3.14159265358979323846
#define VI vector<int>
#define VLL vector<long long>
#define MAX max_element
#define MIN min_element
#define all(v) v.begin(), v.end()
const ll MOD = 1e9 + 7;
using namespace std;
template<typename T>
T gcd(T a, T b) {
	return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
	return a * b / gcd(a, b);
}

template<typename T>
T binarysearch(vector<T> A, T key) {
	ll left = 0;ll right = 4;ll mid;
	while (left < right) {
		mid = (left + right) / 2;
		if (key == A[mid]) return 1;
		if (key > A[mid]) left = mid + 1;
		else if (key < A[mid]) right = mid;
	}
	return 0;
}

template<typename T>
T finder(vector<T> vec, T number) {
	auto itr = find(vec.begin(), vec.end(), number);
	size_t index = distance(vec.begin(), itr);
	if (index != vec.size()) { // 発見できたとき
		return 1;
	}
	else { // 発見できなかったとき
		return 0;
	}
}
ll frac(ll n)//階乗
{
	if (n == 0) {
		return 1;
	}
	return (n * frac(n - 1)) % MOD;
}

template<typename T>
T keta(T a) {
	ll kazu = 1;
	while (1) {
		if (a / 10 != 0) { a /= 10;kazu++; }
		else break;
	}
	return kazu;
}//桁数


template<typename T>
T nCr(ll n, T r) {
	ll ans = 1;
	for (int i = n; i > n - r; --i) {
		ans = ans * i;
	}
	for (int i = 1; i < r + 1; ++i) {
		ans = ans / i;
	}
	return ans;
}
/*char r[4];
int yaju[4];
char op[3];
int sum = 0;
scanf("%s", r);
for (int i = 0;i < 4;i++) {
	yaju[i] = r[i] - '0';
}
*/
int main() {
	string S;cin >> S;
	if (S == "ABC") cout << "ARC" << endl;
	else cout << "ABC" << endl;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;  
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define Rep(i, a, b) for(ll i = a; i <= b; i++)
#define repr(i, a, b) for(ll i = b-1; i >= a; i--)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
using ll = long long;
#define ALL(v) (v).begin(),(v).end()
#define endl "\n"
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define co(x) cout << x << endl
#define coel cout << endl
#define pb push_back
#define sz(v) ((ll)(v).size())
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
// const ll INF = 1LL << 60;
#define pp pair<ll, pair<ll, ll>> 
#define fi first
#define se second

////////////////////////////////////////////////////////

ll val[3050][3050], dp[3050][3050][4];
const ll INF = 10000;

int main() {
    ll r, c, k; cin >> r >> c >> k;
    rep(i, 0, k){
        ll R, C, v;
        cin >> R >> C >> v;
        val[R][C] = v;
    }

    rep(i, 0, 3050) rep(j, 0, 3050) rep(k, 0, 4) dp[i][j][k] = -INF;

    if(val[1][1]) dp[1][1][1] = val[1][1];
    dp[1][1][0] = 0;

    Rep(i, 1, r){
        Rep(j, 1, c){
            Rep(k, 0, 3){
                if(dp[i][j][k] != -INF){
                    if(val[i][j+1] && k!=3) chmax(dp[i][j+1][k+1], dp[i][j][k] + val[i][j+1]);
                    chmax(dp[i][j+1][k], dp[i][j][k]);
                }
            }
            Rep(k, 0, 3) {
                if(val[i+1][j]) chmax(dp[i+1][j][1], dp[i][j][k] + val[i+1][j]);
                chmax(dp[i+1][j][0], dp[i][j][k]);
            }
        }
    }

    ll ans = -INF;
    Rep(k, 0, 3) chmax(ans, dp[r][c][k]);

    // Rep(k, 0, 3){
    //     Rep(i, 1, r){
    //         Rep(j, 1, c){
    //             cout << dp[i][j][k] << " \n"[j==c];
    //         }
    //     }
    //     coel;
    // }

    co(ans);

    return 0;
}
 
 


Measured memory_bytes: 365628
use std::vec::Vec;
use std::cmp::*;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn main() {
  let n: usize = read();
  let a: Vec<i64> = read_vec();
  let sum = a.iter().fold(0, |acc, x| acc + x);

  let mut ans = (sum - 2 * a[0]).abs();
  let mut tmp = 0;
  for i in 0..n-1 {
    tmp += a[i];
    let foge = sum - tmp;
    ans = min(ans, (tmp - foge).abs());
  }




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


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

int dp[10010];
int main() {
	int H,N; cin>>H>>N;
	int a[1010], b[1010];
	rep(i,N) cin>>a[i]>>b[i];
	dp[0]=0;
 
    for(int i=1;i<H+1;i++){    
        dp[i]=1e9;//モンスターのHPでのDP
        for(int j=0;j<N;j++){  //HPごとに技ごとで最小のMPをチェック
            dp[i]=min(dp[i],dp[max(0,i-a[j])]+b[j]);
        }
    }
    cout << dp[H] << endl;//モンスターのHPをH減らすため消耗する魔力の最小値
}

Measured memory_bytes: 384
using System;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Text;

public class Program
{
    public void Proc() {
        Reader.IsDebug = false;
        int x  = 0;
        int ans = 0;
        int cnt = int.Parse(Reader.ReadLine());
        string cmd = Reader.ReadLine();
        foreach(char c in cmd) {
            if(c=='D') {
                x--;
            } else {
                x++;
            }
            ans = Math.Max(x, ans);
        }
        Console.WriteLine(ans);

    }



    public class Reader {
        public static bool IsDebug = true;
        private static System.IO.StringReader SReader;
        private static string InitText = @"

3 5 2 7


";
        public static string ReadLine() {
            if(IsDebug) {
                if(SReader == null) {
                    SReader = new System.IO.StringReader(InitText.Trim());
                }
                return SReader.ReadLine();
            } else {
                return Console.ReadLine();
            }
        }
    }
    public static void Main(string[] args)
    {
        Program prg = new Program();
        prg.Proc();
    }
}


Measured memory_bytes: 2776
A = []
B = []
ans = []
n,m = map(int, input().split())
for i in range(n):
    elem = list(map(int,input().split()))
    A.append(elem)
for i in range(m):
     B.append(int(input()))

for i in range(n):
    calc = 0
    for j in range(m):
        calc += A[i][j] * B[j]
    print(calc)



Measured memory_bytes: 6012
fOdd :: Int->Int->Int
fOdd m x=if x<=m then m-x else x-m-1

fEve :: Int -> Int -> Int
fEve m x=if x<=m then m-x else x-m

f ::(Int->Int->Int)-> Int->(Int,Int)-> [Int]->Int
f _ _ (_,ans) []=ans
f f2 m (d,ans) (x:xs)=
    let d1=f2 m x
    in if d1<=d then f f2 m (d1,x) xs else f f2 m (d,ans) xs


main =do
      e<-getLine
      es<-getLine
      let n=read e::Int
          xs=map read (words es)::[Int]
          m1=maximum xs
          m2=m1 `div` 2
      putStr $ (show m1) ++ " "
      putStrLn $ show $ if n `mod` 2==0 then f fEve m2 (m1,m1) xs else f fOdd m2 (m1,m1) xs

Measured memory_bytes: 37884
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10;
int n, c[N], cnt[N], siz[N];
	inline LL cal(int n) {
		// C(n,2) + n
		return 1LL*n*(n+1)/2;
	}
LL ans[N];
vector<int>G[N];
	void dfs(int v, int fa) {
		int tmp = cnt[c[v]];
		siz[v] = 1;
		for(int u:G[v]) {
			if(u==fa) continue;
			cnt[c[v]] = 0;
			dfs(u, v);
			siz[v] += siz[u];
			ans[c[v]]+=cal(siz[u]-cnt[c[v]]);
		}
		cnt[c[v]] = tmp + siz[v];
	}
	
	#define ADD(a, b) 	\
		do {			\
			G[a].push_back(b);	\
			G[b].push_back(a);	\
		}while(0);		
		
	inline void add(int a, int b) {
		G[a].push_back(b);
		G[b].push_back(a);
	}
	
int main() {
	//scanf("%d", &n);
	std::ios::sync_with_stdio(false);
	cin>>n;
	for (int i = 1; i <= n; i++)
		//scanf("%d", &c[i]);
		cin>>c[i];
	for (int i = 1; i < n; i++) {
		int u, v;
		//scanf("%d%d", &u, &v);
		cin>>u>>v;
		//G[u].push_back(v);
		//G[v].push_back(u);
		add(u, v);
		//ADD(u, v); ADD(v, u);
	}
	dfs(1, 0);
	for (int i = 1; i <= n; i++) {
		cout<< cal(n) - ans[i] - cal(n - cnt[i])<<endl;
	}
	return 0;
}


Measured memory_bytes: 37112
data = [None] * 4
for i in xrange(4):
    data[i] = [None] * 3
    for j in xrange(3):
        data[i][j] = [0] * 10

n = input()
for i in xrange(n):
    line = map(int, raw_input().split())
    data[line[0] - 1][line[1] - 1][line[2] - 1] += line[3]

for i in xrange(4):
    for j in xrange(3):
        s = ""
        for k in xrange(10):
            s += ' '
            s += str(data[i][j][k])
        print s
    if i < 3:
        print '#' * 20

Measured memory_bytes: 6472
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
ans = 0
s = [0]
for i in range(n):
    s.append(s[i] + a[i])

t = Counter(s).most_common()

def comb(n, r):
    a = 1
    for i in range(n-r+1, n+1):
        a *= i
    for i in range(1, r+1):
        a //= i
    return a

for p in t:
    ans += comb(p[1], 2)
print(ans)


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

using namespace std;
using ll =long long;
typedef pair<int,int> P;
#define SORT(a) sort((a).begin(),(a).end())
#define REV(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
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; }

void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}
 
//Write From this Line

//const ll mod = 1e9+7;
//const ll mod = 998244353;
int main()
{
	int n;
	cin >> n;
	vector<P> a(n);
	rep(i,n) cin >> a[i].second >> a[i].first; // 締切,所要時間
	SORT(a);
	int time = 0;
	rep(i,n){
		if(time + a[i].second <= a[i].first){
			// 間に合う
			time += a[i].second;
		} else {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
}


Measured memory_bytes: 4776
n,k=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7
count=k

B,C=[],[]
for i in A:
    if i<=0:B.append(i)
    else:C.append(i)
B.sort(key=lambda x:abs(x))
C.sort()

ans,flag=1,1
while k!=0:
    if k>=2:
        if len(B)>=2 and len(C)>=2:
            if B[-1]*B[-2]>C[-1]*C[-2]:
                ans *=B.pop()*B.pop()
                k -=2
            else:
                ans *=C.pop()
                k -=1
        elif len(B)>=2:
            ans *=B.pop()*B.pop()
            k -=2
        elif len(C)>=2:
            ans *=C.pop()*C.pop()
            k -=2
        else:flag=0;break
    else:
        if len(C)>0:
            ans *=C.pop()
            k -=1
        else:flag=0;break
    ans %=mod

if flag:print(ans)
else:
    ans=1
    A.sort(reverse=True)
    for i in range(count):
        ans *=A[i]
        ans %=mod
    print(ans)

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

int main() {
  int N, P, W, G, Y;
  P = 0;
  W = 0;
  G = 0;
  Y = 0;
  string S;
  cin >> N;

  for (int i = 0; i < N; i++) {
    cin >> S;
    if (S == "P")
      P = 1;
    if (S == "W")
      W = 1;
    if (S == "G")
      G = 1;
    if (S == "Y")
      Y = 1;  
  }
  if (P+W+G+Y == 3)
    cout << "Three" << endl;
  if (P+W+G+Y == 4)
    cout << "Four" << endl;
}


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

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define S(x) (int)(x).size()
#define L(x) (int)(x).length()
#define ld long double
#define mem(x,y) memset(x,y,sizeof x)


const int mod = 1e9+7;
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;

int state[100009];
void solve()
{
	ll n,x,m;
	cin>>n>>x>>m;
	ll ans=0;
	vector<int> v;
	int len=0;
	mem(state,-1);
	while(state[x]==-1 && n)
	{
		state[x]=len;
		v.pb(x);
		ans+=x;
		x=x*x%m;
		n--;
		len++;
	}
	ll temp=0;
	for(int i=state[x];i<len;i++) temp+=v[i];
	len = len-state[x];
	//cout<<temp<<'\n';
	ans+=temp*(n/len);
	n%=len;
	for(int i=0;i<n;i++) ans+=v[state[x]+i];
	cout<<ans<<'\n';
}
//12722645
//9999998970
//9999999756
//492443256176507
int main()
{
	IOS
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
}


Measured memory_bytes: 4124
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
using ll = long long;
int INF = 1000000009;
int main()
{
    string s;
    cin >> s;
    int r = 0, b = 0;
    rep(i, s.size())
    {
        s[i] == '1' ? r++ : b++;
    }
    cout << 2*min(r, b) << endl;
}

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

int main(void) {
  string s;
  cin >> s;
  int p = 0, g = 0;
  int ans = 0;

  rep(i,s.size()) {
    if(p+1 <= g) {
      p++;
      if(s[i] == 'g') ans++;
    } else {
      g++;
      if(s[i] == 'p') ans--;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3760
#include <bits/stdc++.h> 
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;
#define vbi vector<bool> 
#define mod 1000000007
#define INF 1000000000
#define db double
#define all(x) x.begin(),x.end()
#define mp make_pair
#define pb push_back
#define sd second
#define ft first
#define ms(x,v) memset(x,v,sizeof x)
#define endl '\n'
#define cnl cout<<endl;
#define frr(i,b) for(ll i=0; i<b;i++)
#define fb(i,b) for(ll i=b-1; i>=0; i--)
#define pi  3.141592653589793238
ll i,j,k;
ll ans;
vector<long int > tree[10000+1];
vector<long int > v;
vector<bool> visited(10000+1,0);
int main(){
   
  ll n; cin>>n;
  ll k; cin>>k;
  vl v(n); 
  frr(i,n) cin>>v[i];
  ll cnt=0;
  for(i=0;i<n;i++){
    if(v[i]>=k) cnt++;
  }
  cout<<cnt<<endl;

return 0;
}

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

using namespace std;

struct UnionFind {
    vector<long long> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    vector<long long> size; 

    UnionFind(long long N) : par(N), size(N){ //最初は全てが根であるとして初期化
        for(long long i = 0; i < N; i++){
            par[i] = i;
            size[i] = 1;
        } 
    }

    long long  root(long long  x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(long long x, long long y) { // xとyの木を併合
        long long rx = root(x); //xの根をrx
        long long ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける

        size[ry] += size[rx];
        /*
        cout  <<"in unite:";
        for (int i = 0; i< 4; i++){
            cout  << size[i] << " ";
        }       
        cout  <<"|" << size[rx] << " " << size[ry] <<  endl;
        */
    }

    bool same(long long x, long long y) { // 2つのデータx, yが属する木が同じならtrueを返す
        long long rx = root(x);
        long long ry = root(y);
        return rx == ry;
    }
    long long num(long long x) {
        return size[root(x)];
    }
};

int a[100001];
int b[100001]; 
//int ans[100001][100001];

int main() {
    long long n, m, k;
    cin >> n >> m >> k;
    vector<int> t[n];
    // long long a[m+1], b[m+1]; 
    //long long c[k+1], d[k+1]; 
    // long long ans[n+1][n+1];
    long long sum;

    UnionFind tree(n+1);
    //cout << n << " " << m << " " << k << endl;
    for (long long i = 0; i < m; i++){
        cin >> a[i] >> b[i];
        tree.unite(a[i]-1, b[i]-1);

        t[a[i]-1].push_back(b[i]-1);
        t[b[i]-1].push_back(a[i]-1);
    }

    for (long long i = 0; i < k; i++){
        cin >> a[i] >> b[i];
        if (tree.same(a[i]-1, b[i]-1)){
            t[a[i]-1].push_back(b[i]-1);
            t[b[i]-1].push_back(a[i]-1);
        }
    }

    for (int i = 0; i < n; i++){
        /*
        sum = 0;
        for (auto it = t[i].begin(); it != t[i].end(); ++it){
            sum 
        }
        */
        //cout << "DBG:" << i << " "<< tree.num(i) << " " << t[i].size() << endl;
        sum = tree.num(i) - t[i].size() -1;
        cout << sum << ' ';
    }

    return 0;
}


Measured memory_bytes: 9976
#include<bits/stdc++.h>#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,add=0,t2,t3=0;
	cin >> n;
	int t[n],x[n],y[n];
	for(int i=0;i<n;i++)
		cin >> t[i] >> x[i] >> y[i];
	for(int i=0;i<n;i++)
	{
		t2=t[i]-t3-abs(x[i]+y[i]-add);
		if(t2<0 || t2%2 != 0)
		{
			puts("No");
			return 0;
		}
		add=x[i]+y[i];
		t3=t[i];
	}
	puts("Yes");
	return 0;
}

Measured memory_bytes: 1408
n,p=map(int,input().split())
def factorize(n):
    f=[]
    p=2
    cnt=0
    while p**2<=n:
        while n%p==0:
            cnt+=1
            n=n//p
        if cnt!=0:
            f.append([p,cnt])
            cnt=0
        p+=1
    if n!=1:
        f.append([n,1])
    return f

A=factorize(p)
ans=1
for i in range(len(A)):
    ans*=A[i][0]**(A[i][1]//n)
print(ans)

Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct TCard
{
	char Suit;
	int  Number;
	bool operator==(const TCard& A)const;
};

bool TCard::operator==(const TCard& A)const
{
	return Suit == A.Suit && Number == A.Number;
}

bool CompareCards(const TCard& Small, const TCard& Large)
{
	return Small.Number < Large.Number;
}

typedef std::vector<TCard> TCards;

int Partition(TCards& A, int p, int r)
{
	TCard X = A[r];
	int i = p - 1;
	for(int j = p; j < r; j++){
		if(CompareCards(A[j], X) || A[j].Number == X.Number){
			i++;
			std::swap(A[i], A[j]);
		}
	}
	std::swap(A[i+1], A[r]);
	return i + 1;
}

void QuickSort(TCards& Cards, int p, int r)
{
	if(p < r){
		int q = Partition(Cards, p, r);
		QuickSort(Cards, p, q - 1);
		QuickSort(Cards, q + 1, r);
	}
}

std::string IsStable(const TCards& Sorted, TCards& Original)
{
	std::stable_sort(Original.begin(), Original.end(), CompareCards);
	if(Sorted == Original) return "Stable";
	return "Not stable";
}

int main()
{
	int Count;
	std::cin >> Count;
	TCards Cards(Count);
	for(int i=0; i < Count; i++){
		std::cin >> Cards[i].Suit;
		std::cin >> Cards[i].Number;
	}
	TCards Original = Cards;
	QuickSort(Cards, 0, Count - 1);
	std::cout << IsStable(Cards, Original) << std::endl;
	for(int i=0; i < Count; i++){
		std::cout << Cards[i].Suit << " " << Cards[i].Number << std::endl;
	}
	return 0;
}

Measured memory_bytes: 4636
#include <stdio.h>
int main(void)
{
    int N;
    scanf("%d", &N);
    N %= 10;
    switch (N) {
    case 3:
        printf("bon\n");
        break;
    case 0:
    case 1:
    case 6:
    case 8:
        printf("pon\n");
        break;
    default:
        printf("hon\n");
        break;
    }
    return 0;
}


Measured memory_bytes: 1660
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ll long long

const int N = 2e5 + 5;
const int MOD = 1e9 + 7;

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



int main()
{
	IOS;
	int t=1; //cin>>t;
	while(t--){
	    int n; cin>>n;
	    int a[n];
	    ll dp[n][n];
	    for(int i=0;i<n;i++){ cin>>a[i]; dp[i][i]=a[i];}
	    
	    for(int i=n-1;i>=0;i--) {
		  for(int j=i+1;j<n;j++) 
		  {
			dp[i][j] = max(a[i] - dp[i+1][j],a[j] - dp[i][j-1]);
		  }
	    }
 
	     cout<<dp[0][n-1];
	    
	    cout<<endl;
	}  
}

Measured memory_bytes: 49784
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long int

int main()
{
 	std::ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  	//ll tt;	cin>>tt;	while(tt--)
  	{
  		long double n;
  		cin>>n;

  		n/=3;

  		printf("%llf",n*n*n);
  	}
 	cerr<<" Execution : "<<(1.0*clock())/CLOCKS_PER_SEC<<"s \n";
    return 0;
  		
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;

ll height[51];
ll height2[51];
ll numpatties[51];
int N;
ll X;

ll count(int n, ll x) {
    int l = upper_bound(height2, height2 + n + 1, x - n) - height2 - 1;
    if (l < 0) return 0;
    ll ofs = x - height[l] - (n - l);
    if (ofs == 0) return numpatties[l];
    else if (ofs == 1) return numpatties[l] + 1;
    else return numpatties[l] + 1 + count(l, ofs - 1);
}

int main() {
    cin >> N >> X;
    height[0] = 1;
    numpatties[0] = 1; 
    for (int i = 1; i <= 50; i ++) {
        height[i] = height[i-1] * 2 + 3;
        numpatties[i] = numpatties[i-1] * 2 + 1;
    }
    for (int i = 0; i <= N; i ++) {
        height2[i] = height[i] - i;
    }
    cout << count(N, X) << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<utility>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<queue>
#include<stack>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)

using namespace std;

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

    ll N;
    cin >> N;
    vector<ll> a(N);
    bool first = false;
    Rep (i, N) {
        cin >> a[i];
        if (a[i] % 2) first = true;
    }

    // if (-1) cout << -1 << "\n";

    if (first) cout << "first" << "\n";
    else cout << "second" << "\n";
}


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

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = GetLongNumArray();
            var A = input[0];
            var B = input[1];
            var C = input[2];
            var K = GetLongNum();

            for (int i = 0; i < K; i++)
            {
                if (A < B && A < C)
                {
                    if (B < C)
                    {
                        Console.WriteLine("Yes");
                        return;
                    }
                    else
                    {
                        C = C * 2;
                        continue;
                    }
                }
                if (B < C)
                {
                    B = B * 2;
                    continue;
                }
                else
                {
                    C = C * 2;
                    continue;
                }
            }

            if (A < B && A < C && B < C)
            {
                Console.WriteLine("Yes");
                return;
            }

            Console.WriteLine("No");
        }

        private static long[] GetLongNumArray()
        {
            var input = Console.ReadLine().Split(' ');
            return input.Select(x => long.Parse(x)).ToArray();
        }

        private static long GetLongNum()
        {
            return long.Parse(Console.ReadLine());
        }

        private static string[] GetStringArray()
        {
            return Console.ReadLine().Split(' ');
        }

        private static string GetString()
        {
            return Console.ReadLine();
        }
    }
}


Measured memory_bytes: 28216
def solve():
	n,*l=map(int,open(0).read().split())
	con=[[] for _ in range(n)]
	dist=[None]*n
	dist[0]=0
	for a,b,c in zip(*[iter(l)]*3):
		con[a-1].append((b-1,c%2))
		con[b-1].append((a-1,c%2))
 
	stk=[0]
	while stk:
		cur=stk.pop()
		for nxt,d in con[cur]:
			if dist[nxt]==None:
				stk.append(nxt)
				dist[nxt]=(dist[cur]+d)%2

	print(*dist,sep="\n")

if __name__=="__main__":
	solve()

Measured memory_bytes: 49196
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, a, b) for(int i=a; i<b; i++)

#define N 112345
struct bit{
	int a[N];
	void init(){
		fill(a, a+N, 0);
	}

	void add(int i, int x){
		for(; i<N; i|=i+1){
			a[i]+=x;
		}
	}
	
	int sum(int i){
		int ret=0;
		for(i--; i>=0; i=(i&(i+1))-1){
			ret+=a[i];
		}
		return ret;
	}
	
	int sum(int i, int j){
		return sum(j)-sum(i);
	}
};

bit b;

int main(){
	b.init();
	int n, q;
	scanf("%d%d", &n, &q);
	REP(i, q){
		int c, x, y;
		scanf("%d%d%d", &c, &x, &y);
		if(c==0) b.add(x-1, y);
		else printf("%d\n", b.sum(x-1, y));
	}
}

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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<typename T>
class BinaryHeap{
    vector<T>dat;
    public:
    void push(T t){
        int k=dat.size();
        dat.push_back(t);
        while(k&&dat[(k-1)/2]<dat[k]){
            swap(dat[(k-1)/2],dat[k]);
            k=(k-1)/2;
        }
    }

    T top(){
        assert(dat.size()>0);
        return dat[0];
    }

    void pop(){
        assert(dat.size()>0);

        dat[0]=dat.back();
        dat.pop_back();
        int k=0;
        while(true){
            if(k*2+2<dat.size()&&dat[k*2+2]>max(dat[k*2+1],dat[k])){
                swap(dat[k],dat[k*2+2]);
                k=k*2+2;
            }
            else if(k*2+1<dat.size()&&dat[k*2+1]>dat[k]){
                swap(dat[k],dat[k*2+1]);
                k=k*2+1;
            }
            else break;
        }
    }
};

signed main(){
    BinaryHeap<int>bh;
    char str[10];
    while(scanf("%s",str),str[2]!='d'){
        if(str[0]=='i'){
            int a;
            scanf("%lld",&a);
            bh.push(a);
        }
        else{
            printf("%lld\n",bh.top());
            bh.pop();
        }
    }
    return 0;
}

Measured memory_bytes: 11100