akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	vector<int> a(n);
	rep(i,n) cin >> a.at(i);
	sort(a.begin(),a.end());
	int ans=0,cnt=1;
	rep(i,n-1){
		if(a.at(i)==a.at(i+1)) cnt++;
		else{
			if(cnt%2==1) ans++;
			cnt=1;
		}
	}
	if(cnt%2==1) ans++;
	cout << ans << endl;
}

Measured memory_bytes: 640
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan = new java.util.Scanner(System.in);
        int a1 = scan.nextInt();
        int a2 = scan.nextInt();
        int a3 = scan.nextInt();
        int b = a1 + a2 + a3;
        if(b >= 22){
            System.out.println("bust");
        }else{
            System.out.println("win");
        }
    }
}

Measured memory_bytes: 22612
#include <iostream>
#include <string>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstring>

using namespace std;

int main(int argc, char* argv[]) {

	string S;
	string wrk;
	int diff=0;
	int ans = 9999;

	cin >> S;

	for(unsigned i=0;i < S.size() - 2;i++){
		wrk = S.substr(i,3);
		diff = atoi(wrk.c_str());
		if(abs(diff - 753) < ans){
			ans = abs(diff - 753);
		}
	}

	cout << ans << endl;

	return 0;

}



Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Longest Steps
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0517

"""
import sys


def solve(cards):
    if len(cards) == 1:
        return 1
    has_white = True if cards[0] == 0 else False
    res = []
    t = []
    prev = cards[has_white] - 1
    for c in cards[has_white:]:
        if c == prev + 1:
            t.append(c)
        else:
            res.append(t)
            t = [c]
        prev = c
    res.append(t)

    ans = max(len(r) + has_white for r in res)
    if has_white:
        for a, b in zip(res, res[1:]):
            if a[-1] + 2 == b[0]:
                ans = max(ans, len(a)+len(b)+1)
    return ans


def main(args):
    while True:
        n, k = map(int, input().split())
        if n == 0 and k == 0:
            break
        cards = sorted([int(input()) for _ in range(k)])
        ans = solve(cards)
        print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])



Measured memory_bytes: 11312
import sys
input = sys.stdin.readline
N = int(input())
mod = 998244353
a = []
ys = []
for _ in range(N):
  x, y = map(int, input().split())
  a.append((x, y))
  ys.append(y)

def compress(init_val):
  t = sorted(set(init_val))
  d = dict([[t[i], i] for i in range(len(t))])
  res = [0] * len(init_val)
  for i in range(len(init_val)): res[i] = d[init_val[i]]
  return res

ys = compress(ys)
a = [(a[i][0], ys[i] + 1) for i in range(N)]
a.sort()

class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def lowerbound(self, s):
    x = 0
    y = 0
    for i in range(self.n.bit_length(), -1, -1):
      k = x + (1 << i)
      if k <= self.n and (y + self.data[k] < s):
        y += self.data[k]
        x += 1 << i
    return x + 1

fwkl = BIT(N)
fwkr = BIT(N)
ls = [0] * N
rs = [0] * N
for i in range(N):
  ls[i] = fwkl.sum(a[i][1])
  fwkl.add(a[i][1], 1)
for i in range(N - 1, -1, -1):
  rs[i] = fwkr.sum(a[i][1])
  fwkr.add(a[i][1], 1)

table = [pow(2, i, mod) - 1 for i in range(N)]
pw = lambda x: table[x]
#print(ls, rs)
res = 0
for i in range(N):
  ld, rd = ls[i], rs[i]
  lu = i - ld
  ru = N - i - rd - 1
  for k in range(16):
    d = [0] * 4
    t = 1
    if k & 1:
      t *= pw(ld)
      t %= mod
      d[0] = 1
      d[2] = 1
    if k & 2:
      t *= pw(lu)
      t %= mod
      d[0] = 1
      d[3] = 1
    if k & 4:
      t *= pw(rd)
      t %= mod
      d[1] = 1
      d[2] = 1
    if k & 8:
      t *= pw(ru)
      t %= mod
      d[1] = 1
      d[3] = 1
    res += t * (2 ** (sum(d) == 4))
    res %= mod
print(res)

Measured memory_bytes: 164800
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long ;
int main(){
    int n;
    ll ans=1;
    cin >> n;
    for(int i=1; i<=n; i++){
        ans = ans*i%1000000007;
    }
    cout << ans << endl;
}

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

int main() {
    int n;
    cin >> n;
    vector<int> d(n);
    for (int i = 0; i < n; i++) {
        cin >> d.at(i);
    }

    sort(d.begin(), d.end());
    int count = 1;
    for (int i = 1; i < n; i++) {
        if (d.at(i) == d.at(i - 1)) {
            continue;
        }
        count++;
    }

    cout << count << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e9;

int main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if(a + b == c + d)
        cout << "Balanced" << endl;
    else if(a + b > c + d)
        cout << "Left" << endl;
    else
        cout << "Right" << endl;
    return 0;
}


Measured memory_bytes: 3604
#include <stdio.h>

int main(void){
    int a,b;
    scanf("%d %d",&a,&b);
    int i;
    if(a>=b){
        for(i=0;i<a;i++)
            printf("%d",b);
    }else{
        for(i=0;i<b;i++)
            printf("%d",a);
    }
    puts("");
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define ld long double
#define endl '\n'
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpii vector<pii>
#define gr vector<vpii>
#define str string
#define mask vector<bool>
#define vs vector<str>
#define pq priority_queue
#define ordered_set_of(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
#define fi first
#define se second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define nub(x) x.resize(unique(all(x)) - x.begin())
#define TWO class T1, class T2
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define MOD 998244353
#define GAME_OVER return 0
using namespace std;
using namespace __gnu_pbds;
char _$ = ' ';
struct sep {sep(char c) {_$ = c;}};
ostream& operator<<(ostream& o, sep s) {return o;}
template<TWO> ostream& operator<<(ostream& o, pair<T1, T2> x) {return o << x.fi << ' ' << x.se;}
template<TWO> istream& operator>>(istream& i, pair<T1, T2>& x) {return i >> x.fi >> x.se;}
template<class T> ostream& operator<<(ostream& o, vector<T> x) {for (auto it : x) o << it << _$; return o;}
template<class T> istream& operator>>(istream& i, vector<T>& x) {for (auto& it : x) i >> it; return i;}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, s;
    cin >> n >> s;
    vi a(n);
    cin >> a;
    vvi dp(n + 1, vi(s + 1));
    dp[0][0] = 1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= s; j++)
        {
            dp[i + 1][j] = (dp[i + 1][j] + 2 * dp[i][j]) % MOD;
            if (j + a[i] <= s)
                dp[i + 1][j + a[i]] = (dp[i + 1][j + a[i]] + dp[i][j]) % MOD;
        }
    cout << dp[n][s] << endl;
    GAME_OVER;
}

Measured memory_bytes: 73688
def solve(n, arr):
    ans_arr = [0]
    for i in range(0, n-1):
        if arr[i] > arr[i + 1]:
            diff = arr[i] - arr[i + 1]
            ans_arr.append(diff)
            arr[i + 1] += diff
        else:
            ans_arr.append(0)
    return sum(ans_arr)

if __name__ == "__main__":
    n = int(input())
    arr = list(map(int, input().split(' ')))
    print(solve(n, arr))

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

int main() {
    string x;
    int a;
    while (1) {
        cin >> x;
        if (x == "0")
            break;
        a = 0;
        for (int i = 0; i < x.length(); i++) 
            a += x[i] - '0';
        cout << a << endl;
    }
}

Measured memory_bytes: 1188
use std::io::*;
use std::str::FromStr;

struct Scanner<R: Read> {
    reader: R,
}

#[allow(dead_code)]
impl<R: Read> Scanner<R> {
    fn new(reader: R) -> Scanner<R> {
        Scanner { reader: reader }
    }

    fn safe_read<T: FromStr>(&mut self) -> Option<T> {
        let token = self.reader.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            token.parse::<T>().ok()
        }
    }

    fn read<T: FromStr>(&mut self) -> T {
        if let Some(s) = self.safe_read() {
            s
        } else {
            writeln!(stderr(), "Terminated with EOF").unwrap();
            std::process::exit(0);
        }
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let n = sc.read();
    let m = sc.read();
    let a: Vec<Vec<i64>> = (0..n).map(|_| (0..m).map(|_| sc.read()).collect()).collect();
    let b: Vec<i64> = (0..m).map(|_| sc.read()).collect();
    for row in &a {
        let x: i64 = row.iter().zip(b.iter()).map(|(a, b)| a * b).sum();
        println!("{}", x);
    }
}



Measured memory_bytes: 5048
//hinagata.cpp
//作成日
//更新日
//目的
//手段
/*includes*/
#include <bits/stdc++.h>
/*namespace*/
using namespace std;
using ll= long long;
/*define macro*/
#define REP(i,n) for(ll i=0;i<(n);i++)
#define REPi(i,a,b) for(ll i=(a);i<(b);i++)
#define REPRi(i,a,b) for(ll i=(a);i>(b);i--)
#define ALL(x) (x).begin(),(x).end()

int main(){
    int N,M;
    cin>>N>>M;
    vector<int> P(N,-1);
    REP(i,M){
        int S,C;
        cin>>S>>C;
        S-=1;
        if(P[S]==-1){
            P[S]=C;
        }else if(P[S]==C){
            P[S]=C;
        }else{
            cout<<-1<<endl;
            return 0;
        }
    }
    //ゼロの例外設定
    if(N==1&&(P[0]==-1||P[0]==0)){
        cout<<0<<endl;
        return 0;
    }
    int zeroflag=0;
    REP(i,N){
        if(P[i]==0&&zeroflag==0){
            cout<<-1<<endl;
            return 0;
        }else if(P[i]==-1&&zeroflag==0){
            P[i]=1;
            zeroflag=1;
        }else if(P[i]==-1){
            P[i]=0;
        }else{
            zeroflag=1;
        }
    }
    int ans=0;
    REP(i,N){
        ans*=10;
        ans+=P[i];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;


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

		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();

      	if (A - B > C) {
          	System.out.println(0);
        } else {
			System.out.println(C - A + B);
        }
	}
}

Measured memory_bytes: 20820
n = int(input())
bs = [int(x) for x in input().split()]
sign = 1
a_2 = bs[0]
for b in bs[1:]:
    a_2 += sign*b
    sign *= -1

ans = str(a_2) + ' '
for i in range(n-2):
    a_2 = 2*bs[i+1] - a_2
    ans += str(a_2) + ' '
ans = str(2*bs[i+2] - a_2) + ' ' + ans
print(ans)

Measured memory_bytes: 14024
#include <stdio.h>


int main(){
  int i,n,q;
  
 /** S[]
   * the number of S[]
   */
  scanf("%d", &n);
  int S[n+1]; //+1 is for the sentinel.
  //input data
  for(i=0;i<n;i++){
    scanf(" %d", &S[i]);
  }

 /** T[]
   * the number of T[]
   */
  scanf("%d", &q);
  int T[q];
  //input data
  for(i=0;i<q;i++){
    scanf(" %d", &T[i]);
  }

  /* Linear Search
  */
  int cnt=0;
  for(i=0;i<q;i++){
    int key = T[i]; //??????????????¢?´¢
    S[n] = key; //put the sentinel
    int j = 0;
    while(S[j]!=key){
        j++;
    }
    if(j==n){
      continue;
    }else{
      cnt++;
    }
  }
  
  printf("%d\n",cnt);
  
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 
using vs = vector<string>;
using vvs = vector<vs>; 
using vc = vector<char>;
using vvc = vector<vc>; 
using vb = vector<bool>;
using vvb = vector<vb>; 

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; }
const long long INF = 1LL << 60;

#define rep(i,n) ;for( int i =0; i < n ; i ++)
#define all(a) a.begin(),a.end()
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i=a;i<b;i++)
#define pri(a)  printf("%.14lf\n",a);
#define MOD 1000000007
bool is_int_lround(double x){
  return std::lround(x)==x;
}
ll keta(ll x){
  ll n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}

ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;//繰り返し二乗法
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll kaijo(ll x){
  ll z=1;
  if(x==0){
    return 1;
  }
  while(x>0){
    z *=x;
    z %=MOD;
    x--;
  }
  return z;
}
ll yakusu_num(ll n){
  vl yakusu(n+1,1);
  for(ll i=2;i*i<=n;i++){ 
    while(n%i==0){
      n /=i;
      yakusu[i]++;
    }
  }
  if(n!=1)yakusu[n]++;
  ll num=1;
  for(ll i=0;i <=n;i++){
    num*=yakusu[i];
  }
  return num;
}


//cout<<""<<endl;
int main(){
  ll N;cin>>N;
  vl a(N),b(N),c(N);
  rep(i,N)cin>>a[i]>>b[i]>>c[i];
  vl da(N+1),db(N+1),dc(N+1);
  da[0]=a[0];db[0]=b[0];dc[0]=c[0];
  rep(i,N-1){
    da[i+1]=max(db[i]+a[i+1],dc[i]+a[i+1]);
    db[i+1]=max(dc[i]+b[i+1],da[i]+b[i+1]);
    dc[i+1]=max(db[i]+c[i+1],da[i]+c[i+1]);
  }
  cout<< max(da[N-1],max(db[N-1],dc[N-1]))<<endl;
}





Measured memory_bytes: 8016
#include<cstdio>
#include<algorithm>

using namespace std;

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    int p[m];
    pair<int, int> y[m];
    for(int i = 0; i < m; i++){
        scanf("%d %d", &p[i], &y[i].first);
        y[i].second = i;
    }
    sort(y, y + m);
    int pref[n];
    int ans[m];
    fill(pref, pref + n, 0);
    fill(ans, ans + m, 0);
    for (int i = 0; i < m; i++){
        pref[p[y[i].second]-1]++;
        ans[y[i].second] = pref[p[y[i].second]-1];
    }
    // for(int i = 0; i < m; i++){
    //     printf("%d %d\n", y[i].first, y[i].second);
    //     printf("%d\n", ans[i]);
    // }
    for(int i = 0; i < m; i++){
        printf("%06d%06d\n", p[i], ans[i]);
    }

}

Measured memory_bytes: 3328
<?php
$input = explode(' ', trim(fgets(STDIN)));
$result[] = floor($input[0] / $input[1]);
$result[] = $input[0] % $input[1];
$result[] = sprintf('%.10f', $input[0] / $input[1]);
echo implode(' ', $result);
//var_dump($result);
?>

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

int main(){
	int n,m,t[128],x[128],p[128];
	int ans[128];

	for(int i=0;i<128;i++){
		ans[i] = 0;
	}

	cin >>n;
	for(int i=0;i<n;i++)
		cin >> t[i];
	cin >>m;
	for(int i=0;i<m;i++)
		cin >> p[i] >> x[i];

	for(int i=0;i<m;i++){
		int tmp = t[p[i]-1];
		t[p[i]-1] = x[i];
		for(int j=0;j<n;j++){
			ans[i] += t[j];
		}
		t[p[i]-1] = tmp;
	}

	for(int i=0;i<m;i++){
		cout << ans[i] <<endl;
	}
	return 0;
}

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

// @@ !! LIM()

int main(/* int argc, char *argv[] */) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N; cin >> N;
  vector<ll> A(N), g1(N), g2(N);
  for (ll i = 0; i < N; i++) cin >> A[i];
  g1[0] = A[0];
  for (ll i = 1; i < N; i++) g1[i] = gcd(g1[i-1], A[i]);
  g2[N-1] = A[N-1];
  for (ll i = N-2; i >= 0; i--) g2[i] = gcd(g2[i+1], A[i]);
  ll ans = max(g1[N-2], g2[1]);
  for (ll i = 1; i+1 < N; i++) {
    ll p = gcd(g1[i-1], g2[i+1]);
    ans = max(ans, p);
  }
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 5552
// -----------------------------------
// Author     : MatsuTaku
// Affiliation: Tokushima University
// Country    : Japan
// Date       : 04/09/2020
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

  int r; cin>>r;
  cout << 3*r*r << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main () {
  int N, M,answer=0;
  int y=0;
  int aaa=0;
  cin >> N >> M;
  int p[M]={0};
  int ss[M][N]={{0}};
  int k[M]={0};
  for (int j = 0; j < M; j++) {
    cin>>k[j];
    for (int i = 0; i < k[j]; i++) {
      cin>>ss[j][i];}}
    for (int i = 0; i < M ; i++) {
    cin>>p[i];}
  // すべての選び方を試して、総和がKになるものがあるかを調べる
  for (int tmp = 0; tmp < (1 << N); tmp++) {
    bitset<10> s(tmp);  
  for( int i=0; i<M;i++){
  for( int j=0; j<k[i];j++){
     if (s.test(ss[i][j]-1)) {
        answer++;
      }
    }
    if(answer%2==p[i]){
    aaa++;}
    answer=0;}
    if(aaa==M){
    y++;}
    aaa=0;}
    cout << y << endl;
}


Measured memory_bytes: 256
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n,k = iim()
A = iil()
print((n+k-3)//(k-1))

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

using namespace std;

using ll = long long;

int f(ll a, ll b)
{
    int ret=0;
    if(a>b){
        while(a>0){
            a/=10;
            ret++;
        }
    }
    else{
        while(b>0){
            b/=10;
            ret++;
        }
    }
    return ret;
}

signed main(signed arg, char *args[])
{
    ll N;
    cin>>N;
    int ans;
    for(ll i=1;i*i<=N;i++){
        if(N%i==0) ans=f(i,N/i);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, d = map(int, readline().split())

    ans = 0

    for _ in range(n):
        x, y = map(int, readline().split())
        if (x ** 2 + y ** 2) <= d ** 2:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 68512
import java.util.Scanner;

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

        int a = sc.nextInt();
        int b = sc.nextInt();
        int k = sc.nextInt();

        // Brute force because a, b <= 100

        int count = 0;

        for (int i = Math.min(a, b); i >= 1; i--) {
            if (a % i == 0 && b % i == 0) {
                count++;
            }

            if (count == k) {
                System.out.println(i);
                return;
            }
        }
    }
}

Measured memory_bytes: 22228
n = int(input())
a = list(map(int,input().split()))

dp_table = [0 for i in range(n)]
dp_table[1] = abs(a[0] - a[1])
for i in range(2,len(a)):
    dp_table[i] = min(dp_table[i-2]+abs(a[i-2]-a[i]),dp_table[i-1]+abs(a[i-1]-a[i]))
print(dp_table[-1])


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

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

signed main() {
    string s;
    cin>>s; 
    ll x=0, y=0;
    for(auto c: s){
        if (c == '0') x++;
        else y++;
    }

    cout<<min(x,y)*2<<endl;
    return 0;
}


Measured memory_bytes: 512
length = int(input())
target = [int(n) for n in input().split(" ")]
even,odd = 0,0
for l in range(length):
    if target[l] % 2 == 0:
        even += 1
    else:
        odd += 1
if odd % 2 == 0:
    print("YES")
else:
    print("NO")

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

ll N, K;
P in[100000];

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

	sort(in, in + N);

	ll ct = 0;
	for (int i = 0; i < N; i++) {
		if (ct <= K && K <= ct + in[i].second) {
			cout << in[i].first << endl;
			break;
		}
		ct += in[i].second;
	}

	return 0;
}

Measured memory_bytes: 1792
#include<stdio.h>

#define N 100000

int abs(int a);

int main(void){
	int i;
	int j;
	int n;
	int k;
	int h[N];
	int min[N];
	scanf("%d %d",&n,&k);
	for(i=0;i<n;i++){
		scanf("%d",&h[i]);
	}
	min[0]=0;
	for(i=1;i<n;i++){
		min[i]=min[i-1]+abs(h[i]-h[i-1]);
		if(i<k){
			for(j=1;j<=i;j++){
				if(min[i]>(min[i-j] + abs(h[i]-h[i-j]))){
					min[i]=min[i-j] + abs(h[i]-h[i-j]);
				}
			}
		}else{
			for(j=1;j<=k;j++){
				if(min[i]>(min[i-j] + abs(h[i]-h[i-j]))){
					min[i]=min[i-j] + abs(h[i]-h[i-j]);
				}
			}
		}
	}
	printf("%d",min[n-1]);
	return 0;
}

int abs(int a){
	int ret;
	if(a<0){
		ret=(-1)*a;
	}else{
		ret=a;
	}
	return ret;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (int i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using PL = pair<long long, long long>;
const int INF = 1001001007;
const int MOD = 1000000007;
template <typename T>
void printvec(vector<T> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

int main(){
    int n; cin >> n;
    vector<int> ar(n,0);
    repp(i,n,1) cin >> ar[i];
    vector<int> jo(n);
    repp(i,n,1){
        jo[ar[i]-1]++;
    }
    rep(i,n) cout << jo[i] << endl;
}

Measured memory_bytes: 4788
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <istream>
#include <set>
#include <queue>
#define rep0(i,n) for (long long int i = 0; i <= (n); ++i)
#define rep1(i,n) for (long long int i = 1; i <= (n); ++i)
#define REP(a,b) for (long long int i = a; i <= (b); ++i) 
#define MOD 1000000007
using namespace std;
typedef long long ll;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int a, b, c, x;
	int count = 0;
	cin >> a >> b >> c >> x;
	rep0(i, a) {
		rep0(j, b) {
			rep0(k, c) {
				if (i * 500 + j * 100 + k * 50 == x)
					++count;
			}
		}
	}
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PB push_back
#define MP std::make_pair
#define FI first
#define SE second
#define M 1000005
#define INF 1000000000
int K,n,lim=500,col[505][505];
int read(){
	char c=getchar();int ans=0;
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') ans=ans*10+c-'0',c=getchar();
	return ans;
}
void Write(int x){
	if (x<10) putchar(x+'0');
	else Write(x/10),putchar(x%10+'0');
	return;
}
int main(){
	K=read();
	if (K<=lim){
		printf("%d\n",n=K);
		for (int i=1;i<=n;i++,putchar('\n'))
			for (int j=1;j<=n;j++,putchar(' ')) Write(i);
	}
	else {
		printf("%d\n",n=lim);
		for (int i=1;i<=n;i++){
			int x=i;
			for (int j=1;j<=n;j++,x=x%n+1) col[x][j]=i;
		}
		K-=lim;
		for (int i=1;i<=n&&K;i++){
			int x=i,flag=1;
			for (int j=1;j<=n;j++,x=x%n+1,flag^=1)
				if (flag) col[x][j]=i+n;
			K--;
		}
		for (int i=1;i<=n;i++,putchar('\n'))
			for (int j=1;j<=n;j++,putchar(' ')) Write(col[i][j]);
	}
	return 0;
}


Measured memory_bytes: 4752
#include <cstdio>
#include <cmath>

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

inline char tc(){
  static char fl[100],*A=fl,*B=fl;
  return A==B&&(B=(A=fl)+fread(fl,1,100,stdin),A==B)?EOF:*A++;  
}
inline int read(){
  int a=0;static char c;
  while((c=tc())<48||c>57);
  while(c>=48&&c<=57)a=a*10+c-48,c=tc();
  return a;
}
int h[100001];
int main(){
  int n=read(),a=read(),b=read();a-=b;
  double a_=1.0/a;
  rep(i,n)h[i]=read();
  int left=0,right=1000000000;
  ll temp,cnt=0,mid;
  while (right>left+1) {
    mid=(right+left)>>1;
    cnt=0;
    rep(i,n){
      temp=h[i]-b*mid+a-1;
      if(temp>0)cnt+=temp*a_;
    }
    if(cnt<=mid)right=mid;
    else left=mid;
  }
  printf("%d\n",right);
  return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<cstring>
#include<algorithm>
using namespace std;

int rule[100005];
unsigned long long int sum[100005];
vector<int> path[200005];
queue<int> q1;
priority_queue<pair<unsigned long long int,int>,vector<pair<unsigned long long int,int> >,greater<pair<unsigned long long int,int> > > pq1;

int main(){
	int n,m,t,s;
	int i,j,k;
	unsigned long long int a,b,c;
	int co[2];
	memset(sum,-1,sizeof(sum));
	cin>>n>>m>>t>>s;
	cin>>co[0]>>co[1];
	for(i=0;i<t;i++){
		cin>>a;
		a--,rule[a]=2;
		q1.push(a);
	}
	for(i=0;i<m;i++){
		cin>>a>>b;
		a--,b--;
		path[a].push_back(b);
		path[b].push_back(a);
	}
	
	for(i=0;i<s+1;i++){
		a=q1.size();
		for(j=0;j<a;j++){
			b=q1.front(),q1.pop();
			if(rule[b]==1)continue;
			if(rule[b]==2 && i!=0)continue;
			if(rule[b]==0)rule[b]=1;
			for(k=0;k<path[b].size();k++){
				if(rule[path[b][k]]!=0)continue;
				q1.push(path[b][k]);
			}
		}
	}
	pq1.push(make_pair(0,0));
	while(!pq1.empty()){
		a=pq1.top().first,b=pq1.top().second,pq1.pop();
		if(sum[b]!=-1)continue;
		sum[b]=a;
		for(i=0;i<path[b].size();i++){
			if(sum[path[b][i]]!=-1 || rule[path[b][i]]==2)continue;
			pq1.push(make_pair(a+co[rule[path[b][i]]],path[b][i]));
		}
	}
	cout<<(sum[n-1]-co[rule[n-1]])<<endl;
	return 0;
}

Measured memory_bytes: 13276
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
int main()
{
    ll n,d;
    cin>>n>>d;
    ll x[n],y[n];
    int count=0;
    for(int i=0;i<n;i++)
    {
        cin>>x[i]>>y[i];
        ll sum=(x[i]*x[i]) +(y[i]*y[i]);
        double dis=sqrt(sum);
        if(dis<=d)
        {
        count++;
        }
    
    }
    cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 6744
import sys
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


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


def readstrs():
    return input().split()


def main():
    A, B, C = readnums()
    K = readint()
    while K:
        if A >= B:
            B *= 2
            K -= 1
        elif B >= C:
            C *= 2
            K -= 1
        else:
            break

    if A < B < C:
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    main()


Measured memory_bytes: 9184
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <map>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
// 昇順sort
#define sorti(x) sort(x.begin(), x.end())
// 降順sort
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

typedef pair<int, int> pi;

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

  vector<pi> e(100001), o(100001);
  for (int i = 1; i <= n; ++i) {
    ll t; cin >> t;
    if (i % 2 == 0) {
      e[t].second = t; e[t].first++;
    } else {
      o[t].second = t; o[t].first++;
    }
  }

  sorti(e), sorti(o);

  if (e.back() == o.back()) {
    cout << min(n - e[100000].first - o[99999].first, n - o[100000].first - e[99999].first);
  } else {
    cout << n - e.back().first - o.back().first << endl;
  }
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <cstring>

#define MAX 100005

using namespace std;

vector<int> stones;

int frogdp();

int n;

int dp[MAX];

int main() {

    scanf("%d", &n);

    for (int i; i < n; ++i){
        int x;
        scanf("%d", &x);
        stones.push_back(x);
    }

    memset(&dp, -1, sizeof dp);

    printf("%d", frogdp());
}

int frogdp()
{
    dp[0] = 0;
    for (int i = 1; i < n; ++i) {
        int a = abs(stones[i] - stones[i - 1]) + dp[i - 1];
        int b = i - 2 < 0 ? a+1 : abs(stones[i] - stones[i - 2]) + dp[i - 2];

        dp[i] = min(a, b);
    }

    return dp[n-1];
}

Measured memory_bytes: 1144
#include<bits/stdc++.h>
using namespace std;
vector<int> g[200020];
int cnt[200020];
bool used[200020];
int ptr;
int z;
void dfs(int i)
{
	z++;
	used[i]=true;
	for(int j=0;j<g[i].size();j++)
		if(!used[g[i][j]])
			dfs(g[i][j]);
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i=1;i<=n;i++)
		if(!used[i]){
			z=0;
			dfs(i);
			cnt[ptr++]=z;
		}
	int ans=-1;
	for(int i=0;i<ptr;i++)
		ans=max(ans,cnt[i]);
	cout<<ans<<endl;
	return 0;
 } 

Measured memory_bytes: 20868
#include <stdio.h>

typedef struct{
  char moji;
  int num;
  int count;
} Card;

int partition(Card [], int, int);
void quicksort(Card [], int, int);

int main(){
  int n, i, stable = 1;
  Card A[100000];

  scanf("%d", &n);
  for(i=0; i<n; i++){
    scanf(" %c%d", &A[i].moji, &A[i].num);
    A[i].count = i;
  }

  quicksort(A, 0, n-1);

  for(i = 1; i < n; i++){
    if(A[i].num == A[i-1].num && A[i].count < A[i-1].count){
      stable = 0;
      break;
    }
  }

  if(stable) printf("Stable\n");
  else printf("Not stable\n");
  for(i = 0; i < n; i++) printf("%c %d\n", A[i].moji, A[i].num);
  
  return 0;
}

int partition(Card A[], int p, int r){
  int x, i, j;
  Card temp;
  x = A[r].num;
  i = p-1;
  for(j=p; j<r; j++){
    if(A[j].num <= x){
      i++;
      temp = A[i];
      A[i] = A[j];
      A[j] = temp;
    }
  }
  temp = A[i+1];
  A[i+1] = A[r];
  A[r] = temp;
  
  return i+1;
}

void quicksort(Card A[], int p, int r){
  int q;
  if(p < r){
    q = partition(A, p, r);
    quicksort(A, p, q-1);
    quicksort(A, q+1, r);
  }
}

Measured memory_bytes: 1776
#include <stdio.h>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

void print(int* A,int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << A[i];
		if (i != n - 1)
		{
			cout << " ";
		}
	}
	cout << endl;
}
int main()
{
	int n;
	cin >> n;
	
	int* A = new int[n];
	for (int i = 0; i < n; i++)
	{
		cin >> A[i];
	}
	for (int i = 1; i < n; i++)
	{
		print(A, n);
		int v = A[i];
		int j = i - 1;
		while (j >= 0 && A[j] > v)
		{
			A[j + 1] = A[j];
			j--;
			
		}
		A[j + 1] = v;
		
	}
	print(A, n);
	return 0;
}


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

int main() {

    int a;
    int b;

    cin >> a >> b;

    if(a < b) {
        cout << "a < b" << endl;
    } else if(a > b) {
        cout << "a > b" << endl;
    } else {
        cout << "a == b" << endl;
    }

    return 0;
}


Measured memory_bytes: 3068
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cctype>

#define MAX 1001
#define INF (1<<29)

using namespace std;

struct Point{
  int x, y;
};

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

int H, W, N;
char field[MAX][MAX];
Point cheese[11];
int d[MAX][MAX];
int ans;

void bfs(){
  for(int i = 1 ; i <= N ; i++){
    Point sp = cheese[i-1];
    int sx = cheese[i-1].x;
    int sy = cheese[i-1].y;
    int gx = cheese[i].x;
    int gy = cheese[i].y;
    
    for(int i = 0 ; i < H ; i++){
      for(int j = 0 ; j < W ; j++){
	d[i][j] = INF;
      }
    }
    
    queue<Point> que;
    
    que.push(sp);
    d[sy][sx] = 0;

    while(!que.empty()){
      Point now = que.front();
      que.pop();
      
      int x = now.x;
      int y = now.y;
      
      if(x == gx && y == gy){
	ans += d[gy][gx];
	break;
      }
      
      for(int i = 0 ; i < 4 ; i++){
	int nx = x + dx[i];
	int ny = y + dy[i];

	if(0 <= nx && nx < W && 0 <= ny && ny < H){
	  if(field[ny][nx] != 'X'){
	    Point next;
	    
	    next.x = nx;
	    next.y = ny;
	    
	    if(d[ny][nx] == INF){
	      d[ny][nx] = d[y][x] + 1;
	      que.push(next);
	    }
	  }
	}
      }
    }
  }
}

int main(){
  cin >> H >> W >> N;
  
  for(int i = 0 ; i < H ; i++){
    for(int j = 0 ; j < W ; j++){
      cin >> field[i][j];
      if(field[i][j] == 'S'){
	cheese[0].x = j;
	cheese[0].y = i;
      }
      if(isdigit(field[i][j])){
	cheese[field[i][j]-'0'].x = j;
	cheese[field[i][j]-'0'].y = i;
      }
    }
  }
  bfs();
  cout << ans << endl;
}
  
  

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

using namespace std;

int main() {
	// your code goes here
	ll n;
	cin >> n;
	ll sum=0;
	for(ll i=1; i<=n; i++){
		if(i%3!=0 && i%5!=0)
			sum+=i;
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;
void YesNo(bool j){cout << (j ? "Yes" : "No") << endl; return;}
void yesno(bool j){cout << (j ? "yes" : "no") << endl; return;}
template<class Head> void pt(Head&& head){cout << head << endl; return;}


int main() {
    int n;
    cin >> n;
    n%=10;
    if(n==3) pt("bon");
    else if(n==0 || n==1 || n==6 || n==8)pt("pon");
    else pt("hon");
    return 0;
}

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

using namespace std;
#define X first
#define Y second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define debug(x) cerr << #x << " = " << (x) << endl;
template<typename T>
ostream& operator<<(ostream& o, vector<T>& v) {
    for (auto& x : v) o << x << ' ';
    return o;
}

int main(){
    std::ios_base::sync_with_stdio(false); cin.tie(0);
    int H, W, h, w;
    cin >> H >> W >> h >> w;
    int num = (H/h) * (W/w);

    int rem = H*W - num;
    int minus = h*w - 1;
    int evil = minus*num;

    if (evil >= rem){
        cout << "No" << endl;
        return 0;
    }
    int k = (int(1e9) - 1) / minus;
    if ((ll)rem * k <= ((ll)minus*k + 1) * num) {
        cout << "No" << endl;
        return 0;
    }

    cout << "Yes" << endl;
    vvi grid(H, vi(W, k));
    for (int i = h-1; i < H; i += h){
        for (int j = w-1; j < W; j += w){
            grid[i][j] = -minus*k - 1;
        }
    }
    for (int i = 0; i < H; i++){
        for (int j = 0; j < W; j++){
            cout << grid[i][j] << ' ';
        }
        cout << endl;
    }

}


Measured memory_bytes: 3968
import java.io.*;

class Main {
    public static void main (String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        String[] arrStr = br.readLine().split(" ");
        int[] A = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = Integer.parseInt(arrStr[i]);
        }

        int count = mergeSort(A, 0, n);
        StringBuilder sb = new StringBuilder("");
        sb.append(A[0]);
        for (int i = 1; i < n; i++) {
            sb.append(" ").append(A[i]);
        }
        sb.append("\n").append(count);
        System.out.println(sb.toString());
    }

    public static int mergeSort(int[] A, int left, int right) {
        int count = 0;
        if (left + 1 < right) {
            int mid = (left + right) / 2;
            count += mergeSort(A, left, mid);
            count += mergeSort(A, mid, right);
            count += merge(A, left, mid, right);
        }
        return count;
    }

    public static int merge(int[] A, int left, int mid, int right) {
        int n1 = mid - left;
        int n2 = right - mid;
        int[] L = new int[n1];
        int[] R = new int[n2];

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

        int i = 0, j = 0;
        for (int k = left; k < right; k++) {
            if (i >= n1) {
                A[k] = R[j];
                j++;
                continue;
            } else if (j >= n2) {
                A[k] = L[i];
                i++;
                continue;
            }
            if (L[i] < R[j]) {
                A[k] = L[i];
                i++;
            } else {
                A[k] = R[j];
                j++;
            }
        }

        return right - left;
    }
}

Measured memory_bytes: 156208
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>
#include <random>
#include <complex>
#include <functional>
#include <bitset>
#include <sstream>
#include <cassert>
#include <time.h>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll inf = 1LL << 60;

template<class T> inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}
template<class T> inline void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}
void printvec (vec &v) {
    Rep (i, (ll)v.size()) {
        cout << v[i] << " \n"[i+1 == (ll)v.size()];
    }
}

ll D = 365;
vec c(26);
mat s(D, vec(26));
vec last(26, 0);


int main(){

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

    clock_t start = clock();

    cin >> D;
    Rep (i, 26) {
        cin >> c[i];
    }
    Rep (i, D) {
        Rep (j, 26) {
            cin >> s[i][j];
        }
    }

    vec t(D);

    ll tmp = 0;
    Rep (i, D) {
        ll ans = 0;
        ll best = -inf;
        Rep (j, 26) {
            ll score = 0;
            score += s[i][j];
            Rep (k, 26) {
                if (k != j) score -= c[k] * (i+1-last[k]);   
            }
            if (score > best) {
                ans = j;
                best = score;
            }
        }

        last[ans] = i+1;
        tmp += s[i][ans];
        Rep (j, 26) {
            tmp -= c[j] * (i+1-last[j]);
        }

        t[i] = ans;
    }

    vector<set<ll>> days(26);
    Rep (i, 26) {
        days[i].insert(-1);
        days[i].insert(D);
    }
    Rep (i, D) {
        days[t[i]].insert(i);
    }

    random_device rnd;
    mt19937 mt(rnd());
    uniform_int_distribution<> randd(0, 364), randq(0, 25);

    while ((clock() - start) < 1.9/CLOCKS_PER_SEC) {
        ll d = randd(mt);
        ll q = randq(mt);

        ll oldscore = tmp;

        tmp -= s[d][t[d]];
        tmp += s[d][q];
        auto old2 = days[t[d]].upper_bound(d);
        old2--;
        old2--;
        auto old1 = old2;
        old2++;
        old2++;
        auto new2 = days[q].lower_bound(d);
        auto new1 = --new2;
        new2++;
        // cout << *old1 << " " << *old2 << " " << *new1 << " " << *new2 << "\n";
        tmp += c[q] * (d-*new1) * (*new2 - d);
        tmp -= c[t[d]] * (d-*old1) * (*old2 - d);

        if (tmp > oldscore) {
            days[t[d]].erase(d);
            days[q].insert(d);
            t[d] = q;
        }
    }

    Rep (i, D) {
        cout << t[i] + 1 << "\n";
    }


}

Measured memory_bytes: 3800
#include<bits/stdc++.h>
using namespace std;
#define int ll
#define ll long long
const ll mod = 998244353;
ll power(ll x, ll y, ll p) {
	ll res = 1ll;
	x = x % p;
	while (y) {
		if (y & 1ll)res = (res * x) % p;
		y = y >> 1ll;
		x = (x * x) % p;
	}
	return res;
}
signed main(){
  int n,r=0;
  cin>>n;
  for(int c,i=0;i<n;++i){
    cin>>c;
    if(c%2)++r;
  }
  cout<<power(3,n,mod)-power(2,n-r,mod);
}

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i, n) for(int i = (int)(n); i >= 0; i--)
#define repm(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define repmr(i, m, n) for(int i = (int)(n); i >= (int)(m); i--)
#define all(x) (x).begin(),(x).end()
#define inf 2e9
#define MOD 1000000007

using namespace std;
typedef long long ll;

vector<vector<int>> tree(200000,vector<int>());
unordered_map<int,int> add;
vector<ll> ans(200000,0);
vector<bool> visited(200000,false);

void dfs(int now, int before){
  if(before < 0) ans[now] = add[now];
  else ans[now] = ans[before] + add[now];
  visited[now] = true;

  int size = tree[now].size();
  rep(i,size){
    if(!visited[tree[now][i]]) dfs(tree[now][i], now);
  }

  return;
}

int main() {
  int n,q; cin >> n >> q;
  vector<int> a(n-1), b(n-1);
  rep(i,n-1){
    cin >> a[i] >> b[i];
    a[i]--;
    b[i]--;
  }
  vector<int> p(q), x(q);
  rep(i,q){
    cin >> p[i] >> x[i];
    p[i]--;
  }

  //add to tree
  rep(i,n-1){
    tree[a[i]].push_back(b[i]);
    tree[b[i]].push_back(a[i]);
  }

  //add to add
  rep(i,q) add[p[i]] += x[i];

  dfs(0,-1);

  rep(i,n){
    cout << ans[i] << endl;
  }
}

Measured memory_bytes: 35656
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define int long long
#define ld long double
#define fi first
#define se second
#define all(uiet) uiet.begin(),uiet.end()
#define read(UIET) for(int i = 0; i < n; ++i) cin >> UIET[i]
#define out(UIET) for(int i = 0; i < n; ++i) cout << UIET[i] << " "
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vpp vector<pair< int, int > >
#define pll pair<int , int >
#define ppll pair < pll , pll >
#define debug(n1) cout << n1 << endl
#define len(a) ((int) (a).size())
#define endl "\n"
#define mod 1000000007
const int INF=(1LL<<60)-1;
bool isPerfectSquare(long double x) {   
    long double sr = sqrt(x); 
    return ((sr - floor(sr)) == 0); 
} 
bool isPrime(int x){
    for(int i = 2; i * i <= x; ++i){
        if(x % i == 0) return 0;
    }
    return 1;
}
int fun(int n){
    if(n & 1) return 3 * n + 1;
    else return n/2;
}
int32_t main(){
    SPEED;
    int n, a, b;
    cin >> n >> a >> b;
    int rem = n % (a + b);
    cout << (n/(a + b)) * a + min(rem, a) ;
}


Measured memory_bytes: 3672
use proconio::input;
use proconio::marker::Usize1;

fn main() {
    input! {
        n: usize,
        m: usize,
        h: [u64; n],
        ab: [(Usize1, Usize1); m],
    };

    let mut ls = vec![n; n];
    for &(a, b) in ab.iter() {
        if h[a] == h[b] {
            ls[b] = a;
            ls[a] = b;
        } else if h[a] > h[b] {
            ls[b] = a;
        } else {
            ls[a] = b;
        }
    }
    let ans = ls.iter().filter(|&&l| l == n).count();
    println!("{}", ans);
}


Measured memory_bytes: 7200
N = int(input())
D, X = map(int, input().split())
chocolates = [X]
for i in range(N):
    A = int(input())
    chocolates.append(1)
    for j in range(1, 101):
        if j * A + 1 > D:
            break
        else:
            chocolates.append(1)
print(sum(chocolates))


Measured memory_bytes: 3060
N = int(input())
S = dict()
for i in range(N):
  arg = str(input())
  if arg in S:
    S[arg] = S[arg] + 1
  else:
    S[arg] = 1

max_count = max(list(S.values()))
#print(max_count)

S_sorted = sorted(S.items(), key=lambda x: x[0])
#print(S_sorted)

for kv in S_sorted:
  if kv[1] == max_count:
    print(kv[0])

Measured memory_bytes: 46556
import java.util.Scanner;

public class Main {

    public static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int x = Integer.parseInt(sc.next());
        int ans = 1;
        int num = 0;
        for (int i = 0; i < n; i++) {
            num += Integer.parseInt(sc.next());
            if (num > x) {
                break;
            }
            ans++;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
typedef vector<string> vstring;
#define _GLIBCXX_DEBUG
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
const int INF = 1 << 30;
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
#define stp(x)  setprecision(x)
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  vint a(n-1);
  vint count(n+1,0);
  rep(i,n-1){
    cin>>a[i];
    count[a[i]]++;
  }
  REP(i,1,n+1){
    cout<<count[i]<<'\n';
  }
  return(0);
}


Measured memory_bytes: 4780
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
const int INF = 1e8;
using namespace std;

typedef complex<double> Point;
typedef Point Vector;
//線分を表す構造体
struct Segment{ Point p1, p2; };
//直線を表す構造体

namespace std{
	bool operator < (const Point &a, const Point &b){
		return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
	}
	bool operator == (const Point &a, const Point &b){
		return a.real() == b.real() && a.imag() == b.imag();
	}
}

// 許容する誤差
#define EPS (1e-10)

int ccw(Point, Point, Point);

// 内積 (dot product) : a・b = |a||b|cosΘ
double dot(Point a, Point b) {
	return (a.real() * b.real() + a.imag() * b.imag());
}

// 外積 (cross product) : a×b = |a||b|sinΘ
double cross(Point a, Point b) {
	return (a.real() * b.imag() - a.imag() * b.real());
}

// a1,a2を端点とする線分とb1,b2を端点とする線分の交差判定
bool isIntersectedLs(Point a1, Point a2, Point b1, Point b2) {
	return ( ccw(a1, a2, b1) * ccw(a1, a2, b2) <= 0 &&
			ccw(b1, b2, a1) * ccw(b1, b2, a2) <= 0 );
}
bool isIntersectedLs(Segment s1, Segment s2) {
	return isIntersectedLs(s1.p1, s1.p2, s2.p1, s2.p2);
}

//ベクトルの位置検出
static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;

int ccw(Point p0, Point p1, Point p2){
	Vector a = p1 - p0;
	Vector b = p2 - p0;
	if( cross(a, b) > EPS ) return COUNTER_CLOCKWISE;
	if( cross(a, b) < -EPS ) return CLOCKWISE;
	if( dot(a, b) < -EPS ) return ONLINE_BACK;
	if( abs(a) < abs(b) ) return ONLINE_FRONT;

	return ON_SEGMENT;
}


double ga[1000][1000], gb[1000][1000];

const int MAX_V = 1000;
double dijkstra(int n, int s, double g[MAX_V][MAX_V]){
	vector<double> dis(n,INF);
	priority_queue<double, vector<pair<double, int>>, greater<pair<double, int>>> q;

	q.emplace(0,s);
	dis[s] = 0;

	while(not q.empty()){
		int pos;
		double cost;
		tie(cost, pos) = q.top(); q.pop();
		if(pos == 1) break;

		rep(to,n){
			if(dis[to] > cost + g[pos][to]){
				dis[to] = cost + g[pos][to];
				q.emplace(dis[to], to);
			}
		}
	}
	return dis[1];
}

double solve(double g[MAX_V][MAX_V], Segment s, vector<Point>& a){
	int n = a.size();
	rep(i,n){
		rep(j,n){
			if(i == j) continue;
			if(isIntersectedLs(s, Segment{a[i], a[j]})){
				g[i][j] = INF;
			}
		}
	}
	return dijkstra(n, 0, g);
}

void input(vector<Point>& a, int n){
	rep(i,n){
		double x, y;
		cin >> x >> y;
		a[i] = Point(x,y);
	}
}

void culDist(double g[MAX_V][MAX_V], vector<Point>& a, int n){
	rep(i,n) rep(j,n) g[i][j] = abs(a[i] - a[j]);
}

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

	int na, nb;
	cin >> na >> nb;

	vector<Point> a(na), b(nb);
	input(a, na);
	input(b, nb);

	culDist(ga, a, na);
	culDist(gb, b, nb);

	double adis = ga[0][1];
	double bdis = gb[0][1];

	double ans = min<double>(
			solve(gb, Segment{a[0], a[1]}, b) + adis,
			solve(ga, Segment{b[0], b[1]}, a) + bdis
			);
	cout << fixed << setprecision(10) << (ans >= INF ? -1 : ans) << endl;
}



Measured memory_bytes: 19084